# Reinventing the Triangles: Rule of Thumb for Assessing Detectability

Source: [Reinventing the Triangles: Rule of Thumb for Assessing Detectability](<https://www.sota2.com/research/paper/68fa33651e209131ce88fe0d>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-24T20:02:45.256Z

Authors: Jeremi K. Ochab

Published: 2015-11-03T13:36:52.000Z

## 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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1511.00906>)

[PDF](<https://arxiv.org/pdf/1511.00906.pdf>)
