南京大学学报(自然科学版) ›› 2017, Vol. 53 ›› Issue (3): 537–.

• • 上一篇    下一篇

 基于局部结构特征的重叠社区挖掘研究进展

 张泽华1*，段力畑1，段　富1，张　楠2   

  • 出版日期:2017-05-30 发布日期:2017-05-30
  • 作者简介: 1.太原理工大学计算机科学与技术学院，太原，030024：2.烟台大学计算机与控制工程学院，烟台，264005
  • 基金资助:
    基金项目：国家自然科学基金(61503273，61403329)，太原理工大学青年创新团队项目(2014TD056)
    收稿日期：2017－03－21
    *通讯联系人，E­mail：zehua_zhang@163.com

 Research progress of overlapping community detection methods based on local structure

 Zhang Zehua1*，Duan Litian1，Duan Fu1，Zhang Nan2   

  • Online:2017-05-30 Published:2017-05-30
  • About author: 1.College of Computer Science and Technology，Taiyuan University of Technology，Taiyuan，030024，China；
    2．School of Computer and Control Engineering，Yantai University，Yantai，264005，China

PDF (PC)

812

摘要：  社区挖掘是复杂网络研究的核心内容之一．基于局部结构建模的重叠社区发现方法由于可利用局部先验知识，具有适应网络动态环境，建模速度快，可多角度呈现局部结构特征等优点，当前已成为大规模网络发现研究的前沿热点．从理论发展沿革与现实应用的视角，介绍重叠社区发现研究近来的相关研究进展．通过分析重叠社区发现研究存在的关键问题，给出基于局部结构特征的重叠社区挖掘研究框架，并对几类典型的重叠社区发现方法展开分析比较．然后进一步阐述和探讨如何面对现实超大规模网络、多态异构网络、不确定性数据、动态演化结构等方面面临的巨大挑战．最后总结并展望了基于局部结构的重叠社区发现研究的未来方向和前景．

Abstract:  Community mining is one of the core contents of complex network research.Compared to global optimization methods，local structure based community detection models usually have the advantage of using local prior knowledge，and adapt to the dynamic network environment with rapid modeling capabilities in multi­views and so on.Nowadays such methods have become the current hot research on the large scale network.From the perspective of theoretical evolution and practical application，the paper introduces the recent research progress of overlapping community detection.Based on the analysis of the key problems in the research，this study presents the research framework of overlapping community mining based on local structure，and then compares and analyzes some typical overlapping community discovery methods，named as clique percolation methods，local expansion methods，link communities optimization methods，label propagation algorithm，community link structure based methods，which depend on the community measurements with local optimization strategy.The clique percolation can found local communities in the dense network with highly overlapping communities.And the local expansion methods independent of the global network effectively reveals the structure of local communities and can show the hierarchical and overlapping features in local.The link community optimization with natural overlaps on links can effectively deal with overlapping networks，while Label Propagation Algorithms(LPA)has good performance in computational complexity，usually suitable for community detection in large scale networks.Link prediction based methods be closely linked with structural similarity on the target network.Moreover，we discuss the issues how to face the enormous challenges of the large scale network with massive data，polymorphic heterogeneous network，complex network structure with uncertainty，and dynamic evolution and so on.Finally，the paper summarizes the future work about overlapping community detection.

 [1]　Girvan M，Newman M E J．Community structure in social and biological networks.Proceedings of the National Academy of Sciences，2002，99(12)：7821－7826.
[2] Fortunato S．Community detection in graphs.Physics Reports，2010，486(3)：75－174.
[3] Newman M E J，Girvan M．Finding and evaluating community structure in networks.Physical Review E，2004，69(2)：026113.
[4] Newman M E J．Finding community structure in networks using the eigenvectors of matrices.Physical Review E，2006，74(3)：036104.
[5] Pons P，Latapy M．Computing communities in large networks using random walks.In：Proceedings of the Computer and Information Sciences(ISCIS 2005)．Springer，2005：284－293.
[6] Gregory S．Fuzzy overlapping communities in networks.Journal of Statistical Mechanics：Theory and Experiment，2011，2(2)：P02017.
[7] Havemann F，Gläser J，Heinz M，et al.Identifying overlapping and hierarchical thematic structures in networks of scholarly papers：A comparison of three approaches.PLOS ONE，2012，7(3)：e33255.　
[8] Schaeffer S E．Graph clustering.Computer Science Review，2007，1(1)：27－64.
[9] Shen H W，Cheng X Q，Cai K，et al.Detect overlapping and hierarchical community structure in networks.Physica A：Statistical Mechanics and its Applications，2009，388(8)：1706－1712.
[10] Clauset A，Newman M E，Moore C．Finding community structure in very large networks.Physical Review E，2004，70(6)：066111.
[11] Blondel V D，Guillaume J L，Lambiotte R，et al.Fast unfolding of communities in large networks.Journal of Statistical Mechanics Theory & Experiment，2008，2008(10)：155－168.
[12] Papadopoulos S，Kompatsiaris Y，Vakali A，et al.Community detection in social media.Data Mining and Knowledge Discovery，2011，24(3)：515－54.
[13] Clauset A．Finding local community structure in networks.Physical Review E，2005，72(2)：026132.
[14] Palla G，Derenyi I，Farkas I，et al.Uncovering the overlapping community structures of complex networks in nature and society.Nature，2005，435(7043)：814－818.
[15] Evans T S，Lambiotte R．Line graphs，link partitions，and overlapping communities.Physical Review E，2009，80(1)：016105.
[16] Lancichinetti A，Fortunato S，Kertész J．Detecting the overlapping and hierarchical community structure in complex networks.New Journal of Physics，2009，11(3)：033015.
[17] Lee C，Reid F，McDaid A，et al.Detecting highly overlapping community structure by greedy clique expansion.In：Proceedings of the 4th International Workshop on Social Network Mining and Analysis.New York，USA：ACM，2010：33－42.
[18] Havemann F，Heinz M，Struck A，et al.Identification of overlapping communities and their hierarchy by locally calculating community­changing resolution levels.Computer Science，2010，2011(01)：01023.
[19] Condon A，Karp R M．Algorithms for graph partitioning on the planted partition model.Random Structures and Algorithms，2001，18(2)：116－140.
[20] Ahn Y Y，Bagrow J P，Lehmann S．Link communities reveal multiscale complexity in networks.Nature，2010，466(7307)：761－764.
[21] Ball B，Karrer B，Newman M E J．An efficient and principled method for detecting communities in networks.Physical Review E，2011，84(3)：036103.
[22] Kim Y，Jeong H．Map equation for link communities.Physical Review E，2011，84(2)：026110.
[23] Raghavan U N，Albert R，Kumara S．Near linear time algorithm to detect community structures in large­scale networks.Physical Review E，2007，76(3)：036106.
[24] Leung I X，Hui P，Lio P，et al.Crowcroft J．Towards real­time community detection in large networks.Physical Review E，2009，79(6)：066107.　
[25] Gregory S．Finding overlapping communities in networks by label propagation.New Journal of Physics，2010，12(10)：103018.
[26] Chen Z，Xie Z，Zhang Q．Community detection based on local topological information and its application in power grid.Neurocomputing，2015，170：384－392.
[27] Akcora C G，Carminati B，Ferrari E．User similarities on social networks.Social Network Analysis and Mining，2013，3(3)：475－495.
[28] van Dongen S．Graph clustering by flow simulation.Ph.D.Dissertation.Utrecht：Dutch National Research Institute for Mathematics and Computer Science，University of Utrecht，Netherlands，2000.
[29] Lai D R，Lu H T，et al.finding communities in directed networks by PageRank random walk induced network embedding.Physica A：Statistical Mechanics and Its Applications，2010，389(12)：2443－2454.
[30] Tonnies F，Loomis C P．Community and society: Gemeinschaft und Gesellschaft.New York：Dover Publications，1957，294.
[31] Radicchi F，Castellano C，Cecconi F，et al.Defining and identifying communities in networks.Proceedings of the National Academy of Sciences，2004(101)：2658－2663.
[32] Kannan R，Vempala S，Vetta A．On clusterings：Good，bad and spectral.Journal of the ACM，2004，51(3)：497－515.
[33] Demir G N，Uyar A S，Ögüdücü S G．Graph­based sequence clustering through multiobjective evolutionary algorithms for web recommender systems.In：Lipson H．Proceedings of 2007 Genetic and Evolutionary computation Conference(GTECCO2007)．New York，USA：ACM Press，2007，1943－1950.
[34] Fortunato S，Barthelemy M．Resolution limit in community detection.Proceedings of the National Academy of Sciences of the United States of America，2007，104(1)：36－41.
[35] Danon L，Díaz­Guilera A，Arenas A．Effect of size heterogeneity on community identification in complex networks.Journal of Statistical Mechanics：Theory and Experiment，2006，2006(11)：P11010.
[36] Nicosia V，Mangioni G，Carchiolo V，et al.Extending the definition of modularity to directed graphs with overlapping communities.Journal of Statistical Mechanics：Theory and Experiment，2009(3)：3166－3168.
[37] 郭世泽，陆哲明．复杂网络基础理论．北京：科学出版社，2012，340.
[38] Barabási A L，Albert R．Emergence of scaling in random networks.Science，1999，286(5439)：509.
[39] Watts D J，Strogatz S H．Collective dynamics of ‘small­world’ networks.Nature，1998：440－442.
[40] Kumpula J M，Kivelä M，Kaski K，et al.Sequential algorithm for fast clique percolation.Physical Review E：Statistical Nonlinear & Soft Matter Physics，2008，78(2)：026109.
[41] Chen Q，Wu T T，Fang M．Detecting local community structures in complex networks based on local degree central nodes.Physica A：Statistical Mechanics & Its Applications，2013，392(3)：529－537.
[42] 张泽华，苗夺谦，钱　进．邻域粗糙化的启发式重叠社区扩张方法．计算机学报，2013，36(10)：2078－2086.(Zhang Z H，Miao D Q，Qian J．Detecting overlapping communities with heuristic expansion method based on rough neighborhood.Chinese Journal of Computers，2013，36(10)：2078－2086.)
[43] Yang J，Leskovec J．Defining and evaluating network communities based on ground­truth.Knowledge and Information Systems，2015，42(1)：181－213.
[44] 潘　磊，金　杰，王崇骏等．社会网络中基于局部信息的边社区挖掘．电子学报，2012，40(11)：2255－2263.(Pan L，Jin J，Wang C J，et al.Detecting link communities based on local information in social networks.Acta Electronica Sinica，2012，40(11)：2255－2263.)
[45] Xie J，Szymanski B K，Liu X．SLPA：Uncovering overlapping communities in social networks via a speaker­listener interaction dynamic process.In：Proceedings of the International Conference on Data Mining Workshops.Vancouver，USA：IEEE，2011：344－349.
[46] Dai Q G，Guo M Z，Liu Y，et al.MLPA：Detecting overlapping communities by multi­label propagation approach.In：Proceedings of the IEEE Congress on Evolutionary Computation.Cancun，Mexico：IEEE，2013：681－688.
[47] Liu X，Murata T．Advanced modularity­specialized label propagation algorithm for detecting communities in networks.Physica A：Statistical Mechanics & Its Applications，2010，389(7)：1493－1500.
[48] 陈　晶，万　云．社交网络中基于模块度最大化的标签传播算法的研究．通信学报，2017，38(2)：25－33.(Chen J，Wan Y．Research on label propagation algorithm based on modularity maximization in the social network.Journal of Communications，2017，38(2)：25－33.)
[49] 刘世超，朱福喜，甘　琳．基于标签传播概率的重叠社区发现算法．计算机学报，2015，39(4)：717－729.(Liu S C，Zhu F X，Gan L．A Label­propagation­probability­based algorithm for overlapping community detection.Chinese Journal of Computers，2015，39(4)：717－729.)
[50] 刘冰玉，王翠荣，王　聪等．基于动态主题模型融合多维数据的微博社区发现算法．软件学报，2017，28(2)：246－261.(Liu B Y，Wang C R，Wang C，et al.Microblog community discovery algorithm based on dynamic topic model with multidimensional data fusion.Journal of Software，2017，28(2)：246－261.)
[51] Lü L，Zhou T．Link prediction in complex networks：A survey.Physica A：Statistical Mechanics & Its Applications，2010，390(6)：1150－1170.
[52] Lü L，Pan L，Zhou T，et al.Toward link predictability of complex networks.Proceedings of the National Academy of Sciences of the United States of America，2015，112(8)：2325－2330.
[53] Lü L，Chen D，Ren X L，et al.Vital nodes identification in complex networks.Physics Reports，2016：650.
[54] 柴变芳，贾彩燕，于　剑．基于概率模型的大规模网络结构发现方法．软件学报，2014，25(12)：2753－2766.(Chai B F，Jia C Y，Yu J．A label­propagation­probability­based algorithm for overlapping community detection.Journal of Software，2014，25(12)：2753－2766.)
[55] 康　颖，古晓艳，于　博等．一种面向大规模社会信息网络的多层社区发现算法．计算机学报，2016，39(1)：169－180.(Kang Y，Gu X Y，Yu B，et al.A Multilevel community detection algorithm for large scale social information networks.Chinese Journal of Computers，2016，39(1)：169－180.)
[56] Ge R，Ester M，Gao B J，et al.Joint cluster analysis of attribute data and relationship data：The connected k­center problem，algorithms and applications.ACM Transactions on Knowledge Discovery from Data，2008，2(2)7：1－35.
[57] Brigitte B，Stephan G，Holger H，et al.Mining coherent subgraphs in multi­layer graphs with edge labels.Knowledge & Information Systems，2012：1－30.
[58] Cheng H，Zhou Y，Yu J X．Clustering large attributed graphs：A balance between structural and attribute similarities.ACM Transactions on Knowledge Discovery from Data，2011，5(2)：12.
[59] Xu Z，Ke Y，Wang Y，et al.GBAGC：A general bayesian framework for attributed graph clustering.ACM Transactions on Knowledge Discovery from Data，2014，9(1)：1－43.
[60] Shi C，Li Y，Zhang J，et al.A Survey of heterogeneous information network analysis.IEEE Transactions on Knowledge & Data Engineering，2017，29(12)：87－99.
[61] Tang J，Lou T，Kleinberg J，et al.Transfer learning to infer social ties across heterogeneous networks.ACM Transactions on Information Systems，2016，34(2)：7.
[62] Liu D，Liu X，Wang W J，et al.Semi­supervised community detection based on discrete potential theory.Physica A：Statistical Mechanics and its Applications，2014，416：173－182.
[63] Yang L，Jin D，Wang X，et al.Active link selection for efficient semi­supervised community detection.Scientific Reports，2015，5：9039­1－9039­12.
[64] Wang M，Wang C，Yu J X，et al.Community detection in social networks：An in­depth benchmarking study with a procedure­oriented framework.Proceedings of the VLDB Endow­ment，2015，8(10)：998－1009.
[65] 陈俊宇，周　刚，南　煜．一种半监督的局部扩展式重叠社区发现方法．计算机研究与发展，2016，53(6)：1376－1388.(Chen J Y，Zhou G，Nan Y，et al.Semi­supervised local expansion method for overlapping community detection.Journal of Computer Research and Development，2016，53(6)：1376－1388.)
[66] Han X，Shen Z，Wang W X，et al.Robust reconstruction of complex networks from sparse data.Physical Review Letters，2015，114(2)：028701.　
[67] Radicchi F．Percolation in real interdependent networks.Nature Physics，2015，11(7)：597－602.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!

版权所有 © 2021 《南京大学学报(自然科学)》

地址：江苏省南京市鼓楼区汉口路22号，南京大学学报编辑部，210093

电话：025-83592704 , 传真：025-83592704        技术支持：北京玛格泰克科技发展有限公司