Graph/network reduction based on communicability vertex similarity

Grass-Boada, D. H., de la Nuez, R., Estrada, E.
Submitted (2025)

Graph reduction aims to generate smaller graph datasets while retaining essential structural and dynamical features of the original networks.We propose a reduction technique that merges pairs of similar vertices using measures based on communicability cosine distance, which has been proven effective in distinguishing non-automorphic vertices. The method produces substantially
smaller graphs—in terms of both nodes and edges—that closely reproduce key spectral parameters of the Laplacian and adjacency matrices, directly linked to dynamical behavior under diffusion, synchronization (Kuramoto model), and epidemic spreading (Susceptible-Infected- Susceptible model). We benchmark our approach against seven state-of-the-art coarse-graining methods, demonstrating superior performance across these spectral measures. The analysis includes diverse real-world networks spanning multiple complex systems. A detailed case study illustrates the method’s application, highlights potential computational bottlenecks, and outlines directions for further improvement.

This web uses cookies for data collection with a statistical purpose. If you continue Browse, it means acceptance of the installation of the same.


Més informació D'accord