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

摘要

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.