Fast and accurate determination of modularity and its effect size

DOI10.1088/1742-5468/2015/02/P02003MaRDI QIDQ80115zbMATH OpenOpenAlexFDO

Authors Santiago Treviño, Amy Nyberg, Charo I Del Genio, Kevin E Bassler, Santiago Treviño III, Amy Nyberg, Charo I. del Genio, K. E. Bassler

Publication date 3 February 2015

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.8669

Mathematics Subject Classification ID

Stochastic analysis in statistical mechanics (82M60)

Abstract: We present a fast spectral algorithm for community detection in complex networks. Our method searches for the partition with the maximum value of the modularity via the interplay of several refinement steps that include both agglomeration and division. We validate the accuracy of the algorithm by applying it to several real-world benchmark networks. On all these, our algorithm performs as well or better than any other known polynomial scheme. This allows us to extensively study the modularity distribution in ensembles of ErdH{o}s-R'enyi networks, producing theoretical predictions for means and variances inclusive of finite-size corrections. Our work provides a way to accurately estimate the effect size of modularity, providing a $z$-score measure of it and enabling a more informative comparison of networks with different numbers of nodes and links.

Recommendations

• Detecting network communities: a new systematic and efficient algorithm
• Finding network communities using modularity density
• Fast unfolding of communities in large networks
• Asymptotic distribution of modularity in networks
• A Hypothesis Testing Framework for Modularity Based Network Community Detection

Cites work

• An Efficient Heuristic Procedure for Partitioning Graphs
• Community structure in social and biological networks
• Complex networks: structure and dynamics
• Constructing and sampling directed graphs with given degree sequences
• Graph clustering
• Statistical mechanics of complex networks
• The Structure and Function of Complex Networks
• When are networks truly modular?

Cited in

(6)

• Finding network communities using modularity density
• Evaluating accuracy of community detection using the relative normalized mutual information
• A simple and efficient algorithm for modeling modular complex networks
• Greedy recursive spectral bisection for modularity-bound hierarchical divisive community detection
• Network community detection using modularity density measures
• BipartiteModularityMaximization

This page was built for publication: Fast and accurate determination of modularity and its effect size

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q80115)