Finding network communities using modularity density

Federico Botta, Charo del Genio

Research output: Contribution to journalArticle

8 Citations (Scopus)
8 Downloads (Pure)

Abstract

Many real-world complex networks exhibit a community structure, in which the modules correspond to actual functional units. Identifying these communities is a key challenge for scientists. A common approach is to search for the network partition that maximizes a quality function. Here, we present a detailed analysis of a recently proposed function, namely modularity density. We show that it does not incur in the drawbacks suffered by traditional modularity, and that it can identify networks without ground-truth community structure, deriving its analytical dependence on link density in generic random graphs. In addition, we show that modularity density allows an easy comparison between networks of different sizes, and we also present some limitations that methods based on modularity density may suffer from. Finally, we introduce an efficient, quadratic community detection algorithm based on modularity density maximization, validating its accuracy against theoretical predictions and on a set of benchmark networks.
Original languageEnglish
Article number123402
JournalJournal of Statistical Mechanics: Theory and Experiment
DOIs
Publication statusPublished - 19 Dec 2016
Externally publishedYes

Fingerprint

modularity
Modularity
Community Structure
Community Detection
ground truth
Random Graphs
Complex Networks
partitions
modules
Maximise
Partition
Community
Benchmark
Module
Unit
Prediction
predictions

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.

Keywords

  • Complex Networks
  • Community Detection
  • Network Algorithms
  • Modularity Density

Cite this

Finding network communities using modularity density. / Botta, Federico; del Genio, Charo.

In: Journal of Statistical Mechanics: Theory and Experiment, 19.12.2016.

Research output: Contribution to journalArticle

@article{2adb576c028144e2ad3f30390aa19db0,
title = "Finding network communities using modularity density",
abstract = "Many real-world complex networks exhibit a community structure, in which the modules correspond to actual functional units. Identifying these communities is a key challenge for scientists. A common approach is to search for the network partition that maximizes a quality function. Here, we present a detailed analysis of a recently proposed function, namely modularity density. We show that it does not incur in the drawbacks suffered by traditional modularity, and that it can identify networks without ground-truth community structure, deriving its analytical dependence on link density in generic random graphs. In addition, we show that modularity density allows an easy comparison between networks of different sizes, and we also present some limitations that methods based on modularity density may suffer from. Finally, we introduce an efficient, quadratic community detection algorithm based on modularity density maximization, validating its accuracy against theoretical predictions and on a set of benchmark networks.",
keywords = "Complex Networks, Community Detection, Network Algorithms, Modularity Density",
author = "Federico Botta and {del Genio}, Charo",
note = "Copyright {\circledC} 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 = "2016",
month = "12",
day = "19",
doi = "10.1088/1742-5468/2016/12/123402",
language = "English",
journal = "Journal of Statistical Mechanics: Theory and Experiment",
issn = "1742-5468",
publisher = "IOP Publishing",

}

TY - JOUR

T1 - Finding network communities using modularity density

AU - Botta, Federico

AU - del Genio, Charo

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 - 2016/12/19

Y1 - 2016/12/19

N2 - Many real-world complex networks exhibit a community structure, in which the modules correspond to actual functional units. Identifying these communities is a key challenge for scientists. A common approach is to search for the network partition that maximizes a quality function. Here, we present a detailed analysis of a recently proposed function, namely modularity density. We show that it does not incur in the drawbacks suffered by traditional modularity, and that it can identify networks without ground-truth community structure, deriving its analytical dependence on link density in generic random graphs. In addition, we show that modularity density allows an easy comparison between networks of different sizes, and we also present some limitations that methods based on modularity density may suffer from. Finally, we introduce an efficient, quadratic community detection algorithm based on modularity density maximization, validating its accuracy against theoretical predictions and on a set of benchmark networks.

AB - Many real-world complex networks exhibit a community structure, in which the modules correspond to actual functional units. Identifying these communities is a key challenge for scientists. A common approach is to search for the network partition that maximizes a quality function. Here, we present a detailed analysis of a recently proposed function, namely modularity density. We show that it does not incur in the drawbacks suffered by traditional modularity, and that it can identify networks without ground-truth community structure, deriving its analytical dependence on link density in generic random graphs. In addition, we show that modularity density allows an easy comparison between networks of different sizes, and we also present some limitations that methods based on modularity density may suffer from. Finally, we introduce an efficient, quadratic community detection algorithm based on modularity density maximization, validating its accuracy against theoretical predictions and on a set of benchmark networks.

KW - Complex Networks

KW - Community Detection

KW - Network Algorithms

KW - Modularity Density

UR - https://github.com/FedericoBotta/ModularityDensity

U2 - 10.1088/1742-5468/2016/12/123402

DO - 10.1088/1742-5468/2016/12/123402

M3 - Article

JO - Journal of Statistical Mechanics: Theory and Experiment

JF - Journal of Statistical Mechanics: Theory and Experiment

SN - 1742-5468

M1 - 123402

ER -