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.
The primary focus of random walk based clustering algorithms is the detection of density-based clusters @cite_30 , namely with a high number of intra-cluster edges and a low-number of inter-cluster edges. A symmetric Laplacian matrix for directed graphs based on the stationary probability distribution of a random walk is defined and applying classical spectral clustering algorithm to this Laplacian matrix leads to the extraction of clusters in which a random walker is likely to be trapped. To detect pattern-based clusters, an extension of this method was proposed in which a random walker alternatively moves forward following the directionality of edges, and backwards, in the opposite direction @cite_7 . This method successfully extracts clusters in citation-based networks. Similarly, another random walk-based approach extends the definition of directed modularity to extract clusters of densely connected nodes with a cyclic pattern of connections between clusters @cite_17 @cite_20 .
@cite_30 @cite_20 @cite_7 @cite_17
2069992656 1936027193 2963115731
We consider Laplacians for directed graphs and examine their eigenvalues. We introduce a notion of a circulation in a directed graph and its connection with the Rayleigh quotient. We then define a Cheeger constant and establish the Cheeger inequality for directed graphs. These relations can be used to deal with various problems that often arise in the study of non-reversible Markov chains including bounding the rate of convergence and deriving comparison theorems. Finding metastable sets as dominant structures of Markov processes has been shown to be especially useful in modeling interesting slow dynamics of various real world complex processes. Furthermore, coarse graining of such processes based on their dominant structures leads to better understanding and dimension reduction of observed systems. However, in many cases, e.g., for nonreversible Markov processes, dominant structures are often not formed by metastable sets but by important cycles or a mixture of both. This paper aims at understanding and identifying these different types of dominant structures for reversible as well as nonreversible ergodic Markov processes. Our algorithmic approach generalizes spectral-based methods for reversible processes by using Schur decomposition techniques which can also tackle nonreversible cases. We illustrate the mathematical construction of our new approach by numerical experiments. The problem of decomposing networks into modules (or clusters) has gained much attention in recent years, as it can account for a coarse-grained description of complex systems, often revealing functional subunits of these systems. A variety of module detection algorithms have been proposed, mostly oriented towards finding hard partitionings of undirected networks. Despite the increasing number of fuzzy clustering methods for directed networks, many of these approaches tend to neglect important directional information. In this paper, we present a novel random walk based approach for finding fuzzy partitions of directed, weighted networks, where edge directions play a crucial role in defining how well nodes in a module are interconnected. We will show that cycle decomposition of a random walk process connects the notion of network modules and information transport in a network, leading to a new, symmetric measure of node communication. Finally, we will use this measure to introduce a communication graph, for which we will show that although being undirected it inherits important directional information of modular structures from the original network.