An Incremental Method to Detect Communities in Evolving Social Networks

Detecting communities in dynamic evolving networks is of great interest. It has received tremendous attention from researchers. One promising solution is to update communities incrementally taking the historical information into consideration. However, most of the existing methods are only suitable for the case of one node adding or one edge adding. Factually, new data are always generated continuously with subgraphs joining simultaneously in dynamic evolving networks. To address the above problem, we present an incremental method to detect communities by handling subgraphs. We first make a comprehensive analysis and propose four types of incremental elements. Then we propose different updating strategies. Finally, we present the algorithms to detect communities incrementally in dynamic evolving networks. The experimental results on real-world data sets indicate that the proposed method is effective and has superior performance compared with several widely used methods.