Fast and accurate determination of modularity and its effect size

Santiago III Treviño; Amy Nyberg; Charo del Genio; Kevin Bassler

doi:10.1088/1742-5468/2015/02/P02003

Fast and accurate determination of modularity and its effect size

Santiago III Treviño, Amy Nyberg, Charo del Genio, Kevin Bassler

School of Computing, Electronics and Maths

Research output: Contribution to journal › Article › peer-review

17 Citations (Scopus)

17 Downloads (Pure)

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.

Original language	English
Article number	P02003
Journal	Journal of Statistical Mechanics: Theory and Experiment
Volume	2015
DOIs	https://doi.org/10.1088/1742-5468/2015/02/P02003
Publication status	Published - 3 Feb 2015

Bibliographical note

Copyright © and Moral Rights are retained by the author(s) and/ or other copyright owners. A copy can be downloaded for personal non-commercial research or study, without prior permission or charge. This item cannot be reproduced or quoted extensively from without first obtaining permission in writing from the copyright holder(s). The content must not be changed in any way or sold commercially in any format or medium without the formal permission of the copyright holders.

Access to Document

10.1088/1742-5468/2015/02/P02003

Post-PrintAccepted author manuscript, 882 KBLicence: CC BY

Cite this

@article{7aa6149286624750bfd9150e9200e582,

title = "Fast and accurate determination of modularity and its effect size",

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{\H o}s-R{\'e}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.",

author = "Trevi{\~n}o, {Santiago III} and Amy Nyberg and {del Genio}, Charo and Kevin Bassler",

note = "Copyright {\textcopyright} and Moral Rights are retained by the author(s) and/ or other copyright owners. A copy can be downloaded for personal non-commercial research or study, without prior permission or charge. This item cannot be reproduced or quoted extensively from without first obtaining permission in writing from the copyright holder(s). The content must not be changed in any way or sold commercially in any format or medium without the formal permission of the copyright holders. ",

year = "2015",

month = feb,

day = "3",

doi = "10.1088/1742-5468/2015/02/P02003",

language = "English",

volume = "2015",

journal = "Journal of Statistical Mechanics: Theory and Experiment",

issn = "1742-5468",

publisher = "IOP Publishing",

}

TY - JOUR

T1 - Fast and accurate determination of modularity and its effect size

AU - Treviño, Santiago III

AU - Nyberg, Amy

AU - del Genio, Charo

AU - Bassler, Kevin

N1 - Copyright © and Moral Rights are retained by the author(s) and/ or other copyright owners. A copy can be downloaded for personal non-commercial research or study, without prior permission or charge. This item cannot be reproduced or quoted extensively from without first obtaining permission in writing from the copyright holder(s). The content must not be changed in any way or sold commercially in any format or medium without the formal permission of the copyright holders.

PY - 2015/2/3

Y1 - 2015/2/3

N2 - 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.

AB - 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.

UR - https://charodelgenio.weebly.com/community-detection.html

U2 - 10.1088/1742-5468/2015/02/P02003

DO - 10.1088/1742-5468/2015/02/P02003

M3 - Article

VL - 2015

JO - Journal of Statistical Mechanics: Theory and Experiment

JF - Journal of Statistical Mechanics: Theory and Experiment

SN - 1742-5468

M1 - P02003

ER -

Fast and accurate determination of modularity and its effect size

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Charo del Genio

Cite this

Fast and accurate determination of modularity and its effect size

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Profiles

Charo del Genio

Cite this