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 (GCC) 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. Initial computations show that analogous criteria are plausible for directed graphs (less so for weighted graphs). We are in the process of checking the criterion in real-world networks.

The empirical observations we use are:

1. for graphs with community structure GCC is greater than for random graphs, but it reaches the latter value before its connectivity is fully random,

2. saturation of GCC coincides with the theoretically predicted limit of detectability,

3. GCC is proportional to the 3rd moment of eigenspectrum; since communities are related to isolated eigenvalues to the right of the bulk of the spectrum, large GCC means strong community structure, see Obs. 1.,

4. GCC is strictly lower than what can be predicted by the largest eigenvalue alone.

(We observe these facts on Erdos-Renyi, Barabasi-Albert, Newman-Girvan and Lancichinetti-Fortunato-Radicchi graphs.)

Together with known approximations of GCC and the largest eigenvalue of adjacency matrix, we are able to derive the criterion.

• Legal notice:
  

  Copyright (c) Pielaszek Research, all rights reserved.
  The above materials, including auxiliary resources, are subject to Publisher's copyright and the Author(s) intellectual rights. Without limiting Author(s) rights under respective Copyright Transfer Agreement, no part of the above documents may be reproduced without the express written permission of Pielaszek Research, the Publisher. Express permission from the Author(s) is required to use the above materials for academic purposes, such as lectures or scientific presentations.
  In every case, proper references including Author(s) name(s) and URL of this webpage: https://science24.com/paper/31856 must be provided.