View article

Spectral clustering (SC) is a popular approach for gaining insights from complex networks. Conventional SC focuses on second-order structures (e.g. edges) without direct consideration of higher-order structures (e.g. triangles). This has motivated SC extensions that directly consider higher-order structures. However, both approaches are limited to considering a single order. To address this issue, this paper proposes a novel Mixed-Order Spectral Clustering (MOSC) framework to model both second-order and third-order structures simultaneously. To model mixed-order structures, we propose two new methods based on Graph Laplacian (GL) and Random Walks (RW). MOSC-GL combines edge and triangle adjacency matrices, with theoretical performance guarantee. MOSC-RW combines first-order and second-order random walks for a probabilistic interpretation. Moreover, we design mixed-order cut criteria to …