A modularity-maximization-based approach for detecting multi-communities in social networks

Chen-Kun Tsung (), Sing-Ling Lee (), Hann-Jang Ho () and ShengKai Chou ()
Additional contact information
Chen-Kun Tsung: National Chin-Yi University of Technology
Sing-Ling Lee: National Chung Cheng University
Hann-Jang Ho: WuFeng University
ShengKai Chou: National Chung Cheng University

Annals of Operations Research, 2021, vol. 303, issue 1, No 17, 411 pages

Abstract: Abstract The modularity is a widely-used objective function to determine communities from a given network. The leading eigenvector method is a popular solution that applies the first eigenvector to determine the communities. The low computation cost is the major advantage of the leading eigenvector method. However, the leading eigenvector method only can split a network into two communities. To detect multiple communities, the modularity maximization is transformed to the vector partition problem (VPP). We propose an algorithm which is called as the partition at polar coordinate protocol (PPCP) to solve the VPP problem. The goal of PPCP is to find non-overlapping vertex vector sets so as to maximize the quadratic sum of the norms of community vectors. The proposed PPCP has two steps to determine the communities that are the network structure analysis and the community determination. During the network structure analysis, we obtain following issues. First, the vertex vectors belong to different communities can be separated by the distribution angles. Second, a node with a higher degree corresponds to a vertex vector with a larger norm. So, we propose three refinement functions including the noise reduction, the common-friends model and the strong connectivity hypothesis to improve the accuracy of PPCP. In our simulations, PPCP detects communities more precisely than Fine-tuned algorithm especially in the network with the weak structure. Moreover, the proposed refinement functions can capture the special properties of the network. So, PPCP with refinement functions performs much better than Fine-tuned algorithm and PPCP without refinement functions in terms of the accuracy in detecting communities.

Keywords: Modularity maximization; Community detection; Spectral clustering (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-018-3120-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:annopr:v:303:y:2021:i:1:d:10.1007_s10479-018-3120-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-018-3120-8

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().