Reinventing the Triangles: Rule of Thumb for Assessing Detectability
arXiv:1511.00906 · doi:10.1109/SITIS.2015.44
Abstract
Statistical significance of network clustering has been an unresolved problem since it was observed that community detection algorithms produce false positives even in random graphs. After a phase transition between undetectable and detectable cluster structures was discovered, the connection between spectra of adjacency matrices and detectability limits were shown, and both were calculated for a wide range of networks with arbitrary degree distributions and community structure. In practice the full eigenspectrum is not known, and whether a given network has any communities within detectability regime cannot be easily established. Based on the global clustering coefficient we construct a criterion telling whether in an undirected, unweighted network there is some/no detectable community structure, or if the network is in a transient regime. The method is simple and faster than methods involving bootstrapping.
arXiv comment6 pages, 4 figures. Accepted to IEEE Computer Society. Presented at The 4th International Workshop on Complex Networks and their Applications, November 23-27, 2015 Bangkok, Thailand
References in corpus (25)
- Fast unfolding of communities in large networks
- Community structure in social and biological networks
- Community detection in graphs
- Maps of random walks on complex networks reveal community structure
- The architecture of complex weighted networks
- Benchmark graphs for testing community detection algorithms
- Community detection algorithms: a comparative analysis
- Finding statistically significant communities in networks
- Organization of Growing Random Networks
- Consensus clustering in complex networks
- Clustering in Complex Directed Networks
- Generalizations of the clustering coefficient to weighted complex networks
- Spectra of "Real-World" Graphs: Beyond the Semi-Circle Law
- Class of correlated random networks with hidden variables
- Phase transition in the detection of modules in sparse networks
- Growing Scale-Free Networks with Small World Behavior
- Graph spectra and the detectability of community structure in networks
- Random graphs as models of networks
- Statistical significance of communities in networks
- Spectra of random graphs with arbitrary expected degrees
- Clustering of correlated networks
- Network Transitivity and Matrix Models
- (Un)detectable cluster structure in sparse networks
- Spectra of random graphs with community structure and arbitrary degrees
- Approximate Triangle Counting