Abstract：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.
