  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 paper, 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.
