IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0155320.html
   My bibliography  Save this article

Detecting Community Structure by Using a Constrained Label Propagation Algorithm

Author

Listed:
  • Jia Hou Chin
  • Kuru Ratnavelu

Abstract

Community structure is considered one of the most interesting features in complex networks. Many real-world complex systems exhibit community structure, where individuals with similar properties form a community. The identification of communities in a network is important for understanding the structure of said network, in a specific perspective. Thus, community detection in complex networks gained immense interest over the last decade. A lot of community detection methods were proposed, and one of them is the label propagation algorithm (LPA). The simplicity and time efficiency of the LPA make it a popular community detection method. However, the LPA suffers from instability detection due to randomness that is induced in the algorithm. The focus of this paper is to improve the stability and accuracy of the LPA, while retaining its simplicity. Our proposed algorithm will first detect the main communities in a network by using the number of mutual neighbouring nodes. Subsequently, nodes are added into communities by using a constrained LPA. Those constraints are then gradually relaxed until all nodes are assigned into groups. In order to refine the quality of the detected communities, nodes in communities can be switched to another community or removed from their current communities at various stages of the algorithm. We evaluated our algorithm on three types of benchmark networks, namely the Lancichinetti-Fortunato-Radicchi (LFR), Relaxed Caveman (RC) and Girvan-Newman (GN) benchmarks. We also apply the present algorithm to some real-world networks of various sizes. The current results show some promising potential, of the proposed algorithm, in terms of detecting communities accurately. Furthermore, our constrained LPA has a robustness and stability that are significantly better than the simple LPA as it is able to yield deterministic results.

Suggested Citation

  • Jia Hou Chin & Kuru Ratnavelu, 2016. "Detecting Community Structure by Using a Constrained Label Propagation Algorithm," PLOS ONE, Public Library of Science, vol. 11(5), pages 1-21, May.
  • Handle: RePEc:plo:pone00:0155320
    DOI: 10.1371/journal.pone.0155320
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0155320
    Download Restriction: no

    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0155320&type=printable
    Download Restriction: no

    File URL: https://libkey.io/10.1371/journal.pone.0155320?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Sybil Derrible, 2012. "Network Centrality of Metro Systems," PLOS ONE, Public Library of Science, vol. 7(7), pages 1-10, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Ding, Rui & Zhou, Tao & Zhang, Yilin & Du, YiMing & Chen, Shihui & Fu, Jun & Du, Linyu & Zhang, Ting & Li, Tongfei, 2022. "The influence of average speed ratio on multilayer traffic network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 594(C).
    2. Ding, Rui & Ujang, Norsidah & Hamid, Hussain bin & Manan, Mohd Shahrudin Abd & He, Yuou & Li, Rong & Wu, Jianjun, 2018. "Detecting the urban traffic network structure dynamics through the growth and analysis of multi-layer networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 503(C), pages 800-817.
    3. Helena Mihaljević & Lucía Santamaría, 2021. "Disambiguation of author entities in ADS using supervised learning and graph theory methods," Scientometrics, Springer;Akadémiai Kiadó, vol. 126(5), pages 3893-3917, May.
    4. Hao Xu & Yuan Ran & Junqian Xing & Li Tao, 2023. "An Influence-Based Label Propagation Algorithm for Overlapping Community Detection," Mathematics, MDPI, vol. 11(9), pages 1-17, May.
    5. Hosseini-Pozveh, Maryam & Ghorbanian, Maedeh & Tabaiyan, Maryam, 2022. "A label propagation-based method for community detection in directed signed social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 604(C).
    6. Rui Ding & Jun Fu & Yiming Du & Linyu Du & Tao Zhou & Yilin Zhang & Siwei Shen & Yuqi Zhu & Shihui Chen, 2022. "Structural Evolution and Community Detection of China Rail Transit Route Network," Sustainability, MDPI, vol. 14(19), pages 1-19, September.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Sadayuki, Taisuke, 2018. "Measuring the spatial effect of multiple sites: An application to housing rent and public transportation in Tokyo, Japan," Regional Science and Urban Economics, Elsevier, vol. 70(C), pages 155-173.
    2. Wang, Ziyulong & Huang, Ketong & Massobrio, Renzo & Bombelli, Alessandro & Cats, Oded, 2024. "Quantification and comparison of hierarchy in Public Transport Networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 634(C).
    3. Kermanshah, A. & Derrible, S., 2016. "A geographical and multi-criteria vulnerability assessment of transportation networks against extreme earthquakes," Reliability Engineering and System Safety, Elsevier, vol. 153(C), pages 39-49.
    4. Cats, Oded, 2017. "Topological evolution of a metropolitan rail transport network: The case of Stockholm," Journal of Transport Geography, Elsevier, vol. 62(C), pages 172-183.
    5. Huang, Jie & Levinson, David M., 2015. "Circuity in urban transit networks," Journal of Transport Geography, Elsevier, vol. 48(C), pages 145-153.
    6. Ermagun, Alireza & Tajik, Nazanin & Janatabadi, Fatemeh & Mahmassani, Hani, 2023. "Uncertainty in vulnerability of metro transit networks: A global perspective," Journal of Transport Geography, Elsevier, vol. 113(C).
    7. Hyun Kim & Yena Song, 2018. "An integrated measure of accessibility and reliability of mass transit systems," Transportation, Springer, vol. 45(4), pages 1075-1100, July.
    8. Suchat Tachaudomdach & Auttawit Upayokin & Nopadon Kronprasert & Kriangkrai Arunotayanun, 2021. "Quantifying Road-Network Robustness toward Flood-Resilient Transportation Systems," Sustainability, MDPI, vol. 13(6), pages 1-16, March.
    9. Zheng, Lingwei & Austwick, Martin Zaltz, 2023. "Classifying station areas in greater Manchester using the node-place-design model: A comparative analysis with system centrality and green space coverage," Journal of Transport Geography, Elsevier, vol. 112(C).
    10. Elisa Frutos Bernal & Angel Martín del Rey, 2019. "Study of the Structural and Robustness Characteristics of Madrid Metro Network," Sustainability, MDPI, vol. 11(12), pages 1-24, June.
    11. Hu, Xinlei & Huang, Jie & Shi, Feng, 2019. "Circuity in China's high-speed-rail network," Journal of Transport Geography, Elsevier, vol. 80(C).
    12. Wang, Xiangrong & Koç, Yakup & Derrible, Sybil & Ahmad, Sk Nasir & Pino, Willem J.A. & Kooij, Robert E., 2017. "Multi-criteria robustness analysis of metro networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 474(C), pages 19-31.
    13. Siddharth Patwardhan & Marc Barthelemy & Şirag Erkol & Santo Fortunato & Filippo Radicchi, 2024. "Symmetry breaking in optimal transport networks," Nature Communications, Nature, vol. 15(1), pages 1-9, December.
    14. Jiangang Shi & Shiping Wen & Xianbo Zhao & Guangdong Wu, 2019. "Sustainable Development of Urban Rail Transit Networks: A Vulnerability Perspective," Sustainability, MDPI, vol. 11(5), pages 1-24, March.
    15. Zhang, Mengyao & Huang, Tao & Guo, Zhaoxia & He, Zhenggang, 2022. "Complex-network-based traffic network analysis and dynamics: A comprehensive review," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 607(C).
    16. Parthasarathi, Pavithra & Levinson, David, 2018. "Network structure and the journey to work: An intra-metropolitan analysis," Transportation Research Part A: Policy and Practice, Elsevier, vol. 118(C), pages 292-304.
    17. Mohammad Zaher Serdar & Sami G. Al-Ghamdi, 2021. "Resiliency Assessment of Road Networks during Mega Sport Events: The Case of FIFA World Cup Qatar 2022," Sustainability, MDPI, vol. 13(22), pages 1-15, November.
    18. Jungyeol Hong & Reuben Tamakloe & Soobeom Lee & Dongjoo Park, 2019. "Exploring the Topological Characteristics of Complex Public Transportation Networks: Focus on Variations in Both Single and Integrated Systems in the Seoul Metropolitan Area," Sustainability, MDPI, vol. 11(19), pages 1-26, September.
    19. Luo, Ding & Cats, Oded & van Lint, Hans & Currie, Graham, 2019. "Integrating network science and public transport accessibility analysis for comparative assessment," Journal of Transport Geography, Elsevier, vol. 80(C).
    20. Amirhassan Kermanshah & Sybil Derrible, 2017. "Robustness of road systems to extreme flooding: using elements of GIS, travel demand, and network science," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 86(1), pages 151-164, March.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:plo:pone00:0155320. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.