APPLICATION OF CUT ALGORITHM BASED ON ALGEBRAIC CONNECTIVITY TO COMMUNITY DETECTION

作者：Zhao, Fuqiang^*; Zhang, Lichao; Yang, Guijun; He, Li; Yan, Fengyu

来源：Advances in Complex Systems, 2017, 20(1): 1750002.

DOI：10.1142/S0219525917500023

• Algebraic connectivity
• Laplacian matrix
• cut edge
• upper and lower bounds

In the graph of a complex network, the algebraic connectivity is the second smallest eigenvalue of a Laplacian matrix. In this paper, we present a cut algorithm based on edge centrality by minimizing the algebraic connectivity of graph. The edge centrality cut algorithm (ECCA) cuts k edges at a time in order to reduce temporal complexity, the algebraic connectivity of which experiences the fastest decline. To prevent nodes from overcutting, each edge sets the weight. We use the advanced ECCA (AECCA) to detect overlapping communities by calculating the correlation coefficients of the nodes. This paper also proposes upper, lower and weaker lower bounds of algebraic connectivity. We demonstrate that our algorithms are effective and accurate at discovering community structure in both artificial and real-world network data and that the algebraic connectivity of the cut algorithm lies between the upper and lower bounds. Our algorithms offer new insights into community detection by calculating the edge centrality.

• 出版日期2017-2
• 单位天津财经大学