Source-linked AI summary
Spectral coarse-graining of complex networks
David Gfeller, Paolo De los Rios
TL;DR
Large networks are difficult to analyze, and which properties a reduction should preserve remains unsettled. This paper groups nodes using random-walk eigenvectors to build smaller networks that retain slow modes; the resulting coarse-graining preserves spectral properties and closely reproduces mean first passage times in the di-alanine example.
Problem
Large network size challenges analysis, while it remains unsettled which properties a reduced network should preserve, especially because topology may not reveal internal dynamics.
Source: p. 1Method
The method groups nodes with similar components in selected left eigenvectors of the random-walk transition matrix to construct a smaller network with a spectral interpretation.
Source: pp. 1–2Results
The coarse-graining preserves the first eigenvalues and corresponding eigenvectors with high accuracy, and its mean first passage times closely overlap those of the original di-alanine network.
Source: pp. 2–3Takeaways & Limitations
The reduced network provides a representative approximation of random-walk behavior, offering a way to address the size of complex networks in analysis and visualization.
Source: p. 4
Abstract
from arXiv · showhide
Reducing the complexity of large systems described as complex networks is key to understand them and a crucial issue is to know which properties of the initial system are preserved in the reduced one. Here we use random walks to design a coarse-graining scheme for complex networks. By construction the coarse-graining preserves the slow modes of the walk, while reducing significantly the size and the complexity of the network. In this sense our coarse-graining allows to approximate large networks by smaller ones, keeping most of their relevant spectral properties.