Self-Guided Community Detection on Networks with Missing Edges

Self-Guided Community Detection on Networks with Missing Edges

Dongxiao He, Shuai Li, Di Jin, Pengfei Jiao, Yuxiao Huang

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence
Main Track. Pages 3508-3514. https://doi.org/10.24963/ijcai.2021/483

The vast majority of community detection algorithms assume that the networks are totally observed. However, in reality many networks cannot be fully observed. On such network is edges-missing network, where some relationships (edges) between two entities are missing. Recently, several works have been proposed to solve this problem by combining link prediction and community detection in a two-stage method or in a unified framework. However, the goal of link prediction, which is to predict as many correct edges as possible, is not consistent with the requirement for predicting the important edges for discovering community structure on edges-missing networks. Thus, combining link prediction and community detection cannot work very well in terms of detecting community structure for edges-missing network. In this paper, we propose a community self-guided generative model which jointly completes the edges-missing network and identifies communities. In our new model, completing missing edges and identifying communities are not isolated but closely intertwined. Furthermore, we developed an effective model inference method that combines a nested Expectation-Maximization (EM) algorithm and Metropolis-Hastings Sampling. Extensive experiments on real-world edges-missing networks show that our model can effectively detect community structures while completing missing edges.
Keywords:
Machine Learning Applications: Networks
Uncertainty in AI: Graphical Models
Data Mining: Mining Graphs, Semi Structured Data, Complex Data