Spectral clustering algorithms for the detection of clusters in block-cyclic and block-acyclic graphs

DOI10.1093/COMNET/CNY011zbMATH Open1462.05333arXiv1805.00862OpenAlexW2798656189WikidataQ115000068 ScholiaQ115000068MaRDI QIDQ3388948FDOQ3388948

Authors: Hadrien Van Lierde, Jean-Charles Delvenne, Tommy W. S. Chow 

Publication date: 7 May 2021

Published in: Journal of Complex Networks (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1805.00862

Recommendations

• Clustering and community detection in directed networks: a survey
• Automatic determination of clusters
• Spectral redemption in clustering sparse networks
• Detecting community structure in directed networks via multiple eigenvectors
• Koopman-based spectral clustering of directed and time-evolving graphs

zbMATH Keywords

spectral clusteringcomplex networksdirected graphstochastic blockmodelacyclic graphcyclic graph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Paths and cycles (05C38) Random walks on graphs (05C81)

Cited In (5)

• A fast permuation-based algorithm for block clustering
• A graph spectrum based geometric biclustering algorithm
• Spectral complexity of directed graphs and application to structural decomposition
• Co-clustering directed graphs to discover asymmetries and directional communities
• Koopman-based spectral clustering of directed and time-evolving graphs

This page was built for publication: Spectral clustering algorithms for the detection of clusters in block-cyclic and block-acyclic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3388948)