(412b) Coarse-Graining the Dynamics of Network Evolution: An Equation-Free Approach and Perspectives Using Data Mining

Complex dynamic systems, exhibiting emergent dynamics, often arise in the form of graphs (or networks): the internet, social networks, communication networks, chemical and biochemical reaction networks, and so on. We focus on the dynamics of evolving networks, i.e., networks whose connectivity changes dynamically. In such systems, coarse-graining approaches are essential in helping us understand the interplay between the structure and the dynamics of networks.

In this work, we propose a coarse-graining approach [1] based on the equation-free framework: short bursts of detailed network evolution simulations are coupled with lifting and restriction operators that translate between actual network realizations and their (appropriately chosen) coarse observables. This framework is used to accelerate temporal simulations (through coarse projective integration), and implement coarse-grained fixed point algorithms (through matrix-free Newton-Krylov GMRES) in a simple network evolution example. We also discuss the choice of good observables when the network is heterogeneous (its nodes are not identical).

A crucial step in our coarse-graining approach is a judicious selection of coarse variables for the problem at hand. This step is usually carried out heuristically. We explore the possibility of automating this step by using data mining procedures like Diffusion Maps [2] to "extract” the intrinsic parameters (coarse variables) of the system making use of data (graphs) collected either empirically or from a model simulating the dynamical process. We present such data mining results using illustrative families of graphs.

References

[1] Bold, K. A., Rajendran, K.,  Ráth, B. and Kevrekidis, I. G., An equation-free approach to coarse-graining the dynamics of networks, arXiv:1202.5618 (2012).
[2] Nadler, B., Lafon, S., Coifman, R. R. and Kevrekidis, I. G., Diffusion maps, spectral clustering and reaction coordinates of dynamical systems, Applied and Computational Harmonic Analysis, 21, 113 – 127 (2006).