Exhaustive Exploitation of Local Seeding Algorithms for Community Detection in a Unified Manner

Yanmei Hu (), Bo Yang, Bin Duo and Xing Zhu
Additional contact information
Yanmei Hu: College of Computer Science and Cyber Security, Chengdu University of Technology, Chengdu 610059, China
Bo Yang: School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China
Bin Duo: College of Computer Science and Cyber Security, Chengdu University of Technology, Chengdu 610059, China
Xing Zhu: College of Computer Science and Cyber Security, Chengdu University of Technology, Chengdu 610059, China

Mathematics, 2022, vol. 10, issue 15, 1-30

Abstract: Community detection is an essential task in network analysis and is challenging due to the rapid growth of network scales. Recently, discovering communities from the local perspective of some specified nodes called seeds, rather than requiring the global information of the entire network, has become an alternative approach to addressing this challenge. Some seeding algorithms have been proposed in the literature for finding seeds, but many of them require an excessive amount of effort because of the global information or intensive computation involved. In our study, we formally summarize a unified framework for local seeding by considering only the local information of each node. In particular, both popular local seeding algorithms and new ones are instantiated from this unified framework by adopting different centrality metrics. We categorize these local seeding algorithms into three classes and compare them experimentally on a number of networks. The experiments demonstrate that the degree-based algorithms usually select the fewest seeds, while the denseness-based algorithms, except the one with node mass as the centrality metric, select the most seeds; using the conductance of the egonet as the centrality metric performs best in discovering communities with good quality; the core-based algorithms perform best overall considering all the evaluation metrics; and among the core-based algorithms, the one with the Jaccard index works best. The experimental results also reveal that all the seeding algorithms perform poorly in large networks, which indicates that discovering communities in large networks is still an open problem that urgently needs to be addressed.

Keywords: seeding; community detection; node centrality; seed expansion (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/15/2807/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/15/2807/ (text/html)

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:gam:jmathe:v:10:y:2022:i:15:p:2807-:d:882781

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().