Phase transitions in semisupervised clustering of sparse networks

Abstract

Predicting labels of nodes in a network, such as community memberships or demographic variables, is an important problem with applications in social and biological networks. A recently-discovered phase transition puts fundamental limits on the accuracy of these predictions if we have access only to the network topology. However, if we know the correct labels of some fraction $\alpha$ of the nodes, we can do better. We study the phase diagram of this "semisupervised" learning problem for networks generated by the stochastic block model. We use the cavity method and the associated belief propagation algorithm to study what accuracy can be achieved as a function of $\alpha$. For $k=2$ groups, we find that the detectability transition disappears for any $\alpha >0$, in agreement with previous work. For larger $k$ where a hard but detectable regime exists, we find that the easy/hard transition (the point at which efficient algorithms can do better than chance) becomes a line of transitions where the accuracy jumps discontinuously at a critical value of $\alpha$. This line ends in a critical point with a second-order transition, beyond which the accuracy is a continuous function of $\alpha$. We demonstrate qualitatively similar transitions in two real-world networks.

References in corpus (8)

• Fast unfolding of communities in large networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Resolution limit in community detection
• Stochastic blockmodels and community structure in networks
• Phase transition in the detection of modules in sparse networks
• Comparative Study for Inference of Hidden Classes in Stochastic Block Models

Cited by in corpus (4)

• Social significance of community structure: Statistical view
• Detectability thresholds of general modular graphs
• Mutual Information in Community Detection with Covariate Information and Correlated Networks
• Semi-supervised learning in unbalanced and heterogeneous networks