Spectral clustering algorithms for the detection of clusters in block-cyclic and block-acyclic graphs
This work addresses the challenge of clustering directed graphs for applications like ecological networks and internet infrastructure, representing an incremental improvement over existing spectral and blockmodel methods.
The authors tackled the problem of partitioning nodes in directed graphs with cyclic and acyclic connection patterns by proposing two spectral algorithms based on extremal eigenvalues of the transition matrix. Their methods outperformed state-of-the-art approaches on synthetic datasets and were successfully applied to real-world networks, such as a trophic predator-prey network and an Autonomous Systems network, to extract meaningful structures.
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.