# scg-method

##### Spectral Coarse Graining

Functions to perform the Spectral Coarse Graining (SCG) of matrices and graphs.

- Keywords
- graphs

##### Introduction

The SCG functions provide a framework, called
Spectral Coarse Graining (SCG), for reducing large graphs while preserving
their *spectral-related features*, that is features closely related
with the eigenvalues and eigenvectors of a graph matrix (which for now can
be the adjacency, the stochastic, or the Laplacian matrix).

Common examples of such features comprise the first-passage-time of random walkers on Markovian graphs, thermodynamic properties of lattice models in statistical physics (e.g. Ising model), and the epidemic threshold of epidemic network models (SIR and SIS models).

SCG differs from traditional clustering schemes by producing a
*coarse-grained graph* (not just a partition of the vertices),
representative of the original one. As shown in [1], Principal Component
Analysis can be viewed as a particular SCG, called *exact SCG*, where
the matrix to be coarse-grained is the covariance matrix of some data set.

SCG should be of interest to practitioners of various fields dealing with problems where matrix eigenpairs play an important role, as for instance is the case of dynamical processes on networks.

##### References

D. Morton de Lachapelle, D. Gfeller, and P. De Los Rios,
Shrinking Matrices while Preserving their Eigenpairs with Application to the
Spectral Coarse Graining of Graphs. Submitted to *SIAM Journal on
Matrix Analysis and Applications*, 2008.
http://people.epfl.ch/david.morton

D. Gfeller, and P. De Los Rios, Spectral Coarse Graining and Synchronization
in Oscillator Networks. *Physical Review Letters*, **100**(17),
2008. http://arxiv.org/abs/0708.2055

D. Gfeller, and P. De Los Rios, Spectral Coarse Graining of Complex
Networks, *Physical Review Letters*, **99**(3), 2007.
http://arxiv.org/abs/0706.0812

*Documentation reproduced from package igraph, version 1.2.3, License: GPL (>= 2)*