Combinatorial approach to modularity
Radicchi, F, Lancichinetti, A, Ramasco, JJPhys. Rev. E 82, 026102 (2010)
Times cited: 8
Abstract
Communities are clusters of nodes with a higher than average density of
internal connections. Their detection is of great relevance to better
understand the structure and hierarchies present in a network.
Modularity has become a standard tool in the area of community
detection, providing at the same time a way to evaluate partitions and,
by maximizing it, a method to find communities. In this work, we study
the modularity from a combinatorial point of view. Our analysis (as the
modularity definition) relies on the use of the configurational model,
a technique that given a graph produces a series of randomized copies
keeping the degree sequence invariant. We develop an approach that
enumerates the null model partitions and can be used to calculate the
probability distribution function of the modularity. Our theory allows
for a deep inquiry of several interesting features characterizing
modularity such as its resolution limit and the statistics of the
partitions that maximize it. Additionally, the study of the probability
of extremes of the modularity in the random graph partitions opens the
way for a definition of the statistical significance of network
partitions.