Spectral clustering algorithms for directed graphs

Details

Supervisors

Delvenne, Jean-Charles

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] : ingénieur civil en mathématiques appliquées

Abstract

In this report, we present three spectral algorithms for partitioning nodes in directed graphs respectively with a cyclic and an acyclic pattern of connection between groups of nodes. These methods are based on the definition of an asymmetric graph-related matrix which is a generalization of the symmetric Laplacian of undirected graphs. The partitioning of nodes is extracted from the complex spectrum of this matrix. One of the methods is applied to three real-world networks. It successfully defines a ranking of football teams based on their scores. When applied to a food chain, it extracts common categories of preys and predators. Finally, it highlights the hierarchical structure of the network of exchange of information between internet service providers around the world. We also provide details about how to implement the methods on large-scale networks and we conduct tests on synthetic datasets to analyse the sensitivity of the algorithms in the presence of perturbations.