Speaker
Jeremi Ochab
(M. Smoluchowski Institute of Physics, Jagiellonian University, Kraków)
Description
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 [1,2], the spectra of adjacency matrices and detectability limits were shown to be connected, and they were calculated for a wide range of networks with community structure [3]. In practice, given a real-world network neither the hypothetical network model nor its full eigenspectrum is known, and whether the network has any detectable communities 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. To that end we use approximations of GCC and the spectra of adjacency matrices, together with the empirical observations showing that: a) for graphs with community structure GCC reaches the random graph value before its connectivity is fully random, and b) this saturation of GCC coincides with the theoretically predicted limit of detectability.
We compare the criterion against existing methods of assessing significance of network partitioning. We compute it on various benchmark graphs, as well as on real-world networks from SNAP database, and compare it with the results of state-of-the-art community detection methods. The method is simple and faster than methods involving bootstrapping; it is robust also on sparse networks. Analogous criteria are plausible also for directed graphs.
$ $
1. J. Reichardt and M. Leone, Phys. Rev. Lett. 101, 078701 (2008).
2. A. Decelle, F. Krzakala, C. Moore, and L. Zdeborova, Phys. Rev. Lett. 107, 065701 (2011).
3. X. Zhang, R. R. Nadakuditi, and M. E. J. Newman, Phys. Rev. E 89, 042816 (2014).
Primary author
Jeremi Ochab
(M. Smoluchowski Institute of Physics, Jagiellonian University, Kraków)
