An efficient graph clustering algorithm by exploiting k-core decomposition and motifs

Clustering analysis has been widely used in trust evaluation for various complex networks such as wireless sensor networks and online social networks. Spectral clustering is one of the most commonly used algorithms for graph-structured data (networks). However, conventional spectral clustering is inherently difficult to perform in large networks. In this paper, we proposed an efficient graph clustering algorithm, KCoreMotif, specifically for large networks by exploiting k-core decomposition and motifs. We first conducted the k-core decomposition of the large input network, then performed the motif-based spectral clustering for the top k-core subgraphs, and finally grouped the remaining vertices in the rest (k-1)-core subgraphs into previously found clusters to obtain the final clusters. Comparative results of 18 groups of real-world datasets demonstrated that KCoreMotif was accurate yet efficient for large networks, which also means it can be further used to evaluate the intra-cluster and inter-cluster trusts for large networks.