Index-based Structural Clustering on Directed Graphs

Lingkai Meng, Long Yuan, Zi Chen, Xuemin Lin, Shiyu Yang

20222022 IEEE 38th International Conference on Data Engineering (ICDE)18 citationsDOI

Abstract

Structural clustering (SCAN) is one of the most popular graph clustering paradigms. However, SCAN assumes that the input graph is undirected and can not cluster the directed graphs. To address this problem, in this paper, we propose a new structural clustering model based on SCAN to cluster directed graphs. Following the new model, we propose an index-based approach to support the efficient clustering of a given graph. Moreover, we also devise efficient index maintenance algorithms to handle the case that the input graph is dynamically updated. We conduct extensive experiments on nine real directed graphs, one of which contains more than 2 billion edges. The results demonstrate the effectiveness and efficiency of our proposed methods.

Topics & Concepts

Cluster analysisComputer scienceClustering coefficientDirected graphGraphTheoretical computer scienceIndex (typography)Data miningCorrelation clusteringGraph theoryAlgorithmArtificial intelligenceMathematicsCombinatoricsWorld Wide WebComplex Network Analysis TechniquesAdvanced Clustering Algorithms ResearchAdvanced Graph Neural Networks