Reinventing the Triangles: Rule of Thumb for Assessing Detectability

Jeremi K. Ochab 

Jagiellonian University, Institute of Physics, ul. Łojasiewicza 11, Kraków 30-348, Poland

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

 

Presentation: Poster at 8 Ogólnopolskie Sympozjum "Fizyka w Ekonomii i Naukach Społecznych", by Jeremi K. Ochab
See On-line Journal of 8 Ogólnopolskie Sympozjum "Fizyka w Ekonomii i Naukach Społecznych"

Submitted: 2015-09-30 17:00
Revised:   2015-09-30 17:28