《厦门大学学报（自然科学版）》

网元子图是指大规模网络基础设施中包含承载具体业务网元的拓扑子图,网元子图可用于网络基础设施运维中的故障排查、诊断与修复.首先定义重要网元的概念; 其次,为确定重要网元子图,提出一个统一框架来度量网元在结构和业务两方面的影响力,将其作为重要网元的衡量标准,并设计了从重要网元扩展生成重要网元子图的高效算法.基于真实的网络基础设施数据以及合成的业务承载数据进行实验,实验结果验证了该方法可以高效地找到高质量的重要网元子图,并用于网络基础设施的运维,提高运维的效率,节省运维的成本.

In many applications,graphs are used to model structural relationships among objects.Large scale network infrastructures can be represented as graphs,where element subgraphs are those subgraphs containing important network elements with many connections and running services.In this paper,we formularize the problem of discovering element subgraphs in network infrastructures.Element subgraphs can help network administrators lower the cost for network infrastructure operation and maintenance.A uniform framework is proposed to model the element importance by using neighborhood influence based on random walk,which considers both structural connections and running services on these network elements.We design an efficient algorithm that skillfully finds the important element subgraphs by expanding the important vertices.Our experiments are based on real data sets with synthetic service information,whose results show that our element subgraphs exhibit high quality.

引言
1 评估网元节点的重要性
2 生成重要网元子图
3 实验结果与分析
4 结论

图1 业务转化为图上的节点<br/>Fig.1 Service vertices in the graph

图1 业务转化为图上的节点
Fig.1 Service vertices in the graph

图2 网元节点影响力分布曲线<br/>Fig.2 The curve of vertex influence distribution

图2 网元节点影响力分布曲线
Fig.2 The curve of vertex influence distribution

表1 数据集特征<br/>Tab.1 Dataset characteristics

表1 数据集特征
Tab.1 Dataset characteristics

图3 数据集SNAP1U和SNAP1N的Rcoverage<br/>Fig.3 Rcoverage of dataset SNAP1U and SNAP1N

图3 数据集SNAP1U和SNAP1N的Rcoverage
Fig.3 Rcoverage of dataset SNAP1U and SNAP1N

图4 数据集SNAP1U和SNAP1N的重要网元子图示例<br/>Fig.4 An element subgraph of dataset SNAP1U and SNAP1N

图4 数据集SNAP1U和SNAP1N的重要网元子图示例
Fig.4 An element subgraph of dataset SNAP1U and SNAP1N

图5 数据集SNAP1U和SNAP1N的传统网元子图示例<br/>Fig.5 An element subgraph of dataset SNAP1U and SNAP1N

图5 数据集SNAP1U和SNAP1N的传统网元子图示例
Fig.5 An element subgraph of dataset SNAP1U and SNAP1N

图6 数据集的运行时间<br/>Fig.6 The running time on datasets

图6 数据集的运行时间
Fig.6 The running time on datasets

图7 数据集SNAP2N的运行时间<br/>Fig.7 The running time on dataset SNAP2N

图7 数据集SNAP2N的运行时间
Fig.7 The running time on dataset SNAP2N

[1] TANG L,LI T,SHWARTZ L,et al.An integrated framework for optimizing automatic monitoring systems in large IT infrastructures[C]∥Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Chicago:ACM,2013:1249-1257.
[2] 李涛.数据挖掘的应用与实践:大数据时代的案例分析[M].厦门:厦门大学出版社,2015:8-9.
[3] KEMPE D,KLEINBERG J,TARDOS É.Maximizing the spread of influence through a social network[C]∥Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Washington DC:ACM,2003:137-146.
[4] LESKOVEC J,KRAUSE C,GUESTRIN C,et al.Cost-effective outbreak detection in networks [C]∥Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,2007:420-429.
[5] LEI S,MANIU S,MO L,et al.Online influence maximization[C]∥Proceedings of ACM SIGKDD International Conference on Konwledge Discovery and Data Mining.Sydney:ACM,2015:645-654.
[6] FARAJTABAR M,DU N,RODRIGUEZ M G,et al.Shaping social activity by incentivizing users[J].Advances in Neural Information Processing Systems,2014,27:2474-2482.
[7] JEH G,WIDOM J.SimRank:a measure of structural-context similarity [C]∥Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,2002:538-543.
[8] PALMER C.R,FALOUTSOS C.Electricity based external similarity of categorical attributes[C]∥Procee-dings of Pacific-Asia Conference on Knowledge Discovery and Data Mining.New York:ACM,2003:486-500.
[9] NEWMAN M E.Spectral methods for community detection and graph partitioning[J].Physical Review E Statistical Nonlinear and Soft Matter Physics,2013,88(4):042822.
[10] NEWMAN M E J.Community detection and graph partitioning[J].EPL,2013,103(2):330-337.
[11] LIN C C,KANG J R,CHEN J Y.An integer programming approach and visual analysis for detecting hierarchical community structures in social networks[J].Information Sciences,2015,299:296-311.
[12] REN J,WANG J,LI M,et al.Identifying protein complexes based on density and modularity in protein-protein interaction network[J].BMC Systems Biology,2013,7(S4):1-15.
[13] LIU G,WONG L,CHUA H N.Complex discovery from weighted PPI networks[J].Bioinformatics,2009,25(15):1891-1897.
[14] PONS P,LATAPY M.Computing communities in large networks using random walks[J].Journal of Graph Algorithms and Applications,2006,10(2):191-218.
[15] TONG H,FALOUTSOS C.Center-piece subgraphs:problem definition and fast solutions [C]∥Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,2006:404-413.

备注

引言

1 评估网元节点的重要性

2 生成重要网元子图

3 实验结果与分析

4 结论

学报简介

备注

引言

1 评估网元节点的重要性

2 生成重要网元子图

3 实验结果与分析

4 结 论

学报简介

4 结论