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.
In this paper, we generalize a recently introduced expectation maximization EM method for graphs and apply it to content-based networks. The EM method provides a classification of the nodes of a graph, and allows one to infer relations between the different classes. Content-based networks are ideal models for graphs displaying any kind of community and or multipartite structure. We show both numerically and analytically that the generalized EM method is able to recover the process that led to the generation of such networks. We also investigate the conditions under which our generalized EM method can recover the underlying contentbased structure in the presence of randomness in the connections. Two entropies, Sq and Sc, are defined to measure the quality of the node classification and to what extent the connectivity of a given network is content based. Sq and Sc are also useful in determining the number of classes for which the classification is optimal.