JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2018, Vol. 53 ›› Issue (11): 67-77.doi: 10.6040/j.issn.1671-9352.1.2017.023

Previous Articles     Next Articles

Important-node-based community detection algorithm

WANG Xin1,2, ZUO Wan-li2,3, ZHU Feng-tong3, WANG Ying2,3*   

  1. 1. School of Computer Technology and Engineering, Changchun Institute of Technology, Changchun 130012, Jilin, China;
    2. Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, Jilin, China;
    3. College of Computer Science and Technology, Jilin University, Changchun 130012, Jilin, China
  • Published:2018-11-14
  • About author:国家自然科学基金资助项目(61602057);教育部重点实验室开放基金资助项目(93K172016K13);吉林省科技厅优秀青年人才基金项目(20170520059JH);广西可信软件重点实验室研究课题项目(kx201533);中国博士后基金面上项目(2017M611301)
  • Supported by:
    国家自然科学基金资助项目(61602057);教育部重点实验室开放基金资助项目(93K172016K13);吉林省科技厅优秀青年人才基金项目(20170520059JH);广西可信软件重点实验室研究课题项目(kx201533);中国博士后基金面上项目(2017M611301)

PDF (PC)

682

Abstract: The internal community structure is the specific expression of structural features and attribute features in complex networks. First, the maximum k eigenvectors matrix of the modularity matrix of the network was calculated based on the modularity maximization theory. Then, the method of cluster centrality was proposed and used to calculate the important nodes of the k communities as k cluster centralities. The distance between each node and k cluster centralities was calculate by Euclidean distance and each node was assigned to the nearest cluster centrality of the community. Final, k-means iterative calculation method was applied into the network and the k communities divisions was eventually obtained. The algorithm was verified experimentally on both Karate Club Network dataset and American College Football dataset. The experimental results show that the algorithm can effectively identify potential community. The algorithm improves the purity and modularity to a certain extent compared with other community detection algorithms, and with fewer iterations and higher efficiency.

Key words: complex network, community similarity, k-means algorithm, community detection

CLC Number: 

  • TP391
[1] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Phys Rev E, 2004, 69(6):066133. Doi:10.1103/PhysRevE.69.060133.
[2] SHEN H W, CHENG X Q. Spectral methods for the detection of network community structure: a comparative analysis[J]. Journal of Statistical Mechanics Theory & Experiment, 2010, 2010(10):10020.
[3] WANG T S, LIN H T, WANG P. Weighted-spectral clustering algorithm for detecting community structures in complex networks[J]. Artificial Intelligence Review, 2017, 47(4):463-483.
[4] CLAUSET A, NEWMAN M E J, MOORE C. Finding community structure in very large networks[J]. Phys Rev E, 2004, 70(6):066111.
[5] WAKITA K, TSURUMI T. Finding community structure in mega-scale social networks[C] // Proceedings of the 16th International Conference on World Wide Web(WWW 2007). 2007:1275-1276. ArXiv: cs/0702048.
[6] KIRKPATRICK S, GELATT C D, VECCHI M P. Optimization by simulated annealing[J]. Science, 1983, 220(4598):671-680.
[7] GUIMERÀ R, SALES-PARDO M, AMARAL L A N. Modularity from fluctuations in random graphs and complex networks[J]. Phys Rev E, 2004, 70(2):025101. Doi:10.1103/PhysRevE.70.025/01.
[8] GUIMERÀ R, AMARAL L A N. Functional cartography of complex metabolic networks[J]. Nature, 2005, 433(7028):895-900.
[9] BOETTCHER S, PERCUS A G. Optimization with extremal dynamics[J]. Phys Rev Lett, 2001, 86(23):5211-5214.
[10] DUCH J, ARENAS A. Community detection in complex networks using extremal optimization[J]. Phys Rev E, 2005, 72(2):027104. Doi:10.1103/PhysRevE.72.027104.
[11] LI Z P, ZHANG S H, WANG R S, et al. Quantitative function for community detection[J]. Physical Review E, 2008, 77(3):036109. Doi:10.1103/PhysRevE.77.036109.
[12] WANG G X, SHEN Y, OUYANG M. A vector partitioning approach to detecting community structure in complex networks[J]. Computer & Mathematics with Applications, 2008, 55(12):2746-2752.
[13] WANG X, QIAN B, DAVIDSON I. On constrained spectral clustering and its applications[J]. Data Mining and Knowledge Discovery, 2014, 28(1):1-30.
[14] BARNES E R. An algorithm for partitioning the nodes of a graph[C] // Proceedings of the 20th IEEE Conference on Decision and Control Including the Symposium on Adaptive Processes. New York: IEEE, 1981: 303-304.
[15] GOLUB G H, LOAN C F V. Matrix computations[M]. Baltimore: John Hopkins University Press, 1989.
[16] MA X K, GAO L, XUERONG Y, et al. Semi-supervised clustering algorithm for community structure detection in complex networks[J]. Physica A, 2010, 389(1):187-197.
[17] FU L D, GAO L. An eigenvector-based kernel clustering approach to detecting communities in complex networks[C] // Proceeding of the 1st IRAST International Conference on Data Engineering and Internet Technology. Berlin: Springer-Verlag, 2013, 156:23-28.
[18] NEWMAN M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E, 2006, 74(3):036104. Doi:10.1103/PhysRevE.74.036104.
[19] KHORASGANI R R, CHEN J, ZAÏANE O R. Top leaders community detection approach in information networks[C] // Proceedings of the 2010 International Conference on Knowledge Discovery and Data Mining(KDD10). New York: ACM, 2010: 1-9.
[20] ADAMCSEK B, PALLA G, FARKAS I J, et al. CFinder: locating cliques and overlapping modules in biological networks[J]. Bioinformatics, 2006, 22(8):1021-1023.
[21] ZACHARY W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1997, 33(4):452-473.
[1] ZHANG Jun, LI Jing-fei, ZHANG Rui, RUAN Xing-mao, ZHANG Shuo. Community detection algorithm based on effective resistance of network [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(3): 24-29.
[2] WEI Si-min, ZHANG Xian-hua, ZHANG Zhen, MENG Qing-chun, ZHANG Xia-ran. Virtual brand community opinion leader recognition based on complex network——example of the Meizu Flyme community [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(11): 26-34.
[3] SUI Yun-xian, LIU Yong. Mining algorithm of E-burt structural hole based on two-step neighbor [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(9): 59-68.
[4] SUN Song-tao, HE Yan-xiang, CAI Rui, LI Fei, HE Fei-yan. Comparative study of methods for Micro-blog sentiment evaluation tasks [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(11): 43-50.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] SHAO Yong. Semilattice-ordered completely regular periodic semigroups[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 1 -5 .
[2] GONG Zeng-tai, GAO Han. Preinvexity of n-dimensional fuzzy number-valued functions[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 72 -81 .
[3] CHEN Wen-qian, ZHANG Xiao-jin, ZAN Li-bo. The number of tilting modules over Gorenstein algebras[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 14 -16 .
[4] GUO Shou-tao, WANG Zhan-ping. Gorenstein homological dimensions of modules under exact zero-divisors[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 17 -21 .
[5] WU Xiao-ying, WANG Fang-gui. Graded version of Enochs theorem[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 22 -26 .
[6] LI Mei-lian, DENG Qing-ying. Maple calculation of the transition polynomial of plane graph[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 27 -34 .
[7] WANG Dan, WANG Zheng-pan. Characterizing a band variety in terms of forbidden subsemigroups[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 6 -8 .
[8] LIANG Xing-liang, WU Su-peng, REN Jun. Characterization of monoids by C(P')acts[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 9 -13 .
[9] FANG Qi-ming, ZHANG Li. k-frugal list coloring of planar graphs without 4 and 5-cycles[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 35 -41 .
[10] ZHEN Wei-wei, ZENG Jian, REN Jian-long. Time dependent parabolic inverse source problem based on variational theory[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 61 -71 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd