Community Detection in Partially Observable Social Networks
- 21 July 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Knowledge Discovery From Data
- Vol. 16 (2), 1-24
- https://doi.org/10.1145/3461339
Abstract
The discovery of community structures in social networks has gained significant attention since it is a fundamental problem in understanding the networks’ topology and functions. However, most social network data are collected from partially observable networks with both missing nodes and edges. In this article, we address a new problem of detecting overlapping community structures in the context of such an incomplete network, where communities in the network are allowed to overlap since nodes belong to multiple communities at once. To solve this problem, we introduce KroMFac, a new framework that conducts community detection via regularized nonnegative matrix factorization (NMF) based on the Kronecker graph model. Specifically, from an inferred Kronecker generative parameter matrix, we first estimate the missing part of the network. As our major contribution to the proposed framework, to improve community detection accuracy, we then characterize and select influential nodes (which tend to have high degrees) by ranking, and add them to the existing graph. Finally, we uncover the community structures by solving the regularized NMF-aided optimization problem in terms of maximizing the likelihood of the underlying graph. Furthermore, adopting normalized mutual information (NMI), we empirically show superiority of our KroMFac approach over two baseline schemes by using both synthetic and real-world networks.Keywords
Funding Information
- National Research Foundation of Korea
- Korea government (2021R1A2C3004345)
- Korea Health Technology R&D Project through the Korea Health Industry Development Institute
- Ministry of Health & Welfare
- Republic of Korea (HI20C0127)
- Yonsei University Research Fund of 2021 (2021-22-0083)
This publication has 47 references indexed in Scilit:
- Overlapping community detection in networksACM Computing Surveys, 2013
- DebtRank-transparency: Controlling systemic risk in financial networksScientific Reports, 2013
- Finding missing edges and communities in incomplete networksJournal of Physics A: Mathematical and Theoretical, 2011
- Community detection in Social MediaData Mining and Knowledge Discovery, 2011
- Finding overlapping communities in networks by label propagationNew Journal of Physics, 2010
- How Many People Do You Know?: Efficiently Estimating Personal Network SizeJournal of the American Statistical Association, 2010
- Community detection in graphsPhysics Reports, 2009
- Towards real-time community detection in large networksPhysical Review E, 2009
- Near linear time algorithm to detect community structures in large-scale networksPhysical Review E, 2007
- Modularity and community structure in networksProceedings of the National Academy of Sciences of the United States of America, 2006