SCS: A Structural Similarity Measure for Graph Clustering Based on Cycles and Paths

With the continuous development of business intelligence and scientific exploration, graphs have been extensively applied to various fields. Graph clustering has emerged as a crucial task for mining the structure and function of complex networks. However, existing clustering algorithms often overly emphasize the density and degree of vertices in the graph while neglecting the correlations and structural characteristics among vertices, resulting in poor performance when clustering graphs. In this paper, we propose a novel method called Structural and Cyclic Similarity (SCS) for structural graph clustering, aiming to improve the quality of clustering. Our method utilizes short-length cycles and paths, which are common graph motifs, to comprehensively capture the neighborhoods and graph motifs of connected vertices. This enables us to quantify the similarity between vertices effectively. The SCS is then applied to structural graph clustering algorithms, thereby improving the clustering quality. To efficiently compute the SCS, we give an algorithm of subgraph counting, which rapidly counts all short-length cycles in the graph. Experimental results conducted on six real-world datasets demonstrate that the clustering algorithm based on SCS outperforms other similarity measures in terms of clustering quality and can improve the effectiveness of graph clustering.