Incremental structural clustering for dynamic networks

Graph clustering is a fundamental tool for revealing cohesive structures in networks. The structural clustering algorithm for networks (\mathsf {SCAN}) is an important approach for this task, which has attracted much attention in recent years. The \mathsf {SCAN} algorithm can not only use to identify cohesive structures, but it is also able to detect outliers and hubs in a static network. Most real-life networks, however, frequently evolve over time. Unfortunately, the \mathsf {SCAN} algorithm is very costly to handle such dynamic networks. In this paper, we propose an efficient incremental structural clustering algorithm for dynamic networks, called \mathsf {ISCAN}. The \mathsf {ISCAN} algorithm can efficiently maintain the clustering structures without recomputing the clusters from scratch. We conduct extensive experiments in eight large real-world networks. The results show that our algorithm is at least three orders of magnitude faster than the baseline algorithm.