APPLICATION OF CUT ALGORITHM BASED ON ALGEBRAIC CONNECTIVITY TO COMMUNITY DETECTION

Fuqiang Zhao, Lichao Zhang, Guijun Yang, Li He and Fengyu Yan
Additional contact information
Fuqiang Zhao: Department of Information Science and Technology, Tianjin University of Finance and Economics, Tianjin 300222, P. R. China
Lichao Zhang: Department of Information Science and Technology, Tianjin University of Finance and Economics, Tianjin 300222, P. R. China
Guijun Yang: #x2020;Department of Statistics, Tianjin University of Finance and Economics, Tianjin 300222, P. R. China
Li He: Department of Information Science and Technology, Tianjin University of Finance and Economics, Tianjin 300222, P. R. China
Fengyu Yan: Department of Information Science and Technology, Tianjin University of Finance and Economics, Tianjin 300222, P. R. China

Advances in Complex Systems (ACS), 2017, vol. 20, issue 01, 1-18

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

Keywords: Algebraic connectivity; Laplacian matrix; cut edge; upper and lower bounds (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0219525917500023
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:acsxxx:v:20:y:2017:i:01:n:s0219525917500023

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0219525917500023

Access Statistics for this article

Advances in Complex Systems (ACS) is currently edited by Frank Schweitzer

More articles in Advances in Complex Systems (ACS) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().