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, referred to as blocks. 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 the detection of node clusters in synthetic block-cyclic or block-acyclic graphs, including methods based on blockmodels, bibliometric symmetrization and random walks. In particular, we demonstrate the ability of our algorithms to focus on the cyclic or the acyclic patterns of connection in directed graphs, even in the presence of edges that perturb these patterns. 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.