An efficient graph clustering algorithm by exploiting k-core decomposition and motifs. (December 2021)

• Record Type: Journal Article
• Authors: Mei, Gang; Tu, Jingzhi; Xiao, Lei; Piccialli, Francesco
• Is Part Of: Computers & electrical engineering. Volume 96:Part B(2021)
• Publication Date: 2021-12
• Subjects: Machine Learning -- Clustering -- Spectral clustering -- Graph -- k-core decomposition -- Network structure; Computer engineering -- Periodicals; Electrical engineering -- Periodicals; Electrical engineering -- Data processing -- Periodicals; Ordinateurs -- Conception et construction -- Périodiques; Électrotechnique -- Périodiques; Électrotechnique -- Informatique -- Périodiques; Computer engineering; Electrical engineering; Electrical engineering -- Data processing; Periodicals; Electronic journals; 621.302854
• DOI: 10.1016/j.compeleceng.2021.107564
• Languages: English
• ISSNs: 0045-7906

Abstract

Abstract: 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. Graphical abstract: