基于加权树的层次社团划分算法

南京大学学报(自然科学版) ›› 2018, Vol. 54 ›› Issue (4): 696–.

基于加权树的层次社团划分算法

钱　峰1，2，张　蕾1，2，赵　姝1*，陈　洁1，张燕平1

出版日期:2018-04-30
作者简介:1.安徽大学计算机科学与技术学院，合肥，230601；2.铜陵学院数学与计算机学院，铜陵，244061
基金资助:
基金项目：国家重点研发计划(2017YFB1401903)，国家自然科学基金(61402006，61602003，61673020)，国防科技创新特区项目(2017－0001－863015－0009)，安徽省自然科学基金(1508085MF113，1708085QF156)，教育部留学回国人员科研启动基金(第49批) 收稿日期：2018－05－08 *通讯联系人，E－mail：zhaoshuzs2002@hotmail.com

Hierarchical community detection algorithm based on weighted tree

Qian Feng1，2，Zhang Lei1，2，Zhao Shu1*，Chen Jie1，Zhang Yanping1

Online:2018-04-30
About author:1.School of Computer Science and Technology，Anhui University，Hefei，230601，China； 2．School of Mathematics and Computers，Tongling University，Tongling，244061，China

摘要/Abstract

摘要： 社团发现常用于挖掘复杂网络中的隐藏信息，如功能模块和拓扑结构. 为提高复杂网络中社团结构挖掘的质量，提出一种基于加权树的层次社团划分算法HCD_WTree(Hierarchical Community Detection Algorithm Based on Weighted Tree). 首先，结合邻域重叠比和节点的度中心性来度量节点间关系强度，基于该度量将原无权网络转换成加权网络；接着，对网络进行简化，得到加权树；最后，基于层次社团挖掘方法，根据边权依序裁剪加权树，得到层次的社团结构，并结合模块度函数获得最优的社团划分结果. 在公用数据集上的实验结果表明，与现有的社团挖掘技术相比，HCD_WTree算法能够更准确地划分复杂网络中的社团结构．

Abstract: Complex network is widely used to describe a complex system. The nodes and edges in a network represent entities and relationships between the entities respectively. Community structure is the most basic and important topological characteristic of complex network. Community detection is significant to its character statistics. In order to improve the quality of the community structure in complex networks，an algorithm named Hierarchical Community Detection Algorithm Based on Weighted Tree(HCD_WTree algorithm)is proposed in this paper. Firstly，based on the definition of Neighborhood Overlap，a new measurement is given to measure the relationship strength of neighbor nodes by introducing the degree centrality of nodes. Secondly，the strength of the relations(edges)in the network is calculated according to the new measurement so that the original unweighted network is transformed into a weighted network. Kruskal algorithm is used to build a weighted tree for the weighted network. This not only improves the efficiency of the algorithm，but also makes it more intuitive to observe the evolution of the community structure. Thirdly，based on hierarchical community detection method，using split operation，according to the weight of the edges，from small to large to cut the weighted tree step by step，the community structure of levels is obtained and in conjunction with the modularity function，the best result of division is obtained. The experimental results on public datasets show that the proposed algorithm HCD_WTree can find the community structure more accurately and effectively.

钱　峰1，2，张　蕾1，2，赵　姝1*，陈　洁1，张燕平1. 基于加权树的层次社团划分算法[J]. 南京大学学报(自然科学版), 2018, 54(4): 696–.

Qian Feng1，2，Zhang Lei1，2，Zhao Shu1*，Chen Jie1，Zhang Yanping1. Hierarchical community detection algorithm based on weighted tree[J]. Journal of Nanjing University(Natural Sciences), 2018, 54(4): 696–.

参考文献

[1]　Lancichinetti A，Kivel M，Saramki J，et al. Characterizing the community structure of complex networks. PLOS One，2010，5(8)：e11976.　 [2] 张泽华，段力畑，段　富等. 基于局部结构特征的重叠社区挖掘研究进展. 南京大学学报(自然科学)，2017，53(3)：537－548.(Zhang Z H，Duan L T，Duan F，et al. Research progress of overlapping community detection methods based on local structure. Journal of Nanjing University(Natural Science)，2017，53(3)：537－548.) [3] Newman M E J，Girvan M. Finding and evaluating community structure in networks. Physical Review E：Statistical，Nonlinear，and Soft Matter Physics，2004，69(2 Pt 2)：026113. [4] Newman M E J. Fast algorithm for detecting community structure in networks. Physical Review E：Statistical，Nonlinear，and Soft Matter Physics，2003，69(6 Pt 2)：066133. [5] Clauset A，Newman M E J，Moore C，et al. Finding community structure in very large networks. Physical Review E：Statistical，Nonlinear，and Soft Matter Physics，2004，70(6)：066111.　 [6] Blondel V D，Guillaume J L，Lambiotte R，et al. Fast unfolding of communities in large networks. Journal of Statistical Mechanics：Theory and Experiment，2008，2008(10)：P10008. [7] 赵　姝，柯　望，陈　洁等. 基于聚类粒化的社团发现算法. 计算机应用，2014，34(10)：2812－2815.(Zhao S，Ke W，Chen J，et al. Community detection algorithm based on clustering granulation. Journal of Computer Applications，2014，34(10)：2812－2815.) [8] Reihaneh R K，Chen J Y，Osmar R Z. Top leaders community detection approach in information networks ∥ Proceedings of the 4th SNA－KDD Workshop on Social Networks Mining and Analysis. Washington DC，USA：ACM，2010：2319－7323. [9] 刘井莲，王大玲，赵卫绩等. 一种面向度中心性及重叠网络社区的发现算法. 计算机科学，2016，43(3)：33－37，71.(Liu J L，Wang D L，Zhao W J，et al. Algorithm for discovering network community with centrality and overlap. Computer Science，2016，43(3)：33－37，71.) [10] Kumar P，Gupta S，Bhasker B. An upper approximation based community detection algorithm for complex networks. Decision Support Systems，2017，96：103－118. [11] Wang T，Yin L Y，Wang X X. A community detection method based on local similarity and degree clustering information. Physica A：Statistical Mechanics and its Applications，2018，490：1344－1354. [12] Eustace J，Wang X Y，Cui Y Z. Community detection using local neighborhood in complex networks. Physica A：Statistical Mechanics and its Applications，2015，436：665－677. [13] Saoud B，Moussaoui A. Node similarity and modularity for finding communities in networks. Physica A：Statistical Mechanics and its Applications，2018，492：1958－1966. [14] Granovetter M. The strength of weak ties：A network theory revisited. Sociological Theory，1983，1：201－233. [15] Granovetter M. Economic action and social structure：The problem of embeddedness. American Journal of Sociology，1985，91(3)：481－510. [16] de Meo P，Ferrara E，Fiumara G，et al. On Facebook，most ties are weak. Communications of the ACM，2014，57(11)：78－84. [17] Zachary W W. An information flow model for conflict and fission in small groups. Journal of Anthropological Research，1977，33(4)：452－473.　 [18] Lusseau D，Schneider K，Boisseau O J，et al. The bottlenose dolphin community of doubtful sound features a large proportion of long－lasting associations. Behavioral Ecology and Sociobiology，2003，54(4)：396－405. [19] Adamic L A，Glance N. The political blogosphere and the 2004 U. S. election：Divided they blog ∥ Proceedings of the 3rd International Workshop on Link Discovery. Chicago，IL，USA：ACM Press，2005：36－43. [20] Girvan M，Newman M E J. Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America，2002，99(12)：7821－7826. [21] Watts D J，Strogatz S H. Collective dynamics of ‘small－world’ networks. Nature，1998，393(6684)：440－442. [22] Xie J R，Szymanski B K，Liu X M. SLPA：Uncovering overlapping communities in social networks via a speaker－listener interaction dynamic process ∥ Proceedings of the 11th IEEE International Conference on Data Mining Workshops. Vancouver，Canada：IEEE Computer Society，2011：344－349. [23] Lancichinetti A，Fortunato S，Radicchi F. Benchmark graphs for testing community detection algorithms. Physical Review E：Statistical，Nonlinear，and Soft Matter Physics，2008，78(4 Pt 2)：046110. [24] Danon L，Díaz－Guilera A，Duch J，et al. Comparing community structure identification. Journal of Statistical Mechanics：Theory and Experiment，2005，2005(9)：P09008.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed