2.765

2022影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

刘旭 易东云

刘旭, 易东云. 基于局部相似性的复杂网络社区发现方法. 自动化学报, 2011, 37(12): 1520-1529. doi: 10.3724/SP.J.1004.2011.01520
引用本文: 刘旭, 易东云. 基于局部相似性的复杂网络社区发现方法. 自动化学报, 2011, 37(12): 1520-1529. doi: 10.3724/SP.J.1004.2011.01520
LIU Xu, YI Dong-Yun. Complex Network Community Detection by Local Similarity. ACTA AUTOMATICA SINICA, 2011, 37(12): 1520-1529. doi: 10.3724/SP.J.1004.2011.01520
Citation: LIU Xu, YI Dong-Yun. Complex Network Community Detection by Local Similarity. ACTA AUTOMATICA SINICA, 2011, 37(12): 1520-1529. doi: 10.3724/SP.J.1004.2011.01520

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

doi: 10.3724/SP.J.1004.2011.01520
详细信息
    通讯作者:

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

Complex Network Community Detection by Local Similarity

  • 摘要: 复杂网络是复杂系统的典型表现形式, 社区结构是复杂网络最重要的结构特征之一. 针对复杂网络的社区结构发现问题, 本文提出一种新的局部相似性度量, 并结合层次聚类算法用于社区结构发现. 相对全局的相似性度量, 本文提出的相似性度量具有较低的计算开销; 同时又能很好地刻画网络的结构特征, 克服了传统局部相似性度量在某些情形下对节点相似性的低估倾向. 为了将局部相似性度量用于社区结构发现, 推广了传统的Ward层次聚类算法, 使之适用于具有相似性度量的任意对象, 并将其用于复杂网络社区结构发现. 在合成和真实世界的网络上进行了实验, 并与典型算法进行了比较, 实验结果表明所提算法的可行性和有效性.
  • [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
  • 加载中
计量
  • 文章访问数:  2533
  • HTML全文浏览量:  45
  • PDF下载量:  2137
  • 被引次数: 0
出版历程
  • 收稿日期:  2011-04-15
  • 修回日期:  2011-07-16
  • 刊出日期:  2011-12-20

目录

    /

    返回文章
    返回