A generalized incremental bottom-up community detection framework for highly dynamic graphs

Abstract

How to efficiently detect communities for dynamic graphs has attracted significant attention due to its widespread applications, such as 'Recommended System' in social networking or 'Anti-Money Laundry' for banks. However, with the growing size and the increasing of changing frequency for dynamic graphs, it is better to detect communities incrementally than applying community detection algorithm for each of the graph. In this paper, we propose a generalized bottom-up community detection framework to help standard community detection algorithms to detect communities in highly dynamic graphs incrementally. The evaluations on real data sets show that our generalized framework does have the ability to accelerate standard community detection methods for highly dynamic graphs (up to 96%). In addition, for super hubs in large scale graph, we also propose an approximate process to meet the requirement of real-time processing. By giving 'mathematical proof', 'efficiency' and 'accuracy' evaluations from real data sets, we demonstrate this approximate process can not only accelerate the community detection process but also can preserve the accuracy, as the normalized mutual information for regular communities and approximate communities is larger than 92%.