Error-Correcting Decoders for Communities in Networks
arXiv:1902.00896
Abstract
As recent work demonstrated, the task of identifying communities in networks can be considered analogous to the classical problem of decoding messages transmitted along a noisy channel. We leverage this analogy to develop a community detection method directly inspired by a standard and widely-used decoding technique. We further simplify the algorithm to reduce the time complexity from quadratic to linear. We test the performance of the original and reduced versions of the algorithm on artificial benchmarks with pre-imposed community structure, and on real networks with annotated community structure. Results of our systematic analysis indicate that the proposed techniques are able to provide satisfactory results.
8 pages, 5 figures, 2 tables
References in corpus (13)
- Modularity and community structure in 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
- Benchmark graphs for testing community detection algorithms
- Comparing community structure identification
- Stochastic blockmodels and community structure in networks
- Mixture models and exploratory analysis in networks
- Phase transition in the detection of modules in sparse networks
- Graph spectra and the detectability of community structure in networks
- Parsimonious module inference in large networks
- Community detection in networks: Structural communities versus ground truth
- Community Detection as an Inference Problem