Using fast intersection to improve SCAN algorithm

Abstract

The structural graph clustering is considered in this paper. Given a graph G = (V, E) and parameters 0 < ϵ < 0 and μ ≥ 2, we want to efficiently assign vertices in V to clusters such that vertices from the same cluster are densely connected and vertices from different clusters are loosely connected. SCAN algorithm is a standard approach to solve this problem. However, SCAN has an expensive computation cost. In this paper, we propose an improved version of SCAN and reduce computation time in the similarity calculation step. We use simple calculation for edges that connect to a leaf node. For the remaining edges, we adopt the fast intersection algorithm of Baeza-Yates and Salinger. We validate our algorithm with real network datasets. Our algorithm outperforms SCAN for any parameters and pSCAN for small μ.