Decoding communities in networks
arXiv:1711.05310 · doi:10.1103/PhysRevE.97.022316
Abstract
According to a recent information-theoretical proposal, the problem of defining and identifying communities in networks can be interpreted as a classical communication task over a noisy channel: memberships of nodes are information bits erased by the channel, edges and non-edges in the network are parity bits introduced by the encoder but degraded through the channel, and a community identification algorithm is a decoder. The interpretation is perfectly equivalent to the one at the basis of well-known statistical inference algorithms for community detection. The only difference in the interpretation is that a noisy channel replaces a stochastic network model. However, the different perspective gives the opportunity to take advantage of the rich set of tools of coding theory to generate novel insights on the problem of community detection. In this paper, we illustrate two main applications of standard coding-theoretical methods to community detection. First, we leverage a state-of-the-art decoding technique to generate a family of quasi-optimal community detection algorithms. Second and more important, we show that the Shannon's noisy-channel coding theorem can be invoked to establish a lower bound, here named as decodability bound, for the maximum amount of noise tolerable by an ideal decoder to achieve perfect detection of communities. When computed for well-established synthetic benchmarks, the decodability bound explains accurately the performance achieved by the best community detection algorithms existing on the market, telling us that only little room for their improvement is still potentially left.
arXiv comment9 pages, 5 figures + Appendix
References in corpus (24)
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- Maps of random walks on complex networks reveal community structure
- Benchmark graphs for testing community detection algorithms
- Comparing community structure identification
- Defining and identifying communities in networks
- Community detection algorithms: a comparative analysis
- Stochastic blockmodels and community structure in networks
- An information-theoretic framework for resolving community structure in complex networks
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Spectral redemption: clustering sparse networks
- Detecting fuzzy community structures in complex networks with a Potts model
- The ground truth about metadata and community detection in networks
- Spectral methods for network community detection and graph partitioning
- Phase transition in the detection of modules in sparse networks
- Graph spectra and the detectability of community structure in networks
- Hierarchical Block Structures and High-resolution Model Selection in Large Networks
- Parsimonious module inference in large networks
- Detectability of communities in heterogeneous networks
- A paradox in community detection
- Gallager error correcting codes for binary asymmetric channels
- Finite size analysis of the detectability limit of the stochastic block model
- Community Detection and Stochastic Block Models