  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.
