JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2018, Vol. 53 ›› Issue (3): 24-29.doi: 10.6040/j.issn.1671-9352.1.2017.041

Previous Articles     Next Articles

Community detection algorithm based on effective resistance of network

ZHANG Jun1, LI Jing-fei2,4, ZHANG Rui1,3*, RUAN Xing-mao2, ZHANG Shuo2   

  1. 1. School of Computer Science and Technology, Hulunbuir College, Hulunbuir 021008, Inner Mongolia, China;
    2. School of Computer Science and Technology, Tianjin University, Tianjin 300350, China;
    3. College of Management and Economics, Tianjin University, Tianjin 300072, China;
    4. National Computer Network Emergency Response Technical Team/Coordination Center of China, Beijing 100029, China
  • Received:2017-09-19 Online:2018-03-20 Published:2018-03-13

PDF (PC)

597

Abstract: Community detection has a number of important applications in many areas. Inspired by the principle of effective resistance in traditional electrical circuit, we propose a novel community detection algorithm which can discover communities by iteratively calling the edge-cutting selection model based on the total effective resistance of a network. In each iteration, the edge-cutting selection model cuts an appropriate number of edges in order to maximize the total effective resistance of the updated network. Theoretical analysis shows that our algorithm has relatively low algorithm complexity degree. Extensive empirical experiments have been conducted on simulated and real complex networks, the results show that the proposed algorithm has good performance.

Key words: heuristic, community detection, maximization, effective resistance

CLC Number: 

  • TP391
[1] VU T T, SONG Dawei, WILLIS A, et al. Improving search personalisation with dynamic group formation[C] // Proceedings of the International ACM SIGIR Conference. New York: ACM, 2014: 951-954.
[2] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2004, 69(2):026113.
[3] CLAUSET A, NEWMAN M E, MOORE C. Finding community structure in very large networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2004, 70(6 Pt 2):066111. DOI: 10.1103/PhysRevE.70.066111.
[4] CHOUDHURY D, BHATTACHARJEE S, DAS A. An empirical study of community and sub-community detection in social networks applying Newman-Girvan algorithm[C] // International Conference on Emerging Trends and Applications in Computer Science. New York: IEEE, 2013: 74-77.
[5] ZHU Xiaohu, SONG Wenjun, WANG Chongjun, et al. Improved algorithm based on girvan-newman algorithm for community detection[J]. Journal of Frontiers of Computer Science & Technology, 2010, 4(12):1101-1108.
[6] GHOSH A, BOYD S, SABERI A. Minimizing effective resistance of a graph[J]. Siam Review, 2008, 50(1):37-66.
[7] LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2008, 78(2):046110.
[8] ZACHARY W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33(4):452-473.
[9] YIP K Y, CHEUNG D W, NG M K. HARP: a practical projected clustering algorithm[J]. IEEE Transactions on Knowledge & Data Engineering, 2004, 16(11):1387-1397.
[1] 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.
[2] ZHANG Peng, WANG Su-ge, LI De-yu, WANG Jie. A semi-supervised spam review classification method based on heuristic rules [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(7): 44-51.
[3] XU Bing, ZHANG Yang. Research on totally sequential decision-model of two firms location and pricing based on Hotelling model [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(6): 1-9.
[4] WANG Qian, XU Ru-zhi, YANG Feng. TCP rate control in wireless mutiple-hop networks by  cross-layer optimization for QoS provisioning [J]. J4, 2012, 47(3): 61-66.
[5] WANG Gang, XU Xin-shun*. A new Multi-instance learning method for scene classification [J]. J4, 2010, 45(7): 108-113.
[6] WANG Kang, LI Hua. Analysis of the compound Haqing injection with hyphenated chromatography and chemometric resolution [J]. J4, 2009, 44(11): 16-20.
[7] ZHAO Pei-xin,MA Jian-hua and WANG Hong, . Lagrange relaxation heuristic algorithm for stochastic loader problem [J]. J4, 2006, 41(1): 106-110 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd