APPLICATION OF CUT ALGORITHM BASED ON ALGEBRAIC CONNECTIVITY TO COMMUNITY DETECTION.

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 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. [ABSTRACT FROM AUTHOR]