基于K-sup稠密子图的大规模复杂网络概要算法及可视化
|
摘要
现实社会存在大量复杂网络,随着大数据时代的来临,复杂网络数据规模不断扩大,难以进行算法分析和可视化展示.针对复杂网络小世界、无标度特性,提出基于K-sup稠密子图的复杂网络概要算法,利用三角形在网络中的同质性和传递性发现复杂网络中的稠密子图,结合模块度最大化,将子图中相似的节点归并为超点;运用分层结构存储概要图,并进行可视化显示.该算法能对大规模复杂网络进行有效压缩,保持原网络的性质.在5个真实数据集上进行对比实验,显示出该算法在压缩率、幂率性和平均聚类系数的保持等指标优于已有算法,同时在大规模数据下具有保持网络拓扑结构且支持概要图分层可视化的优点.
There are a large number of complex networks in the real world. With the advent of the era of big data, the scale of complex network data is constantly expanding. It is difficult to analyze and visualize them.In this paper, a complex network summary algorithm based on K-sup dense subgraphs was proposed for complex networks with small-world and scale-free features. Using the homogeneity and transitivity of triangles in the network, this algorithm found the dense subgraphs in complex networks by combining the modularity maximization structure. The similar nodes in subgraphs were merged into super points. Hierarchical graphs were stored and visually displayed. As a result, the algorithm can compress large-scale complex networks effectively and keep the properties of the original network. In five real data sets, the experimental results show that the proposed algorithm is superior to the existing algorithms in terms of compression ratio,power rate and average clustering coefficient. At the same time, it also has the advantages of maintaining network topology and supporting hierarchical visualization of summary graphs in large-scale data.
There are a large number of complex networks in the real world. With the advent of the era of big data, the scale of complex network data is constantly expanding. It is difficult to analyze and visualize them.In this paper, a complex network summary algorithm based on K-sup dense subgraphs was proposed for complex networks with small-world and scale-free features. Using the homogeneity and transitivity of triangles in the network, this algorithm found the dense subgraphs in complex networks by combining the modularity maximization structure. The similar nodes in subgraphs were merged into super points. Hierarchical graphs were stored and visually displayed. As a result, the algorithm can compress large-scale complex networks effectively and keep the properties of the original network. In five real data sets, the experimental results show that the proposed algorithm is superior to the existing algorithms in terms of compression ratio,power rate and average clustering coefficient. At the same time, it also has the advantages of maintaining network topology and supporting hierarchical visualization of summary graphs in large-scale data.
引文
[1]Zheng Xiao, Chen Jianping, Shao Jiali, et al. Analysis on topological properties of Beijing urban public transit based on complexnetworktheroy[J].ActaPhysicaSinica,2012,61(19):190510(in Chinese)(郑啸,陈建平,邵佳丽,等.基于复杂网络理论的北京公交网络拓扑性质分析[J].物理学报, 2012, 61(19):190510)
[2]Yang Bo, Liu Dayou, Liu Jiming, et al. Complex network clustering algorithms[J]. Journal of Software, 2009, 20(1):54-66(in Chinese)(杨博,刘大有,LiuJiming,等.复杂网络聚类方法[J].软件学报, 2009, 20(1):54-66)
[3]Liu Xu, Yi Dongyun. Complex network community detection bylocalsimilarity[J].ActaAutomaticaSinica,2011,37(12):1520-1529(in Chinese)(刘旭,易东云.基于局部相似性的复杂网络社区发现方法[J].自动化学报, 2011, 37(12):1520-1529)
[4]SunChong,LuYansheng.Clustering-basedalgorithmstosemanticsummarizinggraphwithmulti-attributes’hierarchical structures[J]. Computer Science, 2013, 40(8):165-171(in Chinese)(孙翀,卢炎生.基于概念分层的图汇总算法[J].计算机科学, 2013, 40(8):165-171)
[5]Yang Hailu, Zhang Jianpei, Yang Jing. Compressing online social networks by calibrating structure redundancy[J]. Journal of ComputerResearchandDevelopment,2013,50(12):2504-2519(in Chinese)(杨海陆,张健沛,杨静.基于结构冗余性校准的在线式社会网络压缩[J].计算机研究与发展,2013,50(12):2504-2519)
[6]LiHongbo,ZhangJianpei,YangJing,etal.Socialnetwork compressionbasedontheimportanceofthecommunity nodes[J]. Acta Scientiarum Naturalium Universitatis Pekinensis,2013, 49(1):117-125(in Chinese)(李泓波,张健沛,杨静,等.基于社区节点重要性的社会网络压缩方法[J].北京大学学报:自然科学版,2013,49(1):117-125)
[7]Li Tiantian, Lu Gang, Xu Nanshan, et al. Compressing layout algorithm for large complex network based on k-core[J]. Computer Engineering, 2016, 42(5):308-312(in Chinese)(李甜甜,卢罡,许南山,等.基于k-core的大规模复杂网络压缩布局算法[J].计算机工程, 2016,42(5):308-312)
[8]NavlakhaS,RastogiR,ShrivastavaN.Graphsummarization with bounded error[C]//Proceedings of the ACM SIGMOD InternationalConferenceonManagementofData.NewYork:ACM Press, 2008:419-432
[9]Liu Y K, Dighe A, Safavi T, et al. Graph summarization:a survey[OL].[2018-03-16]. https://arxiv.org/pdf/1612.04883.pdf
[10]Liu X J, Tian Y Y, He Q, et al. Distributed graph summarization[C]//Proceedingsofthe23rdACMInternationalConference on Information and Knowledge Management. New York:ACM Press, 2014:799-808
[11]WangXiaohua,YangXinyan,JiaoLicheng.Compressionof complexnetworksbasedonmultiscalegeometricanalysis[J].Journal of Electronics&Information Technology, 2009, 31(4):968-972(in Chinese)(王晓华,杨新艳,焦李成.基于多尺度几何分析的复杂网络压缩策略[J].电子与信息学报2009, 31(4):968-972)
[12]Seo H, Park K, Han Y, et al. An effective graph summarization andcompressiontechniqueforalarge-scaledgraph[J].The Journal of Supercomputing, 2018(12):1-15
[13]Satuluri V, Parthasarathy S, Ruan Y. Local graph sparsification for scalable clustering[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data. New York:ACM Press, 2011:721-732
[14]Lindner G, Staudt C L, Hamann M, et al. Structure-preserving sparsification of social networks[C]//Proceedings of the IEEE ACMInternationalConferenceonAdvancesinSocialNetworksAnalysisandMining.NewYork:ACMPress,2015:448-454
[15]Zhao Runqian, Wu Yu, Chen Xin. An algorithm for large-scale socialnetworkcommunitydetectionandvisualization[J].JournalofComputer-AidedDesign&ComputerGraphics,2017, 29(2):328-336(in Chinese)(赵润乾,吴渝,陈昕.大规模社交网络社区发现及可视化算法[J].计算机辅助设计与图形学学报,2017,29(2):328-336)
[16]Zhu Zhiliang, Lin Sen, Cui Kun, et al. Network topology layout algorithm based on community detection of complex networks[J].JournalofComputer-AidedDesign&Computer Graphics, 2011, 23(11):1808-1815(in Chinese)(朱志良,林森,崔坤,等.基于复杂网络社区划分的网络拓扑结构可视化布局算法[J].计算机辅助设计与图形学学报, 2011, 23(11):1808-1815)
[17]HuYF.Visualizationoflargenetworks[M].NewYork:Springer, 2014
[18]Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics:Theory and Experiment, 2008, 2008(10):P10008
[19]ZhengL,JeffreyXY,HongC.Approximatehomogeneous graphsummarization[J].JournalofInformationProcessing,2012, 20(1):77-88
[20]Huang X, Cheng H, Qin L, et al. Querying k-truss community inlargeanddynamicgraphs[C]//ProceedingsoftheACM SIGMODInternationalConferenceonManagementofData.New York:ACM Press, 2014:1311-1322
[21]LiZhenjun,LiRonghua,YangXuan,etal.Akcoretruss communitymodelanddecompositionandsearchalgorithm:China, 106844500 A[P]. 2017-06-13(in Chinese)(李振军,李荣华,杨烜,等.一种k core truss社区模型及分解、搜索算法:中国, 106844500 A[P]. 2017-06-13)
[22]Altaf-Ul-Amin M, Shinbo Y, Mihara K, et al. Development and implementation of an algorithm for detection of protein complexesinlargeinteractionnetworks[J].BMCBioinformatics,2006, 7:207
[23]ZinsmaierM,BrandesU,DeussenO,etal.Interactivelevel-of-detail rendering of large graphs[J]. IEEE Transactions on VisualizationandComputerGraphics,2012,18(12):2486-2495
[24]CuiWW,ZhouHY,QuHM,etal.Geometry-basededge clusteringforgraphvisualization[J].IEEETransactionson Visualization and Computer Graphics, 2008, 14(6):1277-1284
[25]Yang Guang, Wu Yu. Analysis of internal attack experimental datsets[J]. Computer Knowledge and Technology, 2016, 12(21):55-56(in Chinese)(杨光,吴钰.内部攻击实验数据集浅析[J].电脑知识与技术, 2016, 12(21):55-56
[2]Yang Bo, Liu Dayou, Liu Jiming, et al. Complex network clustering algorithms[J]. Journal of Software, 2009, 20(1):54-66(in Chinese)(杨博,刘大有,LiuJiming,等.复杂网络聚类方法[J].软件学报, 2009, 20(1):54-66)
[3]Liu Xu, Yi Dongyun. Complex network community detection bylocalsimilarity[J].ActaAutomaticaSinica,2011,37(12):1520-1529(in Chinese)(刘旭,易东云.基于局部相似性的复杂网络社区发现方法[J].自动化学报, 2011, 37(12):1520-1529)
[4]SunChong,LuYansheng.Clustering-basedalgorithmstosemanticsummarizinggraphwithmulti-attributes’hierarchical structures[J]. Computer Science, 2013, 40(8):165-171(in Chinese)(孙翀,卢炎生.基于概念分层的图汇总算法[J].计算机科学, 2013, 40(8):165-171)
[5]Yang Hailu, Zhang Jianpei, Yang Jing. Compressing online social networks by calibrating structure redundancy[J]. Journal of ComputerResearchandDevelopment,2013,50(12):2504-2519(in Chinese)(杨海陆,张健沛,杨静.基于结构冗余性校准的在线式社会网络压缩[J].计算机研究与发展,2013,50(12):2504-2519)
[6]LiHongbo,ZhangJianpei,YangJing,etal.Socialnetwork compressionbasedontheimportanceofthecommunity nodes[J]. Acta Scientiarum Naturalium Universitatis Pekinensis,2013, 49(1):117-125(in Chinese)(李泓波,张健沛,杨静,等.基于社区节点重要性的社会网络压缩方法[J].北京大学学报:自然科学版,2013,49(1):117-125)
[7]Li Tiantian, Lu Gang, Xu Nanshan, et al. Compressing layout algorithm for large complex network based on k-core[J]. Computer Engineering, 2016, 42(5):308-312(in Chinese)(李甜甜,卢罡,许南山,等.基于k-core的大规模复杂网络压缩布局算法[J].计算机工程, 2016,42(5):308-312)
[8]NavlakhaS,RastogiR,ShrivastavaN.Graphsummarization with bounded error[C]//Proceedings of the ACM SIGMOD InternationalConferenceonManagementofData.NewYork:ACM Press, 2008:419-432
[9]Liu Y K, Dighe A, Safavi T, et al. Graph summarization:a survey[OL].[2018-03-16]. https://arxiv.org/pdf/1612.04883.pdf
[10]Liu X J, Tian Y Y, He Q, et al. Distributed graph summarization[C]//Proceedingsofthe23rdACMInternationalConference on Information and Knowledge Management. New York:ACM Press, 2014:799-808
[11]WangXiaohua,YangXinyan,JiaoLicheng.Compressionof complexnetworksbasedonmultiscalegeometricanalysis[J].Journal of Electronics&Information Technology, 2009, 31(4):968-972(in Chinese)(王晓华,杨新艳,焦李成.基于多尺度几何分析的复杂网络压缩策略[J].电子与信息学报2009, 31(4):968-972)
[12]Seo H, Park K, Han Y, et al. An effective graph summarization andcompressiontechniqueforalarge-scaledgraph[J].The Journal of Supercomputing, 2018(12):1-15
[13]Satuluri V, Parthasarathy S, Ruan Y. Local graph sparsification for scalable clustering[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data. New York:ACM Press, 2011:721-732
[14]Lindner G, Staudt C L, Hamann M, et al. Structure-preserving sparsification of social networks[C]//Proceedings of the IEEE ACMInternationalConferenceonAdvancesinSocialNetworksAnalysisandMining.NewYork:ACMPress,2015:448-454
[15]Zhao Runqian, Wu Yu, Chen Xin. An algorithm for large-scale socialnetworkcommunitydetectionandvisualization[J].JournalofComputer-AidedDesign&ComputerGraphics,2017, 29(2):328-336(in Chinese)(赵润乾,吴渝,陈昕.大规模社交网络社区发现及可视化算法[J].计算机辅助设计与图形学学报,2017,29(2):328-336)
[16]Zhu Zhiliang, Lin Sen, Cui Kun, et al. Network topology layout algorithm based on community detection of complex networks[J].JournalofComputer-AidedDesign&Computer Graphics, 2011, 23(11):1808-1815(in Chinese)(朱志良,林森,崔坤,等.基于复杂网络社区划分的网络拓扑结构可视化布局算法[J].计算机辅助设计与图形学学报, 2011, 23(11):1808-1815)
[17]HuYF.Visualizationoflargenetworks[M].NewYork:Springer, 2014
[18]Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics:Theory and Experiment, 2008, 2008(10):P10008
[19]ZhengL,JeffreyXY,HongC.Approximatehomogeneous graphsummarization[J].JournalofInformationProcessing,2012, 20(1):77-88
[20]Huang X, Cheng H, Qin L, et al. Querying k-truss community inlargeanddynamicgraphs[C]//ProceedingsoftheACM SIGMODInternationalConferenceonManagementofData.New York:ACM Press, 2014:1311-1322
[21]LiZhenjun,LiRonghua,YangXuan,etal.Akcoretruss communitymodelanddecompositionandsearchalgorithm:China, 106844500 A[P]. 2017-06-13(in Chinese)(李振军,李荣华,杨烜,等.一种k core truss社区模型及分解、搜索算法:中国, 106844500 A[P]. 2017-06-13)
[22]Altaf-Ul-Amin M, Shinbo Y, Mihara K, et al. Development and implementation of an algorithm for detection of protein complexesinlargeinteractionnetworks[J].BMCBioinformatics,2006, 7:207
[23]ZinsmaierM,BrandesU,DeussenO,etal.Interactivelevel-of-detail rendering of large graphs[J]. IEEE Transactions on VisualizationandComputerGraphics,2012,18(12):2486-2495
[24]CuiWW,ZhouHY,QuHM,etal.Geometry-basededge clusteringforgraphvisualization[J].IEEETransactionson Visualization and Computer Graphics, 2008, 14(6):1277-1284
[25]Yang Guang, Wu Yu. Analysis of internal attack experimental datsets[J]. Computer Knowledge and Technology, 2016, 12(21):55-56(in Chinese)(杨光,吴钰.内部攻击实验数据集浅析[J].电脑知识与技术, 2016, 12(21):55-56