南京大学学报(自然科学版) ›› 2018, Vol. 54 ›› Issue (4): 696.
钱 峰1,2,张 蕾1,2,赵 姝1*,陈 洁1,张燕平1
Qian Feng1,2,Zhang Lei1,2,Zhao Shu1*,Chen Jie1,Zhang Yanping1
摘要: 社团发现常用于挖掘复杂网络中的隐藏信息,如功能模块和拓扑结构. 为提高复杂网络中社团结构挖掘的质量,提出一种基于加权树的层次社团划分算法HCD_WTree(Hierarchical Community Detection Algorithm Based on Weighted Tree). 首先,结合邻域重叠比和节点的度中心性来度量节点间关系强度,基于该度量将原无权网络转换成加权网络;接着,对网络进行简化,得到加权树;最后,基于层次社团挖掘方法,根据边权依序裁剪加权树,得到层次的社团结构,并结合模块度函数获得最优的社团划分结果. 在公用数据集上的实验结果表明,与现有的社团挖掘技术相比,HCD_WTree算法能够更准确地划分复杂网络中的社团结构.
[1] Lancichinetti A,Kivel M,Saramki 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. |
No related articles found! |
|