基于局部相似性的复杂网络社区发现方法

刘旭; 易东云

doi:10.3724/SP.J.1004.2011.01520

基于局部相似性的复杂网络社区发现方法

doi: 10.3724/SP.J.1004.2011.01520 cstr: 32138.14.SP.J.1004.2011.01520

刘旭^,,
易东云

1.
国防科学技术大学理学院数学与系统科学系长沙 410073

详细信息

通讯作者:
刘旭国防科学技术大学理学院数学与系统科学系博士研究生. 2007年获国防科学技术大学应用数学硕士学位. 主要研究方向为复杂海量信息处理. E-mail: liuxuwork@gmail.com

计量
- 文章访问数: 2650
- HTML全文浏览量: 59
- PDF下载量: 2161
- 被引次数: 0
出版历程
- 收稿日期: 2011-04-15
- 修回日期: 2011-07-16
- 刊出日期: 2011-12-20

Complex Network Community Detection by Local Similarity

LIU Xu^,,
YI Dong-Yun

1.
Department of Mathematics and Systems Science, College of Science, National University of Defense Technology, Changsha 410073

摘要

摘要: 复杂网络是复杂系统的典型表现形式, 社区结构是复杂网络最重要的结构特征之一. 针对复杂网络的社区结构发现问题, 本文提出一种新的局部相似性度量, 并结合层次聚类算法用于社区结构发现. 相对全局的相似性度量, 本文提出的相似性度量具有较低的计算开销; 同时又能很好地刻画网络的结构特征, 克服了传统局部相似性度量在某些情形下对节点相似性的低估倾向. 为了将局部相似性度量用于社区结构发现, 推广了传统的Ward层次聚类算法, 使之适用于具有相似性度量的任意对象, 并将其用于复杂网络社区结构发现. 在合成和真实世界的网络上进行了实验, 并与典型算法进行了比较, 实验结果表明所提算法的可行性和有效性.
- 复杂网络 /
- 社区结构发现 /
- 相似性度量 /
- 层次聚类
Abstract: Complex networks are a typical form of representation of complex systems. Community structure is one of the most important structural characteristics of complex networks. In this paper, we propose a new measurement of similarity based on local structures for the purpose of detecting communities in complex networks. Compared to the similarity measures based on the entire network, the proposed similarity measure requires less computation and produces good descriptions of the structural characteristics of the networks. Meanwhile, it reverses the tendency of under-estimating produced by some existing similarity measures based on local structures. To utilize our measurement of similarity to the detection of community structures, we also generalize the Ward hierarchical clustering algorithm so that it is applicable to any object that has similarity measurement. And as an application we particularly employ this algorithm to detect community structures in complex networks. The proposed method is tested on both computer-generated and real-world networks, and is compared with the typical algorithms in community detection. Experimental results verify and confirm the feasibility and validity of the proposed method.
- Complex networks /
- community structure detection /
- similarity measurement /
- hierarchical clustering

HTML全文

参考文献(1)

[1]

He Dong-Xiao,Zhou Xu,Wang Zuo,Zhou Chun-Guang,Wang Zhe,Jin Di.Community mining in complex net-works—clustering combination based genetic algorithm.Acta Automatica Sinica,2010,36(8):1160-1170(何东晓,周栩,王佐,周春光,王喆,金弟.复杂网络社区挖掘—基于聚类融合的遗传算法.自动化学报,2010,36(8):1160-1170)[2] Newman M E J.The structure and function of complex networks.SIAM Review,2003,45(2):167-256[3] Scheer M.Complex systems:foreseeing tipping points.Nature,2010,467(7314):411-412[4] Newman M E J.Networks:an Introduction.New York:Oxford University Press.2010[5] Newman M E J.Scientific collaboration networks:I.network construction and fundamental results.Physical Review E,2001,64(1):016131[6] Zeng J,Cheung W K,Li C H,Liu J M.Coauthor network topic models with application to expert finding.In:Proceedings of the IEEE/WIC/ACM International Confer-ence on Web Intelligence and Intelligent Agent Technology.Toronto,Canada:IEEE,2010.366-373[7] Guimerà R,Danon L,Díaz-Guilera A,Giralt F,Arenas A.Self-similar community structure in a network of human in-teractions.Physical Review E,2003,68(6):065103[8] Costa L F,Oliveira O,Travieso G,Rodrigues F A,VillasBoas P,Antiqueira L,Viana M P,Correa Rocha L.Analyz-ing and modeling real-world phenomena with complex net-works:a survey of applications.Advances in Physics,2011,60(3):329-412[9] Watts D J,Strogatz S H.Collective dynamics of“small-world”networks.Nature,1998,393(6638):440-442[10] Leij M V,Goyal S.Strong ties in a small world.Review ofNetwork Economics,2011,10(2):1-21[11] Barabási A L,Albert R.Emergence of scaling in randomnetworks.Science,1999,286(5439):509-512[12] Karsai M,Kivel M,Pan R K,Kaski K,Kertész J,BarabásiA-L,Saramki J.Small but slow world:how network topology and burstiness slow down spreading.Physical Review E,2011,83(2):025102[13] Arenas A,Cabrales A,Danon L,Díaz-Guilera A,GuimeràR,Vega-Redondo F.Optimal information transmission inorganizations:search and congestion.Review of EconomicDesign,2010,14(1):75-93[14] Hu Y Q,Wang Y G,Li D Q,Havlin S,Di Z R.Possible origin of ecient navigation in small worlds.Physical ReviewLetters,2011,106(10):108-701[15] Arenas A,Diaz-Guilera A,Pérez-Vicente C J.Synchroniza-tion reveals topological scales in complex networks.PhysicalReview Letters,2006,96(11):114102[16] Arenas A,Diaz-Guilera A,Perez-Vicente C J.Synchronization processes in complex networks,Physica D:Nonline orPhenomena,2006,224(1-2):27-34[17] Girvan M,Newman M E J.Community structure in social and biological networks.Proceedings of the NationalAcademy of Sciences of the United States of America,2002,99(12):7821-7826[18] Wasserman S,Faust K.Social Network Analysis,Cam-bridge:Cambridge University Press,1994.[19] Kwak H,Lee C H,Park H,Moon S.What is Twitter,a socialnetwork or a news media-In:Proceedings of the 19th In-ternational Conference on World Wide Web.Raleigh,NorthCarolina,USA:ACM,2010.591-600[20] Fortunato S.Community detection in graphs.Physics Re-ports,2010,486(3-5):75-174[21] Wang X H,Jiao L C,Wu J S.Phase synchronization onsmall-world networks with community structure.ChinesePhysics B,2010,19(2):020501[22] Newman M E J.Modularity and community structure innetworks.Proceedings of the National Academy of Sciencesof the United States of America,2006,103(23):8577-8582[23] Brandes U,Delling D,Gaertler M,Gorke R,Hoefer M,Nikoloski Z,Wagner D.On modularity clustering.IEEETransactions on Knowledge and Data Engineering 2008,20(2):172-188[24] Duch J,Arenas A.Community detection in complex networks using extremal optimization.Physical Review E,2005,72(2):027104[25] Reichardt J,Bornholdt S.Statistical mechanics of community detection.Physical Review E,2006,74(1):016110[26] Newman M E J.Finding community structure using theeigenvectors of matrices.Physical Review E,2006,74(3):036104[27] Shen H W,Cheng X Q.Spectral methods for the detectionof network community structure:a comparative analysis.Journal of Statistical Mechanics:Theory and Experiment,2010,10:P10020[28] Newman M E J,Girvan M.Finding and evaluating community structure in networks.Physical Review E,2004,69(2):026113[29] Clauset A,Newman M E J,Moore C.Finding communitystructure in very large networks.Physical Review E,2004,70(6):066111[30] Lv L Y,Zhou T.Link prediction in complex networks:asurvey.Physica A,2011,390(6):1150-1170[31] Zachary W W.An information flow model for conflict andfission in small groups.Journal of Anthropological Research,1977,33(4):452-473[32] Katz L.A new status index derived from sociometric analysis.Psychmetrika,1953,18(1):39-43[33] Leicht E A,Holme P,Newman M E J.Vertex similarity innetworks.Physical Review E,2006,73(2):026120[34] Fouss F,Pirotte A,Renders J M,Saerens M.Random-walkcomputation of similarities between nodes of a graph withapplication to collaborative recommendation.IEEE Transactions on Knowledge and Data Engineering,2007,19(3):355-369[35] Hamers L,Hemeryck Y,Herweyers G,Janssen M,KetersH,Rousseau R,Vanhoutte A.Similarity measures in scientometric research:the Jaccard index versus Saltons cosine formula.Information Processing Management,1989,25(3):315-318[36] Salton G,McGill M J.Introduction to Modern InformationRetrieval.New York:McGraw-Hill,1983[37] Zhou T,Lv L Y,Zhang Y C.Predicting missing links vialocal information.The European Physical Journal B:Con-densed Matter and Complex Systems,2009,71(4):623-630[38] Mirkin B.Core Concepts in Data Analysis:Summarization,Correlation and Visualization.London:Springer,2011.283-313[39] Raghavan U N,Albert R,Kumara S.Near linear time algorithm to detect community structures in largescale networks.Physical Review E,2007,76(3):036106[40] Newman M E J.Fast algorithm for detecting communitystructure in networks.Physical Review E,2004,69(6):066133[41] Danon L,Diaz-Guilera A,Duch J,Arenas A.Comparing community structure identification.Journal of Statis-tical Mechanics:Theory and Experiment,2005,2005(9):P09008[42] Sorensen D C.Implicit application of polynomial filters in a κ-step arnoldi method.SIAM Journal of Matrix Analysisand Applications,1992,13(1):357-385[43] Lusseau D.The emergent properties of a dolphin social network.Proceedings of the Royal Society of London.Series B:Biological Sciences,2003,270(2),186-188[44] Gleiser P,Danon L.Community structure in jazz.Advancesin Complex Systems,2003,6(4):565-573[45] Adamic L A,Glance N.The political blogosphere and the 2004 US election:divided they blog.In:Proceedings of the3rd International Workshop on the Weblogging Ecosystem,New York,USA:ACM,2005.36-43[46] Jeong H,Mason S,Barabási A L,Oltvai Z N.Lethalityand centrality in protein networks.Nature,2001,411(6833):41-42[47] Ahn Y Y,Bagrow J P,Lehmann S.Link communities revealmultiscale complexity in networks.Nature,2011,466(7307):761-764[48] Gregory S.Fuzzy overlapping communities in networks.Journal of Statistical Mechanics:Theory and Experiment,2011,2:P02017

施引文献

资源附件(0)

访问统计