Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2017 Nov 9;12(11):e0187603.
doi: 10.1371/journal.pone.0187603. eCollection 2017.

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

Yu-Hsiang Fu  1 , Chung-Yuan Huang  2 , Chuen-Tsai Sun  1
Affiliations

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

Yu-Hsiang Fu et al. PLoS One. .

Abstract

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.

PubMed Disclaimer

Conflict of interest statement

Competing Interests: The authors declare no competing financial interests.

Figures

Fig 1
Fig 1. HAM community detection architecture.
Fig 2
Fig 2. Edge classification results for a toy network.
(a) The network, (b) after calculating similarities, (c) after classifying edges.
Fig 3
Fig 3. HAM algorithm flowchart.
Fig 4
Fig 4. A comparison of similarities among the LFR benchmark networks used in this study.
(a) 50000S, (b) 50000B.
Fig 5
Fig 5. NMI results for the LFR benchmark networks used in this study.
(a) 1000S, (b) 1000B, (c) 5000S, (d) 5000B, (e) 10000S, (f) 10000B, (g) 50000S, (h) 50000B.
Fig 6
Fig 6. Execution time results for the LFR benchmark networks used in this study.
(a) 1000S, (b) 1000B, (c) 5000S, (d) 5000B, (e) 10000S, (f) 10000B, (g) 50000S, (h) 50000B.
Fig 7
Fig 7. Execution time growth rate results for the LFR benchmark networks used in this study.
(a) 50000S, (b) 50000B.
Fig 8
Fig 8. Multi-resolution analysis data for different Karate network similarities.
Fig 9
Fig 9. Multi-resolution analysis of different Dolphins network similarities.
Fig 10
Fig 10. The HAM multi-resolution problem.
(a) The test network; (b) multi-resolution problem result; (c) modified strategy solution; (d) solution involving the addition of edges without modifying the strategy.
See this image and copyright information in PMC

Similar articles

See all similar articles

Cited by

References

    1. Newman M. Networks: An introduction. Oxford University Press; 2010.
    1. Girvan M, Newman ME. Community structure in social and biological networks. Proceedings of the National Academy of Sciences. 2002; 99(12): 7821–7826. - PMC - PubMed
    1. Fu YH, Huang CY, Sun CT. Using global diversity and local topology features to identify influential network spreaders. Physica A: Statistical Mechanics and its Applications. 2015; 433: 344–355.
    1. Watts DJ, Strogatz SH. Collective dynamics of ‘small-world’networks. Nature. 1998; 393(6684): 440–442. doi: 10.1038/30918 - DOI - PubMed
    1. Barabási AL, Albert R. Emergence of scaling in random networks. Science. 1999; 286(5439): 509–512. - PubMed

Grants and funding

This work was supported by the Republic of China National Science Council (MOST-106-2221-E-182-073) and the High Speed Intelligent Communication (HSIC) Research Center of Chang Gung University, Taiwan. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.

LinkOut - more resources