2010/08/20 by Alvarez-Hamelin, José Ignacio, Gastón, Beiró Mariano, Busch, Jorge Rodolfo
#FOS: Computer and information sciences #FOS: Physical sciences #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI) #Statistical Mechanics (cond-mat.stat-mech)
paper · doi:10.48550/arxiv.1008.3443
Modularity was introduced as a measure of goodness for the community structure induced by a partition of the set of vertices in a graph. Then, it also became an objective function used to find good partitions, with high success. Nevertheless, some works have shown a scaling limit and certain instabilities when finding communities with this criterion. Modularity has been studied proposing several formalisms, as hamiltonians in a Potts model or laplacians in spectral partitioning. In this paper we present a new probabilistic formalism to analyze modularity, and from it we derive an algorithm based on weakly optimal partitions. This algorithm obtains good quality partitions and also scales to large graphs.