A community detection algorithm using network topologies and rule-based hierarchical arc-merging strategies

Yu Hsiang Fu, Chung Yuan Huang*, Chuen Tsai Sun

*Corresponding author for this work

Research output: Contribution to journalJournal Article peer-review

6 Scopus citations


The authors use four criteria to examine a novel community detection algorithm: (a) effectiveness in terms of producing high values of normalized mutual information (NMI) and modularity, using well-known social networks for testing; (b) examination, meaning the ability to examine mitigating resolution limit problems using NMI values and synthetic networks; (c) correctness, meaning the ability to identify useful community structure results in terms of NMI values and Lancichinetti-Fortunato-Radicchi (LFR) benchmark networks; and (d) scalability, or the ability to produce comparable modularity values with fast execution times when working with large-scale real-world networks. In addition to describing a simple hierarchical arc-merging (HAM) algorithm that uses network topology information, we introduce rule-based arc-merging strategies for identifying community structures. Five well-studied social network datasets and eight sets of LFR benchmark networks were employed to validate the correctness of a ground-truth community, eight large-scale real-world complex networks were used to measure its efficiency, and two synthetic networks were used to determine its susceptibility to two resolution limit problems. Our experimental results indicate that the proposed HAM algorithm exhibited satisfactory performance efficiency, and that HAM-identified and ground-truth communities were comparable in terms of social and LFR benchmark networks, while mitigating resolution limit problems.

Original languageEnglish
Article numbere0187603
JournalPLoS ONE
Issue number11
StatePublished - 11 2017

Bibliographical note

Publisher Copyright:
© 2017 Fu et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.


Dive into the research topics of 'A community detection algorithm using network topologies and rule-based hierarchical arc-merging strategies'. Together they form a unique fingerprint.

Cite this