C-Blondel: An Efficient Louvain-Based Dynamic Community Detection Algorithm

Seifikar, Mahsa; Farzi, Saeed; Barati, Masoud

Abstract

One of the most interesting topics in the scope of social network analysis is dynamic community detection, keeping track of communities' evolutions in a dynamic network. This article introduces a new Louvain-based dynamic community detection algorithm relied on the derived knowledge of the previous steps of the network evolution. The algorithm builds a compressed graph, where its supernodes represent the detected communities of the previous step and its superedges show the edges among the supernodes. The algorithm not only constructs the compressed graph with low computational complexity but also detects the communities through the integration of the Louvain algorithm into the graph. The efficiency of the proposed algorithms is widely investigated in this article. By doing so, several evaluations have been performed over three standard real-world data sets, namely Enron Email, Cit-HepTh, and Facebook data sets. The obtained results indicate the superiority of the proposed algorithm with respect to the execution time as an efficiency metric. Likewise, the results show the modularity of the proposed algorithm as another effectiveness metric compared with the other well-known related algorithms.

• Journal Article Type: Article
• Acceptance Date: Dec 21, 2019
• Online Publication Date: Feb 4, 2020
• Publication Date: 2020-04
• Deposit Date: May 4, 2021
• Journal: IEEE Transactions on Computational Social Systems
• Electronic ISSN: 2329-924X
• Publisher: Institute of Electrical and Electronics Engineers
• Peer Reviewed: Peer Reviewed
• Volume: 7
• Issue: 2
• Pages: 308-318
• DOI: https://doi.org/10.1109/tcss.2020.2964197
• Keywords: Community detection, dynamic community detection, large-scale network analysis, Louvain algorithm
• Public URL: http://researchrepository.napier.ac.uk/Output/2767165