
The Library
Fast and accurate determination of modularity and its effect size
Tools
Treviño, Santiago, Nyberg, Amy, Del Genio, Charo I. and Bassler, Kevin E. (2015) Fast and accurate determination of modularity and its effect size. Journal of Statistical Mechanics : Theory and Experiment, 2015 (2). P02003. doi:10.1088/1742-5468/2015/02/P02003 ISSN 1742-5468.
![]() |
PDF
WRAP_trevio_-_fast_and_accurate_determination.pdf - Accepted Version - Requires a PDF viewer. Download (792Kb) |
Official URL: http://dx.doi.org/10.1088/1742-5468/2015/02/P02003
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 Erdős–Rényi 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.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QC Physics | ||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Research Centres > Centre for Complexity Science Faculty of Science, Engineering and Medicine > Science > Life Sciences (2010- ) Faculty of Science, Engineering and Medicine > Science > Mathematics Faculty of Science, Engineering and Medicine > Medicine > Warwick Medical School |
||||||||
Library of Congress Subject Headings (LCSH): | Algorithms, Statistical mechanics | ||||||||
Journal or Publication Title: | Journal of Statistical Mechanics : Theory and Experiment | ||||||||
Publisher: | Institute of Physics Publishing Ltd. | ||||||||
ISSN: | 1742-5468 | ||||||||
Official Date: | 3 February 2015 | ||||||||
Dates: |
|
||||||||
Volume: | 2015 | ||||||||
Number: | 2 | ||||||||
Article Number: | P02003 | ||||||||
DOI: | 10.1088/1742-5468/2015/02/P02003 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 18 November 2016 | ||||||||
Date of first compliant Open Access: | 18 November 2016 | ||||||||
Funder: | National Science Foundation (U.S.) (NSF), United States. Air Force. Office of Scientific Research (AFOSR), United States. Defense Advanced Research Projects Agency (DARPA), Seventh Framework Programme (European Commission) (FP7) | ||||||||
Grant number: | DMR-1206839 (NSF), FA9550-12-1- 0405 (AFOSR & DARPA), 288021 (FP7) |
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |
Downloads
Downloads per month over past year