An equation-free approach to coarse-graining the dynamics of networks

Katherine A. Bold; Karthikeyan Rajendran; Balázs Ráth; Ioannis G. Kevrekidis

doi:10.3934/jcd.2014.1.111

Article Contents

2014, Volume 1, Issue 1: 111-134. Doi: 10.3934/jcd.2014.1.111

This issue Previous Article Continuation and collapse of homoclinic tangles Next Article A closing scheme for finding almost-invariant sets in open dynamical systems

An equation-free approach to coarse-graining the dynamics of networks

1.
Program in Applied and Computational Mathematics (PACM), Princeton University, Princeton, New Jersey 08544
2.
Department of Chemical and Biological Engineering, Princeton University, Princeton, New Jersey 08544
3.
Institute of Mathematics, Budapest University of Technology (BME), H-1111 Budapest
4.
Department of Chemical and Biological Engineering, and Program in Applied and Computational Mathematics, Princeton University, Princeton, NJ 08544

Received: February 2012

Revised: October 2012

Published online: April 2014

Abstract / Introduction Related Papers Cited by

Abstract

We propose and illustrate an approach to coarse-graining the dynamics of evolving networks, i.e., networks whose connectivity changes dynamically. The approach is 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 here to accelerate temporal simulations through coarse projective integration, and to implement coarse-grained fixed point algorithms through matrix-free Newton-Krylov. The approach is illustrated through a very simple network evolution example, for which analytical approximations to the coarse-grained dynamics can be independently obtained, so as to validate the computational results. The scope and applicability of the approach, as well as the issue of selection of good coarse observables are discussed.

Keywords:

Mathematics Subject Classification: Primary: 68U20, 37E25; Secondary: 65Z05.

Citation:

Related Papers

Cited by

References

[1]	R. Albert and A. L. Barabási, Statistical mechanics of complex networks, Rev. Mod. Phys., 74 (2002), 47-97.doi: 10.1103/RevModPhys.74.47.
[2]	A. Arenas, A. Díaz-Guilera and C. J. Pérez-Vicente, Synchronization reveals topological scales in complex networks, Phys. Rev. Lett., 96 (2006), 114102.doi: 10.1103/PhysRevLett.96.114102.
[3]	A. L. Barabási and R. Albert, Emergence of scaling in random networks, Science, 286 (1999), 509-512.doi: 10.1126/science.286.5439.509.
[4]	A. Barrat, M. Barthelemy and A. Vespignani, Dynamical Processes on Complex Networks, Cambridge University Press, 2008.doi: 10.1017/CBO9780511791383.
[5]	T. Binzegger, R. J. Douglas and K. A. C. Martin, Topology and dynamics of the canonical circuit of cat v1, Neural Networks, 22 (2009), 1071-1078.doi: 10.1016/j.neunet.2009.07.011.
[6]	J. Blitzstein and P. Diaconis, A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees, Technical report, 2006. Available from: http://www.people.fas.harvard.edu/~blitz/BlitzsteinDiaconisGraphAlgorithm.pdf.doi: 10.1080/15427951.2010.557277.
[7]	S. Boccaletti, V. Latora, Y. Moreno, M. Chavez and D.-U. Hwang, Complex networks: Structure and dynamics, Physics Reports, 424 (2006), 175-308.doi: 10.1016/j.physrep.2005.10.009.
[8]	K. A. Bold, Y. Zou, I. G. Kevrekidis and M. A. Hensonevrekidis, An equation-free approach to analyzing heterogeneous cell population dynamics, J. Math. Biol., 55 (2007), 331-352.doi: 10.1007/s00285-007-0086-6.
[9]	B. Bollobas, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, European J. Combin., 1 (1980), 311-316.doi: 10.1016/S0195-6698(80)80030-8.
[10]	C. Borgs, J. Chayes, L. Lovász, V. Sós and K. Vesztergombi, Topics in Discrete Mathematics: Algorithms and Combinatorics, Springer, Berlin, 2006.
[11]	L. Chen, P. G. Debenedetti, C. W. Gear and I. G. Kevrekidis, From molecular dynamics to coarse self-similar solutions: a simple example using equation-free computation, J. Non-Newton Fluid, 120 (2004), 215-223.doi: 10.1016/j.jnnfm.2003.12.007.
[12]	F. Chung and L. Lu, Connected components in random graphs with given expected degree sequences, Ann. Comb., 6 (2002), 125-145.doi: 10.1007/PL00012580.
[13]	S. N. Dorogovtsev, J. F. F. Mendes and A. N. Samukhin, How to construct a correlated net, eprint, arXiv:cond-mat/0206131.
[14]	S. N. Dorogovtsev and J. F. F. Mendes, Evolution of networks, Adv. Phys., 51 (2002), 1079-1187.doi: 10.1093/acprof:oso/9780198515906.001.0001.
[15]	M. Faloutsos, P. Faloutsos and C. Faloutsos, On power-law relationships of the internet topology, In SIGCOMM, (1999), 251-262.doi: 10.1145/316194.316229.
[16]	C. Gounaris, K. Rajendran, I. G. Kevrekidis and C. Floudas, Generation of networks with prescribed degree-dependent clustering, Optim. Lett., 5 (2011), 435-451.doi: 10.1007/s11590-011-0319-x.
[17]	T. Gross and I. G. Kevrekidis, Robust oscillations in SIS epidemics on adaptive networks: Coarse graining by automated moment closure, Europhys. Lett., 82 (2008), 38004, 6 pp.doi: 10.1209/0295-5075/82/38004.
[18]	S. L. Hakimi, On realizability of a set of integers as degrees of the vertices of a linear graph. I, J. Soc. Ind. Appl. Math., 10 (1962), 496-506.doi: 10.1137/0110037.
[19]	V. Havel, A remark on the existence of finite graphs. (czech), Casopis Pest. Mat., 80 (1955), 477-480.
[20]	M. Ispány and G. Pap, A note on weak convergence of random step processes, Acta Mathematica Hungarica, 126 (2010), 381-395.doi: 10.1007/s10474-009-9099-5.
[21]	C. T. Kelley, Iterative Methods for Linear and Nonlinear Equations, number 16 in Frontiers in Applied Mathematics, SIAM, Philadelphia, 1995.doi: 10.1137/1.9781611970944.
[22]	I. G. Kevrekidis, C. W. Gear and G. Hummer, Equation-free: The computer-aided analysis of complex multiscale systems, AIChE Journal, 50 (2004), 1346-1355.doi: 10.1002/aic.10106.
[23]	I. G. Kevrekidis, C. W. Gear, J. M. Hyman, P. G. Kevrekidis, O. Runborg and C. Theodoropoulos, Equation-free, coarse-grained multiscale computation: Enabling microscopic simulators to perform system-level analysis, Commun. Math. Sci., 1 (2003), 715-762.doi: 10.4310/CMS.2003.v1.n4.a5.
[24]	I. G. Kevrekidis and G. Samaey, Equation-free multiscale computation: Algorithms and applications, Annu. Rev. Phys. Chem., 60 (2009), 321-344.doi: 10.1146/annurev.physchem.59.032607.093610.
[25]	B. J. Kim, Performance of networks of artificial neurons: The role of clustering, Phys. Rev. E, 69 (2004), 045101.doi: 10.1103/PhysRevE.69.045101.
[26]	S. Lafon and A. B. Lee, Diffusion maps and coarse-graining: A unified framework for dimensionality reduction, graph partitioning and data set parameterization, IEEE T. Pattern Anal., 28 (2006), 1393-1403.doi: 10.1109/TPAMI.2006.184.
[27]	C. R. Laing, The dynamics of chimera states in heterogeneous kuramoto networks, Physica D, 238 (2009), 1569-1588.doi: 10.1016/j.physd.2009.04.012.
[28]	P. Li and Z. Yi, Synchronization of Kuramoto oscillators in random complex networks, Physica A, 387 (2008), 1669-1674.doi: 10.1016/j.physa.2007.11.008.
[29]	L. Lovász, Very large graphs, eprint, arXiv:0902.0132.
[30]	L. Lovász and B. Szegedy, Limits of dense graph sequences, J. Comb. Theory Ser. B, 96 (2006), 933-957.doi: 10.1016/j.jctb.2006.05.002.
[31]	S. J. Moon, B. Nabet, N. E. Leonard, S. A. Levin and I. G. Kevrekidis, Heterogeneous animal group models and their group-level alignment dynamics: An equation-free approach, J. Theor. Biol., 246 (2007), 100-112.doi: 10.1016/j.jtbi.2006.12.018.
[32]	F. Mori and T. Odagaki, Synchronization of coupled oscillators on small-world networks, Physica D, 238 (2009), 1180-1185.doi: 10.1016/j.physd.2009.04.002.
[33]	B. Nadler, S. Lafon, R. R. Coifman and I. G. Kevrekidis, Diffusion maps, spectral clustering and reaction coordinates of dynamical systems, Appl. Comput. Harmon. A., 21 (2006), 113-127.doi: 10.1016/j.acha.2005.07.004.
[34]	M. E. J. Newman, The structure and function of complex networks, SIAM Review, 45 (2003), 167-256.doi: 10.1137/S003614450342480.
[35]	M. E. J. Newman, D. J. Watts and S. H. Strogatz, Random graph models of social networks, Proc. Natl. Acad. Sci., 1 (2002), 2566-2572.doi: 10.1073/pnas.012582999.
[36]	M. E. J. Newman, A. L. Barabási and D. J. Watts, The Structure and Dynamics of Networks, Princeton University Press, 2006.
[37]	K. Rajendran and I. G. Kevrekidis, Coarse graining the dynamics of heterogeneous oscillators in networks with spectral gaps, Phys. Rev. E, 84 (2011), 036708.doi: 10.1103/PhysRevE.84.036708.
[38]	Y. Saad and M. H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comp., 7 (1986), 856-869.doi: 10.1137/0907058.
[39]	M. A. Serrano and M. Boguná, Tuning clustering in random networks with arbitrary degree distributions, Phys. Rev. E, 72 (2005), 036133.
[40]	R. Toivonen, L. Kovanen, M. Kivelä, J. Onnela, J. Saramäki and K. Kaski, A comparative study of social network models: Network evolution models and nodal attribute models, Soc. Networks, 31 (2009), 240-254.doi: 10.1016/j.socnet.2009.06.004.
[41]	S. V. N. Vishwanathan, K. M. Borgwardt, I. Risi Kondor and N. N. Schraudolph, Graph Kernels, eprint, arXiv:0807.0093.
[42]	D. J. Watts and S. H. Strogatz, Collective dynamics of ‘small-world' networks, Nature, 393 (1998), 440-442.
[43]	N. C. Wormald, Some problems in the enumeration of labelled graphs, B. Aust. Math. Soc., 21 (1980), 159-160.doi: 10.1017/S0004972700011436.