Community detection with realistic network models: a superimposed SBM and a hyperbolic space model

Subhadeep Paul (November 9, 2018)

Please install the Flash Plugin

Abstract

Detecting communities or a group of vertices that are similar to each other in a complex network is a well-studied problem in network science. Methods for community detection include model-based approaches, namely, based on the stochastic block model and its variants, latent space models, as well as model-free approaches including spectral, modularity and matrix factorization methods. The stochastic block model is the most commonly employed model of complex networks with community structure. However, the model fails to explain many observed properties of networks including, heterogeneous and power-law degree distribution (scale-free), strong local clustering especially triadic closures (transitivity) in an otherwise sparse graph, hierarchical nature of connections (core-periphery structure). The goals of this project are to develop models for networks with community structure that explain observed properties of real-world networks better. We propose a superimposed stochastic block model (SupSBM) and a hyperbolic latent space network community model (Hypcomm) for this purpose. We analyze the performance of a higher-order spectral clustering algorithm under the SupSBM. We also develop computationally efficient Variational EM, and Laplacian spectral embedding algorithms to estimate the latent positions and the communities in the Hypcomm model.