Manifold Regularized Symmetric Joint Link Model For Overlapping Community Detection

Complex networks are a typical abstraction of networks in real world. In complex network, a vertex stands for an individual an edge stands for the interaction between individuals. Community structure exists in many real networks and finding them is of great significance to understand the world.Overlapping community detection is an important research topic in analyzing real-world networks and a lot of heuristic algorithms have been proposed. Although heuristic methods give some reasonable results in practice, they lack a strict mathematical significance and the ability to generate new links. Compared to heuristic methods, generative models are able to give a strict mathematical significance and offer natural probabilistic interpretations to overlapping belongings of each node. However, previous generative models assume that the community probability distribution generates data in the Euclidean space, without considering the case of manifold structure.To tackle this problem, we propose a Manifold Regularized Symmetric Joint Link Model (MSJL), which utilizes the local geometrical structure of manifold to improve the performance of overlapping community detection. MSJL assumes that the community probability distribution lives on a submanifold, and adopts the manifold assumption which specifically requires two close nodes in an intrinsic geometry to have similar community distribution. The structure of the intrinsic manifold is modeled by a nearest neighbor graph, and MSJL incorporates the graph Laplacian as a manifold regularization into the maximum likelihood function of the standard SJL model. Experiments on synthetic benchmarks and real-world networks have showed that MSJL can significantly improve the performance compared with the state-of-the-art methods.