IDEAS home Printed from https://ideas.repec.org/a/spr/ijsaem/v12y2021i2d10.1007_s13198-020-01048-w.html
   My bibliography  Save this article

Community detection in dynamic networks: a comprehensive and comparative review using external and internal criteria

Author

Listed:
  • Namika Makhija

    (Heinz College, Carnegie Mellon University)

  • Shashank Mouli Satapathy

    (Vellore Institute of Technology)

Abstract

Context: The world is experiencing a boom of data throughout several fields such as finance, engineering, medicine, crime and security etc. More and more problems associated with these fields are starting to be modeled using networks and dynamic and/or static graphs. This has led to further exploration of these graphs, their community structures and the associated community detection methods. Objective: This paper aims at studying a set of community detection approaches and analyzing their performance in terms of both external and internal criteria, including rand index, adjusted rand index, variation of information and normalized mutual information. Method: The chosen set of algorithms is thoroughly studied. Amongst this set, each algorithm is compared with the other in the set and the result is recorded numerically. These numerical values are recorded in a tabular format for better understanding of the reader. Each table is made specific to the criterion used to compare the algorithms. Altogether, a total of 4 tables are obtained for each of the metric used for the comparative analysis. Results: On comparing the algorithms with each other, the results are tabulated in a symmetric matrix whose values along the diagonal have an associated significance, which is described in the following sections. Conclusion: This paper presents a comparative analysis of the community detection algorithms against a set of external and internal criteria. Further, it lists some challenges faced by the research community in the study of these algorithms. The last section gives a summary of the common applications of community structure and detection methods.

Suggested Citation

  • Namika Makhija & Shashank Mouli Satapathy, 2021. "Community detection in dynamic networks: a comprehensive and comparative review using external and internal criteria," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 12(2), pages 217-230, April.
    • Handle: RePEc:spr:ijsaem:v:12:y:2021:i:2:d:10.1007_s13198-020-01048-w
    DOI: 10.1007/s13198-020-01048-w
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s13198-020-01048-w
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s13198-020-01048-w?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Xuzhen Zhu & Yang Tian & Hui Tian, 2014. "Link Prediction in Complex Network via Penalizing Noncontribution Relations of Endpoints," Mathematical Problems in Engineering, Hindawi, vol. 2014, pages 1-8, November.
    2. Chen, Jiancong & Zhang, Huiling & Guan, Zhi-Hong & Li, Tao, 2012. "Epidemic spreading on networks with overlapping community structure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(4), pages 1848-1854.
    3. Fei Tan & Yongxiang Xia & Boyao Zhu, 2014. "Link Prediction in Complex Networks: A Mutual Information Perspective," PLOS ONE, Public Library of Science, vol. 9(9), pages 1-8, September.
    4. Marcel Salathé & James H Jones, 2010. "Dynamics and Control of Diseases in Networks with Community Structure," PLOS Computational Biology, Public Library of Science, vol. 6(4), pages 1-11, April.
    Full references (including those not matched with items on IDEAS)

    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. Shang, Jiaxing & Liu, Lianchen & Li, Xin & Xie, Feng & Wu, Cheng, 2015. "Epidemic spreading on complex networks with overlapping and non-overlapping community structure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 419(C), pages 171-182.
    2. Gregory, Steve, 2012. "Ordered community structure in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(8), pages 2752-2763.
    3. Wei Zhong, 2017. "Simulating influenza pandemic dynamics with public risk communication and individual responsive behavior," Computational and Mathematical Organization Theory, Springer, vol. 23(4), pages 475-495, December.
    4. Chen, Dandan & Zheng, Muhua & Zhao, Ming & Zhang, Yu, 2018. "A dynamic vaccination strategy to suppress the recurrent epidemic outbreaks," Chaos, Solitons & Fractals, Elsevier, vol. 113(C), pages 108-114.
    5. Shang, Jiaxing & Liu, Lianchen & Li, Xin & Xie, Feng & Wu, Cheng, 2016. "Targeted revision: A learning-based approach for incremental community detection in dynamic networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 443(C), pages 70-85.
    6. Bowen Yan & Steve Gregory, 2013. "Identifying Communities and Key Vertices by Reconstructing Networks from Samples," PLOS ONE, Public Library of Science, vol. 8(4), pages 1-14, April.
    7. Zhou, Bin & Yan, Xiao-Yong & Xu, Xiao-Ke & Xu, Xiao-Ting & Wang, Nianxin, 2018. "Evolutionary of online social networks driven by pareto wealth distribution and bidirectional preferential attachment," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 507(C), pages 427-434.
    8. Eugenio Valdano & Chiara Poletto & Armando Giovannini & Diana Palma & Lara Savini & Vittoria Colizza, 2015. "Predicting Epidemic Risk from Past Temporal Contact Data," PLOS Computational Biology, Public Library of Science, vol. 11(3), pages 1-19, March.
    9. Saxena, Chandni & Doja, M.N. & Ahmad, Tanvir, 2018. "Group based centrality for immunization of complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 508(C), pages 35-47.
    10. Stephen J Gilmore, 2011. "Control Strategies for Endemic Childhood Scabies," PLOS ONE, Public Library of Science, vol. 6(1), pages 1-14, January.
    11. Kotnis, Bhushan & Kuri, Joy, 2016. "Cost effective campaigning in social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 450(C), pages 670-681.
    12. Kathrin Büttner & Joachim Krieter & Arne Traulsen & Imke Traulsen, 2013. "Efficient Interruption of Infection Chains by Targeted Removal of Central Holdings in an Animal Trade Network," PLOS ONE, Public Library of Science, vol. 8(9), pages 1-12, September.
    13. Namtirtha, Amrita & Dutta, Animesh & Dutta, Biswanath, 2018. "Identifying influential spreaders in complex networks based on kshell hybrid method," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 499(C), pages 310-324.
    14. Shakibian, Hadi & Charkari, Nasrollah Moghadam, 2018. "Statistical similarity measures for link prediction in heterogeneous complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 501(C), pages 248-263.
    15. Jose L Herrera & Ravi Srinivasan & John S Brownstein & Alison P Galvani & Lauren Ancel Meyers, 2016. "Disease Surveillance on Complex Social Networks," PLOS Computational Biology, Public Library of Science, vol. 12(7), pages 1-16, July.
    16. Guan, Yuan-Pan & You, Zhi-Qiang & Han, Xiao-Pu, 2016. "Reconstruction of social group networks from friendship networks using a tag-based model," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 463(C), pages 485-492.
    17. Shams, Bita & Khansari, Mohammad, 2015. "On the impact of epidemic severity on network immunization algorithms," Theoretical Population Biology, Elsevier, vol. 106(C), pages 83-93.
    18. Karikalan Nagarajan & Bharathidasan Palani & Javeed Basha & Lavanya Jayabal & Malaisamy Muniyandi, 2022. "A social networks-driven approach to understand the unique alcohol mixing patterns of tuberculosis patients: reporting methods and findings from a high TB-burden setting," Palgrave Communications, Palgrave Macmillan, vol. 9(1), pages 1-8, December.
    19. Chi, Kuo & Qu, Hui & Yin, Guisheng, 2022. "Link prediction for existing links in dynamic networks based on the attraction force," Chaos, Solitons & Fractals, Elsevier, vol. 159(C).
    20. Gong Kai & Kang Li, 2018. "A New K-Shell Decomposition Method for Identifying Influential Spreaders of Epidemics on Community Networks," Journal of Systems Science and Information, De Gruyter, vol. 6(4), pages 366-375, August.

    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:spr:ijsaem:v:12:y:2021:i:2:d:10.1007_s13198-020-01048-w. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.