Reinventing the Triangles: Rule of Thumb for Assessing Detectability

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.

6 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 (12)

• Fast unfolding of communities in large networks
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Finding statistically significant communities in networks
• Consensus clustering in complex networks
• Clustering in Complex Directed Networks
• Phase transition in the detection of modules in sparse networks
• Graph spectra and the detectability of community structure in networks
• Spectra of random graphs with arbitrary expected degrees
• (Un)detectable cluster structure in sparse networks
• Spectra of random graphs with community structure and arbitrary degrees
• Approximate Triangle Counting