针对现有的社团划分算法过分粒度化和基于模块度优化存在的局限性,本文引入万有引力的思想,假设社团是由节点之间存在虚拟力牵引聚集而成,提出了一种基于虚拟力作用的社团划分算法。在已知社团结构的真实网络中与GN算法、CNM算法等经典算法对比测试,发现本算法不仅能够给出更加准确的网络的社团结构,还具有较高可靠性和接近线性的时间复杂度。
In view of the existing community partition algorithms too granular and the limitation of optimization based on the modularity,this paper proposes a community partition algorithm based on gravity,which the relation between the adjacent vertices is considered as attraction while the relation between the non-adjacent vertices is repulsion. The community structure is formed by the self-organization of vertices which are influenced by the virtual force from their neighbors. Compared with GN and CNM algorithm in the reality of the network which known community structure,the algorithm in this paper has high reliability and nearly linear time complexity.
[1] 汪小帆, 李翔, 陈关荣. 复杂网络理论及其应用[M]. 北京:清华大学出版社, 2006: 162-193.
[2] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(6): 7821-7826.
[3] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(6): 026113.
[4] Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6): 066133.
[5] Clauset A. Finding Local Community Structure in Networks[J].Phys Rev E, 2005, 72(2): 026132
[6] Fortunato S, Barthélemy M. Resolution limit in community detection[J]. Proceedings of the National Academy of Sciences, 2007, 104(1): 36-41.
[7] Palla G, Derenyi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814-818.
[8] Ahn Y Y, Bagrow J P, Lehmann S. Link Communities RevealMultiscale Complexity in Networks[J]. Nature, 2010, 466(7307): 761-764.
[9] 顾亦然, 戴晓罡. 基于虚拟力牵引的社团划分算法[J]. 南京邮电大学学报:自然科学版, 2013, 33(6): 106-111.
Gu Yiran, Dai Xiaogang. Community partitioning algorithm based on virtual force[J]. Journal of Nanjing University of Posts and Telecommunications(Natural Science), 2013, 33(6): 106-111.
[10] 高自友, 赵小梅, 黄海军, 等. 复杂网络理论与城市交通系统复杂性问题的相关研[J]. 交通运输系统工程与信息, 2006, 3(4): 41-47.
Gao Ziyou, Zhao Xizomei, Huang Haijun, et al. Research on problems related to complex networks and urban traffic systems[J]. Journal of Transportation Systems Engineering and Information Technology, 2006, 3(4): 41-47.
[11] Karemera D, Oguledo VI, Davis B. A gravity model analysis of international migration to north America[J]. Appl Econ, 2000, 32(13): 1745-1755.
[12] Rose A K. Do we really know that thewto increases trade[J]. Am Econ Rev, 2004, 94(21): 98-114.
[13] Jung W S, Wang F, Stanley H E. Gravity model in the Korean highway[J]. EPL, 2008, 81(4): 48005.
[14] Backstrom L, Boldi P, Rosa M, et al. Four degrees of separation[C]//Proceedings of the 3rd Annual ACM Web Science Conference. New York USA:NY: 2012: 33-42.
[15] Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33(4):452-473.
[16] Kernighan B, Lin S. An efflicient heuristic procedure for partitioning graphs[J]. Bell system technical journal, 1970, 49(2): 291-307.
[17] Kitsak M, Gallos L K, Havlin S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6(11): 888-893.
[18] Bagrow J P, Bollt E M. Local method for detecting communities[J]. Physical Review E, 2005, 72(4): 046108.
[19] Lusseau D, Schneider K, Boisseau O J, et al. The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations[J]. Behavioral Ecology and Sociobiology, 2003, 54(4): 396-405.
[20] 马海波, 陈时勇. 基于网页等级的PageRank算法改进[J]. 大连交通大学学报, 2010, 31(2): 78-81.
Ma Haibo, Chen Shiyong. PageRank algorithm improvements based on page-level[J]. Journal of Dalian Jiaotong University, 2010, 31(2): 78-81.
