Community detection in networks with unequal groups

Abstract

Recently, a phase transition has been discovered in the network community detection problem below which no algorithm can tell which nodes belong to which communities with success any better than a random guess. This result has, however, so far been limited to the case where the communities have the same size or the same average degree. Here we consider the case where the sizes or average degrees are different. This asymmetry allows us to assign nodes to communities with better-than- random success by examining their local neighborhoods. Using the cavity method, we show that this removes the detectability transition completely for networks with four groups or fewer, while for more than four groups the transition persists up to a critical amount of asymmetry but not beyond. The critical point in the latter case coincides with the point at which local information percolates, causing a global transition from a less-accurate solution to a more-accurate one.

References in corpus (6)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Phase transition in the detection of modules in sparse networks
• Identification of core-periphery structure in networks
• Generalized communities in networks
• (Un)detectable cluster structure in sparse networks
• Phase transitions in semisupervised clustering of sparse networks

Cited by in corpus (12)

• Community detection in networks: A user guide
• Statistical physics of inference: Thresholds and algorithms
• Block Models and Personalized PageRank
• Typology of phase transitions in Bayesian inference problems
• Information-theoretic thresholds for community detection in sparse networks
• Revealing consensus and dissensus between network partitions
• Information-theoretic thresholds for community detection in sparse networks
• Density Evolution in the Degree-correlated Stochastic Block Model
• Community Detection and Improved Detectability in Multiplex Networks
• Finite size analysis of the detectability limit of the stochastic block model
• Self-falsifiable Hierarchical Detection of Overlapping Communities On Social Networks
• Generative models for local network community detection