(Un)detectable cluster structure in sparse networks

Abstract

We study the problem of recovering a known cluster structure in a sparse network, also known as the planted partitioning problem, by means of statistical mechanics. We find a sharp transition from un-recoverable to recoverable structure as a function of the separation of the clusters. For multivariate data, such transitions have been observed frequently, but always as a function of the number of data points provided, i.e. given a large enough data set, two point clouds can always be recognized as different clusters, as long as their separation is non-zero. In contrast, for the sparse networks studied here, a cluster structure remains undetectable even in an infinitely large network if a critical separation is not exceeded. We give analytic formulas for this critical separation as a function of the degree distribution of the network and calculate the shape of the recoverability-transition. Our findings have implications for unsupervised learning and data-mining in relational data bases and provide bounds on the achievable performance of graph clustering algorithms.

4 Pages, 2 Figures

References in corpus (8)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Finding and evaluating community structure in networks
• Comparing community structure identification
• Polynomial iterative algorithms for coloring and analyzing random graphs
• Partitioning and modularity of graphs with arbitrary degree distribution
• Computational complexity arising from degree correlations in networks
• Phase transitions in optimal unsupervised learning

Cited by in corpus (46)

• Community detection in graphs
• Community detection algorithms: a comparative analysis
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Spectral methods for network community detection and graph partitioning
• Phase transition in the detection of modules in sparse networks
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Graph spectra and the detectability of community structure in networks
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Identification of core-periphery structure in networks
• Statistical significance of communities in networks
• Bayesian stochastic blockmodeling
• Community detection and graph partitioning
• Spectral methods for the detection of network community structure: a comparative analysis
• Enhanced detectability of community structure in multilayer networks through layer aggregation
• Consistency of community structure in complex networks
• Protein-Interaction-Networks: More than mere modules
• Spectra of random graphs with community structure and arbitrary degrees
• Community detection in networks with unequal groups
• Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
• Significant communities in large sparse networks
• A paradox in community detection
• Universality of the stochastic block model
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Community Detection with and without Prior Information
• Comparative Study for Inference of Hidden Classes in Stochastic Block Models
• Improving the performance of algorithms to find communities in networks
• Identifying multi-scale communities in networks by asymptotic surprise
• Algorithmic detectability threshold of the stochastic block model
• Modularity and Projection of Bipartite Networks
• Phase Transitions in Community Detection: A Solvable Toy Model
• Community detection based on significance optimization in complex networks
• Global disorder transition in the community structure of large-q Potts systems
• Detectability of the spectral method for sparse graph partitioning
• Detecting the optimal number of communities in complex networks
• Finite size analysis of the detectability limit of the stochastic block model
• A Tractable Fully Bayesian Method for the Stochastic Block Model
• Statistical Mechanics of Semi-Supervised Clustering in Sparse Graphs
• Detectability thresholds of general modular graphs
• Detectability of Macroscopic Structures in Directed Asymmetric Stochastic Block Model
• Inference of hidden structures in complex physical systems by multi-scale clustering
• Learning Interpretable Collective Variables for Spreading Processes on Networks
• Stochastic fluctuations and the detectability limit of network communities
• Linking Through Time: Memory-Enhanced Community Discovery in Temporal Networks
• Detectability threshold in weighted modular networks
• Reinventing the Triangles: Rule of Thumb for Assessing Detectability