×

Moment-closure approximations for discrete adaptive networks. (English) Zbl 1285.93013

Summary: Moment-closure approximations are an important tool in the analysis of the dynamics on both static and adaptive networks. Here, we provide a broad survey over different approximation schemes by applying each of them to the adaptive voter model. While already the simplest schemes provide reasonable qualitative results, even very complex and sophisticated approximations fail to capture the dynamics quantitatively. We then perform a detailed analysis that identifies the emergence of specific correlations as the reason for the failure of established approaches, before presenting a simple approximation scheme that works best in the parameter range where all other approaches fail. By combining a focused review of published results with new analysis and illustrations, we seek to build up an intuition regarding the situations when existing approaches work, when they fail, and how new approaches can be tailored to specific problems.

MSC:

93A15 Large-scale systems
93C40 Adaptive control/observation systems
05C82 Small world graphs, complex networks (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Albert, R.; Barabási, A.-L., Statistical mechanics of complex networks, Rev. Modern Phys., 74, 47-97 (2002) · Zbl 1205.82086
[2] Newman, M. E.J., The structure and function of complex networks, SIAM Rev., 45, 167-256 (2003) · Zbl 1029.68010
[3] (Newman, M. E.J.; Barabási, A.-L.; Watts, D. J., The Structure and Dynamics of Networks (2006), Princeton University Press: Princeton University Press Princeton, NJ)
[4] Boccaletti, S.; Latora, V.; Moreno, Y.; Chavez, M.; Hwang, D.-U., Complex networks: structure and dynamics, Phys. Rep., 424, 175-308 (2006) · Zbl 1371.82002
[5] Dorogovtsev, S. N.; Goltsev, A. V.; Mendes, J. F.F., Critical phenomena in complex networks, Rev. Modern Phys., 80, 1275-1335 (2008)
[6] Castellano, C.; Fortunato, S.; Loreto, V., Statistical physics of social dynamics, Rev. Modern Phys., 81, 591-646 (2009)
[7] Barabási, A.-L.; Albert, R., Emergence of scaling in random networks, Science, 286, 509-512 (1999) · Zbl 1226.05223
[8] Watts, D. J.; Strogatz, S. H., Collective dynamics of ‘small-world’ networks, Nature, 393, 440-442 (1998) · Zbl 1368.05139
[9] Pastor-Satorras, R.; Vespignani, A., Epidemic spreading in scale-free networks, Phys. Rev. Lett., 86, 3200-3203 (2001)
[10] Gross, T.; Blasius, B., Adaptive coevolutionary networks: a review, J. R. Soc. Interface, 5, 259-271 (2008)
[11] (Gross, T.; Sayama, H., Adaptive Networks. Theory, Models and Applications (2009), Springer-Verlag: Springer-Verlag New York)
[12] Holme, P.; Newman, M. E.J., Nonequilibrium phase transition in the coevolution of networks and opinions, Phys. Rev. E, 74, 056108 (2006)
[13] Vazquez, F.; Eguiluz, V. M.; Miguel, M. S., Generic absorbing transition in coevolution dynamics, Phys. Rev. Lett., 100, 108702 (2008)
[14] Nardini, C.; Kozma, B.; Barrat, A., Who’s talking first? Consensus or lack thereof in coevolving opinion formation models, Phys. Rev. Lett., 100, 158701 (2008)
[15] Kimura, D.; Hayakawa, Y., Coevolutionary networks with homophily and heterophily, Phys. Rev. E, 78, 016103 (2008)
[16] Zschaler, G.; Böhme, G. A.; Seißinger, M.; Huepe, C.; Gross, T., Early fragmentation in the adaptive voter model on directed networks, Phys. Rev. E, 85, 046107 (2012)
[17] Durrett, R.; Gleeson, J. P.; Lloyd, A. L.; Mucha, P. J.; Shi, F.; Sivakoff, D.; Socolar, J.; Varghese, C., Graph fission in an evolving voter model, Proc. Natl. Acad. Sci. USA, 109, 3682 (2012) · Zbl 1256.91042
[18] Böhme, G. A.; Gross, T., Fragmentation transitions in multi-state voter models, Phys. Rev. E, 85, 066117 (2012)
[19] Vazquez, F., Opinion dynamics on coevolving networks, (Mukherjee, A.; Choudhury, M.; Peruani, F.; Ganguly, N.; Mitra, B., Dynamics on and of Complex Networks, Volume 2 (2013), Birkhäuser: Birkhäuser New York), 89-107
[20] Gross, T.; D’Lima, C. J.D.; Blasius, B., Epidemic dynamics on an adaptive network, Phys. Rev. Lett., 96, 208701 (2006)
[21] Shaw, L. B.; Schwartz, I. B., Fluctuating epidemics on adaptive networks, Phys. Rev. E, 77, 066101 (2008)
[22] Risau-Gusman, S.; Zanette, D. H., Contact switching as a control strategy for epidemic outbreaks, J. Theoret. Biol., 257, 52-60 (2009) · Zbl 1400.92534
[23] Shaw, L. B.; Schwartz, I. B., Enhanced vaccine control of epidemics in adaptive networks, Phys. Rev. E, 81, 046120 (2010)
[24] Marceau, V.; Nöel, P.-A.; Hebert-Dufresne, L.; Allard, A.; Dube, L., Adaptive networks: coevolution of disease and topology, Phys. Rev. E, 82, 036116 (2010)
[25] Gräser, O.; Hui, P. M.; Xu, C., Separatrices between healthy and endemic states in an adaptive epidemic model, Physica A, 390, 906-913 (2011)
[26] Lagorio, C.; Dickison, M.; Vazquez, F.; Braunstein, L. A.; Macri, P. A.; Migueles, M. V.; Havlin, S.; Stanley, H. E., Quarantine-generated phase transition in epidemic spreading, Phys. Rev. E, 83, 026102 (2011)
[27] Wang, B.; Cao, L.; Suzuki, H.; Aihara, K., Epidemic spread in adaptive networks with multitype agents, J. Phys. A, 44, 035101 (2011) · Zbl 1205.92068
[28] Juher, D.; Ripoll, J.; Saldana, J., Outbreak analysis of an sis epidemic model with rewiring, J. Math. Biol. (2012) · Zbl 1402.92393
[29] Zimmermann, M.; Eguiluz, V.; Miguel, M. S.; Spadaro, A., Cooperation in an adaptive network, (Ballot, G.; Weisbuch, G., Application of Simulations to Social Sciences (2000), Hermes Science Publications: Hermes Science Publications Oxford, UK), 283-297
[30] Skyrms, B.; Pemantle, R., A dynamic model of social network formation, Proc. Natl. Acad. Sci. USA, 97, 9340-9346 (2000) · Zbl 0984.91013
[31] Zimmermann, M. G.; Eguiluz, V. M.; Miguel, M. S., Coevolution of dynamical states and interactions in dynamic networks, Phys. Rev. E, 69, 065102(R) (2004)
[32] Pacheco, J. M.; Traulsen, A.; Nowak, M. A., Coevolution of strategy and structure in complex networks with dynamical linking, Phys. Rev. Lett., 97, 258103 (2006)
[33] van Segbroeck, S.; Santos, F.; Lenaerts, T.; Pacheco, J., Reacting differently to adverse ties promotes cooperation in social networks, Phys. Rev. Lett., 102, 058105 (2009)
[34] Poncela, J.; Gómez-Gardeñes, J.; Traulsen, A.; Moreno, Y., Evolutionary game dynamics in a growing structured population, New J. Phys., 11, 083031 (2009)
[35] Szolnoki, A.; Perc, M., Emergence of multilevel selection in the prisoner’s dilemma game on coevolving random networks, New J. Phys., 11, 093033 (2009)
[36] Do, A.-L.; Rudolf, L.; Gross, T., Patterns of cooperation, New J. Phys., 12, 063023 (2010) · Zbl 1382.91014
[37] Zschaler, G.; Traulsen, A.; Gross, T., A homoclinic route to asymptotic full cooperation in adaptive networks and its failure, New J. Phys., 12, 093015 (2010)
[38] van Segbroeck, S.; Santos, F.; Lenaerts, T.; Pacheco, J., Selection pressure transforms the nature of social dilemmas in adaptive networks, New J. Phys., 13, 013007 (2011) · Zbl 1448.91042
[39] Lee, S.; Holme, P.; Wu, Z.-X., Emergent hierarchical structures in multiadaptive games, Phys. Rev. Lett., 106, 028702 (2011)
[40] Fehl, K.; van der Post, D. J.; Semmann, D., Co-evolution of behaviour and social network structure promotes human cooperation, Ecol. Lett., 14, 546-551 (2011)
[41] Santos, F. C.; Pinheiro, F. L.; Lenaerts, T.; Pacheco, J. M., The role of diversity in the evolution of cooperation, J. Theoret. Biol., 299, 88-96 (2012)
[42] Zhou, C.; Kurths, J., Dynamical weights and enhanced synchronization in adaptive complex networks, Phys. Rev. Lett., 96, 164102 (2006)
[43] Sorrentino, F.; Ott, E., Adaptive synchronization of dynamics on evolving complex networks, Phys. Rev. Lett., 100, 114101 (2008)
[44] Aoki, T.; Aoyagi, T., Co-evolution of phases and connection strengths in a network of phase oscillators, Phys. Rev. Lett., 102, 034101 (2009)
[45] Assenza, S.; Gutiérrez, R.; Gómez-Gardeñes, J.; Latora, V.; Boccaletti, S., Emergence of structural patterns out of synchronization in networks with competitive interactions, Sci. Rep., 1, 99 (2011)
[46] Botella-Soler, V.; Glendinning, P., Emergence of hierarchical networks and polysynchronous behaviour in simple adaptive systems, Europhys. Lett., 97, 1332-1355 (2012)
[47] Bornholdt, S.; Rohlf, T., Topological evolution of dynamical networks: global criticality from local dynamics, Phys. Rev. Lett., 84, 6114-6117 (2000)
[48] Bornholdt, S.; Röhl, T., Self-organized critical neural networks, Phys. Rev. E, 67, 066118 (2003)
[49] Levina, A.; Herrmann, J. M.; Geisel, T., Dynamical synapses causing self-organized criticality in neural networks, Nat. Phys., 3, 857-860 (2007)
[50] Levina, A.; Herrmann, J. M.; Geisel, T., Phase transitions towards criticality in a neural system with adaptive interactions, Phys. Rev. Lett., 102, 118110 (2007)
[51] Jost, J.; Kolwankar, K. M., Evolution of network structure by temporal learning, Physica A, 388, 1959-1966 (2009)
[52] Meisel, C.; Gross, T., Adaptive self-organization in a realistic neural network model, Phys. Rev. E, 80, 061917 (2009)
[53] Ren, Q.; Kolwankar, K. M.; Samal, A.; Jost, J., Stdp-driven networks and the C. Elegans neuronal network, Physica A, 389, 3900-3914 (2010)
[54] Meisel, C.; Storch, A.; Hallmeyer-Elgner, S.; Bullmore, E.; Gross, T., Failure of adaptive self-organized criticality during epileptic seizure attacks, PLoS Comput. Biol., 8, 1, e1002312 (2012)
[55] Droste, F.; Do, A.-L.; Gross, T., Analytical investigation of self-organized criticality in neural networks, J. R. Soc. Interface (2012)
[56] Huepe, C.; Zschaler, G.; Do, A.-L.; Gross, T., Adaptive-network models of swarm dynamics, New J. Phys., 13, 073022 (2011)
[57] Couzin, I. D.; Ioannou, C. C.; Demirel, G.; Gross, T.; Torney, C. J.; Hartnett, A.; Conradt, L.; Levin, S. A.; Leonard, N. E., Uninformed individuals promote democratic consensus in animal groups, Science, 334, 1578-1580 (2011)
[58] Peixoto, T. P.; Bornholdt, S., No need for conspiracy: self-organized cartel formation in a modified trust game, Phys. Rev. Lett., 108, 218702 (2012)
[59] Kim, S.-W.; Noh, J. D., Instability in a network coevolving with a particle system, Phys. Rev. Lett., 100, 118702 (2008)
[60] Tomita, K.; Kurokawa, H.; Muarata, S., Graph-rewiring automata as a natural extension of cellular automata, (Gross, T.; Sayama, H., Adaptive Networks. Theory, Models and Applications (2009), Springer-Verlag: Springer-Verlag New York), 291-310
[61] Atay, F. M.; Jost, J., Delays, connection topology, and synchronization of coupled chaotic maps, Phys. Rev. Lett., 92, 144101 (2004)
[62] Do, A.-L.; Boccaletti, S.; Gross, T., Graphical notation reveals topological stability criteria for collective dynamics in complex networks, Phys. Rev. Lett., 108, 194102 (2012)
[63] Bethe, H. A., Statistical theory of superlattices, Proc. R. Soc. B, 150, 552-575 (1935) · Zbl 0012.04501
[64] Peierls, R., On ising’s model of ferromagnetism, Proc. Cambridge Philos. Soc., 32, 477-481 (1936) · Zbl 0014.33604
[65] Matsuda, H.; Ogita, N.; Sasaki, A.; Sato, K., Statistical mechanics of population: the lattice Lotka-Volterra model, Progr. Theoret. Phys., 88, 1035-1049 (1992)
[66] Bauch, C. T., The spread of infectious diseases in spatially structured populations: an invasory pair approximation, Math. Biosci., 198, 217-237 (2005) · Zbl 1089.92041
[67] Szabó, G.; Szolnoki, A.; Izsak, R., Rock-scissors-paper game on regular small-world networks, J. Phys. A, 37, 2599 (2004) · Zbl 1055.82021
[68] Peyrard, N.; Dieckmann, U.; Franc, A., Long-range correlations improve understanding of the influence of network structure on contact dynamics, Theor. Popul. Biol., 73, 383-394 (2008) · Zbl 1210.92043
[69] Gross, T.; Kevrekidis, I. G., Robust oscillations in sis epidemics on adaptive networks: coarse graining by automated moment closure, Europhys. Lett., 82, 38004-38006 (2008)
[70] Jolad, S.; Liu, W.; Schmittmann, B.; Zia, R. K.P., Epidemic spreading on preferred degree adaptive networks, PLoS ONE, 7, 11, e48686 (2012)
[71] Wieland, S.; Aquino, T.; Nunes, A., The structure of coevolving infection networks, Europhys. Lett., 97, 18003 (2012)
[72] Wieland, S.; Parisi, A.; Nunes, A., Detecting and describing dynamic equilibria in adaptive networks, Eur. Phys. J. Spec. Top., 212, 99-113 (2012)
[73] G. Demirel, T. Gross, Absence of epidemic thresholds in a growing adaptive network, 2012. arXiv:1209.2541.
[74] Gräser, O.; Xu, C.; Hui, P. M., Disconnected-connected network transitions and phase separation driven by co-evolving dynamics, Europhys. Lett., 87, 38003 (2009)
[75] Fu, F.; Wu, T.; Wang, L., Partner switching stabilizes cooperation in coevolutionary prisoner’s dilemma, Phys. Rev. E, 79, 036101 (2009)
[76] Zanette, D. H.; Gil, S., Opinion spreading and agent segregation on evolving networks, Physica D, 224, 156-165 (2006) · Zbl 1129.90014
[77] Demirel, G.; Prizak, R.; Reddy, P. N.; Gross, T., Cyclic dominance in adaptive networks, Eur. Phys. J. B, 84, 541-548 (2011)
[78] G. Demirel, F. Vazquez, G. Böhme, T. Gross, Moment closure approximations for discrete adaptive networks, 2012. arXiv:1211.0449. · Zbl 1285.93013
[79] Holley, R.; Liggett, T., Ergodic theorems for weakly interacting infinite systems and the voter model, Ann. Probab., 3, 643-663 (1975) · Zbl 0367.60115
[80] Sood, V.; Redner, S., Voter model on heterogeneous graphs, Phys. Rev. Lett., 94, 178701 (2005)
[81] Sood, V.; Antal, T.; Redner, S., Voter models on heterogeneous networks, Phys. Rev. E, 77, 041121 (2008)
[82] Vazquez, F.; Eguiluz, V. M., Analytical solution of the voter model on uncorrelated networks, New J. Phys., 10, 063011 (2008)
[83] Castellano, C.; Vilone, D.; Vespignani, A., Incomplete ordering of the voter model on small-world networks, Europhys. Lett., 63, 153-158 (2003)
[84] Vilone, D.; Castellano, C., Solution of voter model dynamics on annealed small-world networks, Phys. Rev. E, 69, 016109 (2004)
[85] Suchecki, K.; Eguiluz, V. M.; Miguel, M. S., Conservation laws for the voter model in complex networks, Europhys. Lett., 69, 228-234 (2005)
[86] Castellano, C.; Loreto, V.; Barrat, A.; Cecconi, F.; Parisi, D., Comparison of voter and Glauber ordering dynamics on networks, Phys. Rev. E, 71, 066107 (2005)
[87] Suchecki, K.; Eguiluz, V. M.; Miguel, M. S., Voter model dynamics in complex networks: role of dimensionality, disorder, and degree distribution, Phys. Rev. E, 72, 036132 (2005)
[88] Castelló, X.; Toivonen, R.; Eguiluz, V. M.; Saramäki, J.; Kaski, K.; Miguel, M. S., Anomalous lifetime distributions and topological traps in ordering dynamics, Europhys. Lett., 79, 66006 (2007)
[89] Böhme, G. A.; Gross, T., Analytical calculation of fragmentation transitions in adaptive networks, Phys. Rev. E, 83, 035101(R) (2011)
[90] Gil, S.; Zanette, D. H., Coevolution of agents and networks: opinion spreading and community disconnection, Phys. Lett. A, 356, 89-94 (2006) · Zbl 1160.91404
[91] Benczik, I. J.; Benczik, S. Z.; Schmittmann, B.; Zia, R. K.P., Lack of consensus in social systems, Europhys. Lett., 82, 48006 (2008)
[92] Fu, F.; Wang, L., Coevolutionary dynamics of opinions and networks: from diversity to uniformity, Phys. Rev. E, 78, 016104 (2008)
[93] Benczik, I. J.; Benczik, S. Z.; Schmittmann, B.; Zia, R. K.P., Opinion dynamics on an adaptive random network, Phys. Rev. E, 79, 046104 (2009)
[94] Sobkowicz, P., Studies of opinion stability for small dynamic networks with opportunistic agents, Internat. J. Modern Phys. C, 20, 1645-1662 (2009) · Zbl 1187.91166
[95] Zhong, L.-X.; Ren, F.; Qiu, T.; Xu, J.-R.; Chen, B.-H.; Liu, C.-F., Effects of attachment preferences on coevolution of opinions and networks, Physica A, 389, 2557-2565 (2010)
[96] Herrera, J. L.; Cosenza, M. G.; Tucci, K.; González-Avella, J. C., General coevolution of topology and dynamics in networks, Europhys. Lett., 95, 58006 (2011)
[97] Gleeson, J. P.; Melnik, S.; Ward, J.; Porter, M. A.; Mucha, P. J., Accuracy of mean-field theory for dynamics on real-world networks, Phys. Rev. E, 85, 026106 (2012)
[98] Pastor-Satorras, R.; Vespignani, A., Epidemic dynamics and endemic states in complex networks, Phys. Rev. E, 63, 066117 (2001)
[99] Moreno, Y.; Pastor-Satorras, R.; Vespignani, A., Epidemic outbreaks in complex heterogeneous networks, Eur. Phys. J. B, 26, 521-529 (2002)
[100] Pugliese, E.; Castellano, C., Heterogeneous pair approximation for voter models on networks, Europhys. Lett., 88, 58004 (2009)
[101] Nöel, P.-A.; Davoudi, B.; Brunham, R. C.; Dube, L. J.; Pourbohloul, B., Time evolution of epidemic disease on finite and infinite networks, Phys. Rev. E, 79, 026101 (2009)
[102] Gleeson, J. P., High-accuracy approximation of binary-state dynamics on networks, Phys. Rev. Lett., 107, 068701 (2011)
[103] Keeling, M. J., The effects of local spatial structure on epidemiological invasions, Proc. R. Soc. B, 266, 859-867 (1999)
[104] House, T.; Keeling, M. J., Insights from unifying modern approximations to infections on networks, J. R. Soc. Interface, 8, 67-73 (2011)
[105] Zanette, D. H.; Risau-Gusman, S., Infection spreading in a population with evolving contacts, J. Biol. Phys., 34, 135-148 (2008)
[106] Kuehn, C., A mathematical framework for critical transitions: Bifurcations, fast-slow systems and stochastic dynamics, Physica D, 240, 1020-1035 (2011) · Zbl 1225.35242
[107] Katsura, S.; Takizawa, M., Bethe lattice and Bethe approximation, Progr. Theoret. Phys., 51, 82-98 (1974)
[108] Burley, D. M., Closed form approximations for lattice systems, (Domb, C.; Green, M., Phase Transitions and Critical Phenomena (1972), Academic Press: Academic Press London, UK), 329-374
[109] Yedidia, J.; Freeman, W.; Weiss, Y., Constructing free energy approximations and generalized belief propagation algorithms, IEEE Trans. Inform. Theory, 51, 2282-2312 (2005) · Zbl 1283.94023
[110] Law, R.; Murrell, D. J.; Dieckmann, U., Population growth in space and time: spatial logistic equations, Ecology, 84, 252-262 (2003)
[111] Kikuchi, R., A theory of cooperative phenomena, Phys. Rev., 81, 988-1003 (1951) · Zbl 0043.44002
[112] Kevrekidis, I. G.; Gear, C. W.; Hummer, G., Equation-free: the computer-aided analysis of complex multiscale systems, AIChE J., 50, 1346-1355 (2004)
[113] Rogers, T., Maximum-entropy moment-closure for stochastic systems on networks, J. Stat. Mech., P05007 (2011)
[114] Lindquist, J.; Ma, J.; van den Driessche, P.; Willeboordse, F. H., Effective degree network disease models, J. Math. Biol., 62, 143-164 (2011) · Zbl 1232.92066
[115] Taylor, M.; Taylor, T. J.; Kiss, I. Z., Epidemic threshold and control in a dynamic network, Phys. Rev. E, 85, 016103 (2012)
[116] H. Silk, G. Demirel, M. Homer, T. Gross, Exploring network dynamics with a mathematical triple jump, 2013. arXiv:1302.2743.
[117] Vazquez, F.; González-Avella, J. C.; Eguiluz, V. M.; Miguel, M. S., Time scale competition leading to fragmentation and recombination transition in the coevolution of network and states, Phys. Rev. E, 76, 046120 (2007)
[118] Kozma, B.; Barrat, A., Consensus formation on adaptive networks, Phys. Rev. E, 77, 016102 (2008)
[119] Kozma, B.; Barrat, A., Consensus formation on coevolving networks: groups’ formation and structure, J. Phys. A, 41, 224020 (2008)
[120] Iñiguez, G.; Kertész, J.; Kaski, K. K.; Barrio, R. A., Opinion and community formation in coevolving networks, Phys. Rev. E, 80, 066119 (2009)
[121] Bryden, J.; Funk, S.; Geard, N.; Bullock, S.; Jansen, V. A.A., Stability in flux: community structure in dynamic networks, J. R. Soc. Interface, 8, 1031-1040 (2011)
[122] Holme, P.; Ghoshal, G., Dynamics of networking agents competing for high centrality and low degree, Phys. Rev. Lett., 96, 098701 (2006)
[123] Zimmermann, M. G.; Eguiluz, V. M., Cooperation, social networks and the emergence of leadership in a prisoners dilemma with adaptive local interactions, Phys. Rev. E, 72, 056118 (2005)
[124] Eames, K. T.D.; Keeling, M. J., Modeling dynamic and network heterogeneities in the spread of sexually transmitted diseases, Proc. Natl. Acad. Sci. USA, 99, 13330-13335 (2002)
[125] Bansal, S.; Grenfell, B. T.; Meyers, L. A., When individual behaviour matters: homogeneous and network models in epidemiology, J. R. Soc. Interface, 4, 879-891 (2007)
[126] Volz, E.; Meyers, L. A., Susceptible-infected-recovered epidemics in dynamic contact networks, Proc. R. Soc. B, 274, 2925-2934 (2007)
[127] Volz, E.; Meyers, L. A., Epidemic thresholds in dynamic contact networks, J. R. Soc. Interface, 6, 233-241 (2009)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.