2014, 1(1): 111-134. doi: 10.3934/jcd.2014.1.111

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, United States

2. 

Department of Chemical and Biological Engineering, Princeton University, Princeton, New Jersey 08544, United States

3. 

Institute of Mathematics, Budapest University of Technology (BME), H-1111 Budapest, Hungary

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  April 2014

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.
Citation: Katherine A. Bold, Karthikeyan Rajendran, Balázs Ráth, Ioannis G. Kevrekidis. An equation-free approach to coarse-graining the dynamics of networks. Journal of Computational Dynamics, 2014, 1 (1) : 111-134. doi: 10.3934/jcd.2014.1.111
References:
[1]

R. Albert and A. L. Barabási, Statistical mechanics of complex networks,, Rev. Mod. Phys., 74 (2002), 47. 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). doi: 10.1103/PhysRevLett.96.114102.

[3]

A. L. Barabási and R. Albert, Emergence of scaling in random networks,, Science, 286 (1999), 509. 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. 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). 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. 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. 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. 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, (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. 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. doi: 10.1007/PL00012580.

[13]

S. N. Dorogovtsev, J. F. F. Mendes and A. N. Samukhin, How to construct a correlated net,, eprint, ().

[14]

S. N. Dorogovtsev and J. F. F. Mendes, Evolution of networks,, Adv. Phys., 51 (2002), 1079. 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. 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. 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). 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. doi: 10.1137/0110037.

[19]

V. Havel, A remark on the existence of finite graphs. (czech),, Casopis Pest. Mat., 80 (1955), 477.

[20]

M. Ispány and G. Pap, A note on weak convergence of random step processes,, Acta Mathematica Hungarica, 126 (2010), 381. 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, (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. 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. 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. 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). 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. doi: 10.1109/TPAMI.2006.184.

[27]

C. R. Laing, The dynamics of chimera states in heterogeneous kuramoto networks,, Physica D, 238 (2009), 1569. 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. doi: 10.1016/j.physa.2007.11.008.

[29]

L. Lovász, Very large graphs,, eprint, ().

[30]

L. Lovász and B. Szegedy, Limits of dense graph sequences,, J. Comb. Theory Ser. B, 96 (2006), 933. 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. 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. 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. 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. 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. 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). 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. 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).

[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. 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, ().

[42]

D. J. Watts and S. H. Strogatz, Collective dynamics of ‘small-world' networks,, Nature, 393 (1998), 440.

[43]

N. C. Wormald, Some problems in the enumeration of labelled graphs,, B. Aust. Math. Soc., 21 (1980), 159. doi: 10.1017/S0004972700011436.

show all references

References:
[1]

R. Albert and A. L. Barabási, Statistical mechanics of complex networks,, Rev. Mod. Phys., 74 (2002), 47. 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). doi: 10.1103/PhysRevLett.96.114102.

[3]

A. L. Barabási and R. Albert, Emergence of scaling in random networks,, Science, 286 (1999), 509. 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. 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). 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. 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. 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. 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, (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. 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. doi: 10.1007/PL00012580.

[13]

S. N. Dorogovtsev, J. F. F. Mendes and A. N. Samukhin, How to construct a correlated net,, eprint, ().

[14]

S. N. Dorogovtsev and J. F. F. Mendes, Evolution of networks,, Adv. Phys., 51 (2002), 1079. 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. 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. 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). 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. doi: 10.1137/0110037.

[19]

V. Havel, A remark on the existence of finite graphs. (czech),, Casopis Pest. Mat., 80 (1955), 477.

[20]

M. Ispány and G. Pap, A note on weak convergence of random step processes,, Acta Mathematica Hungarica, 126 (2010), 381. 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, (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. 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. 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. 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). 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. doi: 10.1109/TPAMI.2006.184.

[27]

C. R. Laing, The dynamics of chimera states in heterogeneous kuramoto networks,, Physica D, 238 (2009), 1569. 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. doi: 10.1016/j.physa.2007.11.008.

[29]

L. Lovász, Very large graphs,, eprint, ().

[30]

L. Lovász and B. Szegedy, Limits of dense graph sequences,, J. Comb. Theory Ser. B, 96 (2006), 933. 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. 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. 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. 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. 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. 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). 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. 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).

[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. 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, ().

[42]

D. J. Watts and S. H. Strogatz, Collective dynamics of ‘small-world' networks,, Nature, 393 (1998), 440.

[43]

N. C. Wormald, Some problems in the enumeration of labelled graphs,, B. Aust. Math. Soc., 21 (1980), 159. doi: 10.1017/S0004972700011436.

[1]

Yves Frederix, Giovanni Samaey, Christophe Vandekerckhove, Ting Li, Erik Nies, Dirk Roose. Lifting in equation-free methods for molecular dynamics simulations of dense fluids. Discrete & Continuous Dynamical Systems - B, 2009, 11 (4) : 855-874. doi: 10.3934/dcdsb.2009.11.855

[2]

Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 17-23. doi: 10.3934/era.2008.15.17

[3]

Antonios Zagaris, Christophe Vandekerckhove, C. William Gear, Tasso J. Kaper, Ioannis G. Kevrekidis. Stability and stabilization of the constrained runs schemes for equation-free projection to a slow manifold. Discrete & Continuous Dynamical Systems - A, 2012, 32 (8) : 2759-2803. doi: 10.3934/dcds.2012.32.2759

[4]

Constantinos Siettos. Equation-free computation of coarse-grained center manifolds of microscopic simulators. Journal of Computational Dynamics, 2014, 1 (2) : 377-389. doi: 10.3934/jcd.2014.1.377

[5]

Xianmin Geng, Shengli Zhou, Jiashan Tang, Cong Yang. A sufficient condition for classified networks to possess complex network features. Networks & Heterogeneous Media, 2012, 7 (1) : 59-69. doi: 10.3934/nhm.2012.7.59

[6]

Regino Criado, Rosa M. Benito, Miguel Romance, Juan C. Losada. Preface: Mesoscales and evolution in complex networks: Applications and related topics. Networks & Heterogeneous Media, 2012, 7 (3) : i-iii. doi: 10.3934/nhm.2012.7.3i

[7]

David J. Aldous. A stochastic complex network model. Electronic Research Announcements, 2003, 9: 152-161.

[8]

Noboru Okazawa, Tomomi Yokota. Subdifferential operator approach to strong wellposedness of the complex Ginzburg-Landau equation. Discrete & Continuous Dynamical Systems - A, 2010, 28 (1) : 311-341. doi: 10.3934/dcds.2010.28.311

[9]

Deena Schmidt, Janet Best, Mark S. Blumberg. Random graph and stochastic process contributions to network dynamics. Conference Publications, 2011, 2011 (Special) : 1279-1288. doi: 10.3934/proc.2011.2011.1279

[10]

Liu Hui, Lin Zhi, Waqas Ahmad. Network(graph) data research in the coordinate system. Mathematical Foundations of Computing, 2018, 1 (1) : 1-10. doi: 10.3934/mfc.2018001

[11]

András Bátkai, Istvan Z. Kiss, Eszter Sikolya, Péter L. Simon. Differential equation approximations of stochastic network processes: An operator semigroup approach. Networks & Heterogeneous Media, 2012, 7 (1) : 43-58. doi: 10.3934/nhm.2012.7.43

[12]

Mirela Domijan, Markus Kirkilionis. Graph theory and qualitative analysis of reaction networks. Networks & Heterogeneous Media, 2008, 3 (2) : 295-322. doi: 10.3934/nhm.2008.3.295

[13]

M. D. König, Stefano Battiston, M. Napoletano, F. Schweitzer. On algebraic graph theory and the dynamics of innovation networks. Networks & Heterogeneous Media, 2008, 3 (2) : 201-219. doi: 10.3934/nhm.2008.3.201

[14]

N. I. Karachalios, Hector E. Nistazakis, Athanasios N. Yannacopoulos. Asymptotic behavior of solutions of complex discrete evolution equations: The discrete Ginzburg-Landau equation. Discrete & Continuous Dynamical Systems - A, 2007, 19 (4) : 711-736. doi: 10.3934/dcds.2007.19.711

[15]

Zhen Jin, Guiquan Sun, Huaiping Zhu. Epidemic models for complex networks with demographics. Mathematical Biosciences & Engineering, 2014, 11 (6) : 1295-1317. doi: 10.3934/mbe.2014.11.1295

[16]

Robert Stephen Cantrell, Chris Cosner, Yuan Lou. Evolution of dispersal and the ideal free distribution. Mathematical Biosciences & Engineering, 2010, 7 (1) : 17-36. doi: 10.3934/mbe.2010.7.17

[17]

Alessandra Pluda. Evolution of spoon-shaped networks. Networks & Heterogeneous Media, 2016, 11 (3) : 509-526. doi: 10.3934/nhm.2016007

[18]

Chunmei Zhang, Wenxue Li, Ke Wang. Graph-theoretic approach to stability of multi-group models with dispersal. Discrete & Continuous Dynamical Systems - B, 2015, 20 (1) : 259-280. doi: 10.3934/dcdsb.2015.20.259

[19]

Nikolay Dimitrov. An example of rapid evolution of complex limit cycles. Discrete & Continuous Dynamical Systems - A, 2011, 31 (3) : 709-735. doi: 10.3934/dcds.2011.31.709

[20]

Claudio Canuto, Anna Cattani. The derivation of continuum limits of neuronal networks with gap-junction couplings. Networks & Heterogeneous Media, 2014, 9 (1) : 111-133. doi: 10.3934/nhm.2014.9.111

 Impact Factor: 

Metrics

  • PDF downloads (0)
  • HTML views (0)
  • Cited by (3)

[Back to Top]