Spectral clustering algorithms for the detection of clusters in block-cyclic and block-acyclic graphs
We propose two spectral algorithms for partitioning nodes in directed graphs respectively with a cyclic and an acyclic pattern of connection between groups of nodes. Our methods are based on the computation of extremal eigenvalues of the transition matrix associated to the directed graph. The two algorithms outperform state-of-the art methods for directed graph clustering on synthetic datasets, including methods based on blockmodels, bibliometric symmetrization and random walks. Our algorithms have the same space complexity as classical spectral clustering algorithms for undirected graphs and their time complexity is also linear in the number of edges in the graph. One of our methods is applied to a trophic network based on predator-prey relationships. It successfully extracts common categories of preys and predators encountered in food chains. The same method is also applied to highlight the hierarchical structure of a worldwide network of Autonomous Systems depicting business agreements between Internet Service Providers.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringGraph ClusteringSimilar Papers 제목 키워드 기반
On Consistency of Compressive Spectral Clustering
Spectral clustering is one of the most popular methods for community detection in graphs. A key step in spectral clustering algorithms is the eigen decomposition of the $n{\times}n$ graph Laplacian matrix to extract its …
ClusteringCommunity DetectionStochastic Block ModelEstimating the number of clusters of a Block Markov Chain
Clustering algorithms frequently require the number of clusters to be chosen in advance, but it is usually not clear how to do this. To tackle this challenge when clustering within sequential data, we present a method fo…
ClusteringStochastic Block ModelAn improved spectral clustering method for community detection under the degree-corrected stochastic blockmodel
For community detection problem, spectral clustering is a widely used method for detecting clusters in networks. In this paper, we propose an improved spectral clustering (ISC) approach under the degree corrected stochas…
ClusteringCommunity DetectionStochastic Block ModelAnalysis of spectral clustering algorithms for community detection: the general bipartite setting
We consider spectral clustering algorithms for community detection under a general bipartite stochastic block model (SBM). A modern spectral clustering algorithm consists of three steps: (1) regularization of an appropri…
ClusteringCommunity DetectionStochastic Block ModelOn consistency of constrained spectral clustering under representation-aware stochastic block model
Spectral clustering is widely used in practice due to its flexibility, computational efficiency, and well-understood theoretical performance guarantees. Recently, spectral clustering has been studied to find balanced clu…
ClusteringComputational EfficiencyStochastic Block Model