×

Modeling complex systems with adaptive networks. (English) Zbl 1345.90021

Summary: Adaptive networks are a novel class of dynamical networks whose topologies and states coevolve. Many real-world complex systems can be modeled as adaptive networks, including social networks, transportation networks, neural networks and biological networks. In this paper, we introduce fundamental concepts and unique properties of adaptive networks through a brief, non-comprehensive review of recent literature on mathematical/computational modeling and analysis of such networks. We also report our recent work on several applications of computational adaptive network modeling and analysis to real-world problems, including temporal development of search and rescue operational networks, automated rule discovery from empirical network evolution data, and cultural integration in corporate merger.

MSC:

90B10 Deterministic network models in operations research
05C82 Small world graphs, complex networks (graph-theoretic aspects)
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming

Software:

NetworkX; Python; ORA
PDF BibTeX XML Cite
Full Text: DOI arXiv

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.; Barabási, A.-L.; Watts, D. J., The Structure and Dynamics of Networks, (2006), Princeton University Press Princeton, NJ) · Zbl 1362.00042
[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] Pastor-Satorras, R.; Vespignani, A., Epidemic spreading in scale-free networks, Phys. Rev. Lett., 86, 3200-3203, (2001)
[7] Pikovsky, A.; Rosenblum, M.; Kurths, J., Synchronization: A universal concept in nonlinear sciences, (2003), Cambridge University Press Cambridge, UK · Zbl 1219.37002
[8] Sood, V.; Redner, S., Voter model on heterogeneous graphs, Phys. Rev. Lett., 94, 178701, (2005)
[9] Zhou, H.; Lipowsky, R., Dynamic pattern evolution on scale-free networks, PNAS, 102, 10052-10057, (2005)
[10] Tomassini, M., Generalized automata networks, (Cellular Automata: Proc. 7th Intl. Conf. Cellular Automata for Research and Industry, ACRI 2006, (2006), Springer Berlin, Heidelberg), 14-28 · Zbl 1155.68467
[11] Otto, S. B.; Rall, B. C.; Brose, U., Allometric degree distributions facilitate food-web stability, Nature, 450, 1226-1229, (2007)
[12] Nakao, H.; Mikhailov, A. S., Turing patterns in network-organized activator-inhibitor systems, Nat. Phys., 6, 544-550, (2010)
[13] de Solla Price, D. J., Networks of scientific papers, Science, 149, 510-515, (1965)
[14] Watts, D. J.; Strogatz, S. H., Collective dynamics of ‘small-world’ networks, Nature, 393, 440-442, (1998) · Zbl 1368.05139
[15] Barabási, A.-L.; Albert, R., Emergence of scaling in random networks, Science, 286, 509-512, (1999) · Zbl 1226.05223
[16] Shargel, B.; Sayama, H.; Epstein, I. R.; Bar-Yam, Y., Optimization of robustness and connectivity in complex networks, Phys. Rev. Lett., 90, 068701, (2003)
[17] da Fontoura Costa, L., Reinforcing the resilience of complex networks, Phys. Rev. E, 69, 066127, (2004)
[18] Krapivsky, P. L.; Redner, S., Network growth by copying, Phys. Rev. E, 71, 036118, (2005)
[19] Beygelzimer, A.; Grinstein, G. M.; Linsker, R.; Rish, I., Improving network robustness by edge modification, Physica A, 357, 593-612, (2005)
[20] Gross, T.; Blasius, B., Adaptive coevolutionary networks: a review, J. R. Soc. Interface, 5, 259-271, (2008)
[21] (Gross, T.; Sayama, H., Adaptive Networks: Theory, Models and Applications, (2009), Springer Berlin, Heidelberg)
[22] Bornholdt, S.; Rohlf, T., Topological evolution of dynamical networks: global criticality from local dynamics, Phys. Rev. Lett., 84, 6114-6117, (2000)
[23] Christensen, K.; Donangelo, R.; Koiller, B.; Sneppen, K., Evolution of random networks, Phys. Rev. Lett., 81, 2380-2383, (1998)
[24] Chialvo, D. R.; Bak, P., Learning from mistakes, Neuroscience, 90, 1137-1148, (1999)
[25] Pearlmutter, B. A.; Houghton, C. J., Tuning for criticality: a new hypothesis for sleep, Neural Comput., 21, 1622-1641, (2009) · Zbl 1166.92017
[26] Levina, A.; Herrmann, J. M.; Geisel, T., Phase transitions towards criticality in a neural system with adaptive interactions, Phys. Rev. Lett., 102, 118110, (2009)
[27] Meisel, C.; Gross, T., Adaptive self-organization in a realistic neural network model, Phys. Rev. E, 80, 061917, (2009)
[28] Beggs, J.; Plenz, D., Neuronal avalanches in neocortical circuits, J. Neurosci., 23, 11167-11177, (2003)
[29] Kitzbichler, M.; Smith, M.; Christensen, S.; Bullmore, E., Broadband criticality of human brain network synchronization, PLoS Comput. Biol., 5, e1000314, (2009)
[30] Meisel, C.; Storch, A.; Hallmeyer-Elgner, S.; Bullmore, E.; Gross, T., Failure of adaptive self-organized criticality during epileptic seizure attacks, PLoS Comput. Biol., 84, e1002312, (2012)
[31] Gross, T.; Dommar D’Lima, C.; Blasius, B., Epidemic dynamics on an adaptive network, Phys. Rev. Lett., 96, 208701, (2006)
[32] Gross, T.; Kevrekidis, I. G., Robust oscillations in SIS epidemics on adaptive networks: coarse graining by automated moment closure, Europhys. Lett., 82, 38004, (2008)
[33] Marceau, V.; Noël, P.-A.; Hébert-Dufresne, L.; Allard, A.; Dube, L. J., Adaptive networks: coevolution of disease and topology, Phys. Rev. E, 82, 036116, (2010)
[34] Guerra, B.; Gomez-Gardenes, J., Annealed and mean-field formulations of disease dynamics on static and adaptive networks, Phys. Rev. E, 82, 035101, (2010)
[35] Wieland, S.; Aquino, T.; Nunes, A., The structure of coevolving infection networks, Europhys. Lett., 97, 18003, (2012)
[36] Wang, L.; Yan, J.-R.; Zhang, J.-G.; Liu, Z.-R., Controlling disease spread on networks with feedback mechanism, Chin. Phys., 16, 2498, (2007)
[37] Shaw, L. B.; Schwartz, I. B., Fluctuating epidemics on adaptive networks, Phys. Rev. E, 77, 066101, (2008)
[38] Zanette, D. H.; Risau-Gusmán, S., Infection spreading in a population with evolving contacts, J. Biol. Phys., 34, 135-148, (2008)
[39] Volz, E.; Frost, S. D.W.; Rothenberg, R.; Meyers, L. A., Epidemiological bridging by injection drug use drives an early HIV epidemic, Epidemics, 2, 155-164, (2010)
[40] Funk, S.; Salathé, M.; Jansen, V. A.A., Modelling the influence of human behaviour on the spread of infectious diseases: a review, J. R. Soc. Interface, 7, 1247-1256, (2010)
[41] Epstein, J. M.; Parker, J.; Cummings, D.; Hammond, R. A., Coupled contagion dynamics of fear and disease: mathematical and computational explorations, PLoS One, 3, 12, e3955, (2008)
[42] Funk, S.; Gilad, E.; Watkins, C.; Jansen, V. A.A., The spread of awareness and its impact on epidemic outbreaks, PNAS, 106, 6872-6877, (2009) · Zbl 1203.91242
[43] Shaw, L. B.; Schwartz, I. B., Enhanced vaccine control of epidemics in adaptive networks, Phys. Rev. E, 81, 046120, (2010)
[44] Holme, P.; Newman, M. E.J., Nonequilibrium phase transition in the coevolution of networks and opinions, Phys. Rev. E, 74, 056108, (2006)
[45] Zanette, D. H.; Gil, S., Opinion spreading and agent segregation on evolving networks, Physica D, 224, 156-165, (2006) · Zbl 1129.90014
[46] Kozma, B.; Barrat, A., Consensus formation on adaptive networks, Phys. Rev. E, 77, 016102, (2008)
[47] Vazquez, F.; Eguíluz, V. M.; San Miguel, M., Generic absorbing transition in coevolution dynamics, Phys. Rev. Lett., 100, 108702, (2008)
[48] Kimura, D.; Hayakawa, Y., Coevolutionary networks with homophily and heterophily, Phys. Rev. E, 78, 016103, (2008)
[49] Böhme, G. A.; Gross, T., Analytical calculation of fragmentation transitions in adaptive networks, Phys. Rev. E, 83, 035101, (2011)
[50] 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)
[51] Centola, D.; Gonzalez-Avella, J. C.; Eguiluz, V. M.; San Miguel, M., Homophily, cultural drift, and the co-evolution of cultural groups, J. Conflict Resolut., 51, 905-929, (2007)
[52] Centola, D., The spread of behavior in an online social network experiment, Science, 329, 1194-1197, (2010)
[53] Centola, D., An experimental study of homophily in the adoption of health behavior, Science, 334, 1269-1272, (2011)
[54] Huepe, C.; Zschaler, G.; Do, A.-L.; Gross, T., Adaptive-network models of swarm dynamics, New J. Phys., 13, 073022, (2011)
[55] 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)
[56] Paczuski, M.; Bassler, K. E.; Corral, A., Self-organized network of competing Boolean agents, Phys. Rev. Lett., 84, 3185-3188, (2000)
[57] Skyrms, B.; Pemantle, R., A dynamic model of social network formation, PNAS, 97, 9340-9346, (2000) · Zbl 0984.91013
[58] Zimmermann, M. G.; Eguíluz, V. M.; San Miguel, M.; Spadaro, A., Cooperation in an adaptive network, Adv. Complex Syst., 3, 283-297, (2000)
[59] H. Ebel, S. Bornholdt, Evolutionary games and the emergence of complex networks, 2002. arXiv:cond-mat/0211666 (accessed 08.30.12).
[60] 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)
[61] van Segbroeck, S.; Santos, F. C.; Lenaerts, T.; Pacheco, J. M., Selection pressure transforms the nature of social dilemmas in adaptive networks, New J. Phys., 13, 013007, (2011)
[62] Poncela, J.; Gomez-Gardenes, J.; Traulsen, A.; Moreno, Y., Evolutionary game dynamics in a growing structured population, New J. Phys., 11, 083031, (2009)
[63] Zschaler, G.; Traulsen, A.; Gross, T., A homoclinic route to full cooperation in adaptive networks and its failiure, New J. Phys., 12, 093015, (2010)
[64] Bala, V.; Goyal, S., Conformism and diversity under social learning, Econom. Theory, 17, 101-120, (2001) · Zbl 1038.91555
[65] Holme, P.; Ghoshal, G., Dynamics of networking agents competing for high centrality and low degree, Phys. Rev. Lett., 96, 098701, (2006)
[66] Do, A.-L.; Rudolf, L.; Gross, T., Patterns of cooperation: fairness and coordination in networks of interacting agents, New J. Phys., 12, 063023, (2010) · Zbl 1382.91014
[67] Burt, R. S., Structural holes: the social structure of competition, (1995), Harvard University Press
[68] Buskens, V.; Van de Rijt, A., Dynamics of networks if everyone strives for structural holes, Am. J. Sociol., 114, 371-407, (2008)
[69] Dionne, S. D.; Sayama, H.; Hao, C.; Bush, B. J., The role of leadership in shared mental model convergence and team performance improvement: an agent-based computational model, Leadership Quart., 21, 1035-1049, (2010)
[70] Y. Lin, K.C. Desouza, Co-evolution of organizational network and individual behavior: an agent-based model of interpersonal knowledge transfer, in: ICIS 2010 Proc. 2010 Paper 153. Available online at: http://aisel.aisnet.org/icis2010_submissions/153 (accessed 08.30.12).
[71] J. Yamanoi, H. Sayama, Post-merger cultural integration from a social network perspective: a computational modeling approach, Comput. Math. Organ. Theory (in press).
[72] T. Gross, Adaptive networks website. http://adaptive-networks.wikidot.com/ (accessed 08.30.12).
[73] H. Sayama, Generative network automata: a generalized framework for modeling complex dynamical systems with autonomously varying topologies, in: Proc. IEEE Symp. Artif. Life, 2007, pp. 214-221.
[74] Sayama, H.; Laramee, C., Generative network automata: a generalized framework for modeling adaptive network dynamics using graph rewritings, (Gross, T.; Sayama, H., Adaptive Networks: Theory, Models and Applications, (2009), Springer Berlin, Heidelberg), 311-332
[75] (Rozenberg, G., Handbook of Graph Grammars and Computing by Graph Transformation, Volume 1: Foundations, (1997), World Scientific Singapore) · Zbl 0908.68095
[76] Kurth, W.; Kniemeyer, O.; Buck-Sorlin, G. H., Relational growth grammars-a graph rewriting approach to dynamical systems with a dynamical structure, (Proc. 2004 Intl. Workshop on Unconventional Programming Paradigms, (2005), Springer Berlin, Heidelberg), 56-72
[77] Nehaniv, C. L., Asynchronous automata networks can emulate any synchronous automata network, Internat. J. Algebra Comput., 14, 719-739, (2004) · Zbl 1088.68127
[78] I. Pestov, Defence and security applications of network technologies, in: Proc. Workshop on Link Analysis, Counterterrorism and Security, SIAM Int. Conf. on Data Mining, 2009, pp. 1-7.
[79] I. Pestov, S. Verga, Dynamical networks as a tool for system analysis and exploration, in: Proc. IEEE Symp. Comput. Intell. in Security and Defence Applications, CISDA 2009, 2009, 8 pages.
[80] I. Pestov, M. Pilat, Modelling search and rescue systems with dynamical networks, in: Proc. IEEE Symp. Comput. Intell. in Security and Defence Applications, CISDA 2011, 2011, 8 pages.
[81] I. Pestov, M. Pilat, A net-enabled approach to modelling joint interagency systems: the Arctic search and rescue network, DRDC CORA TM 2012-067, Ottawa, Canada, 2012.
[82] I. Pestov, H. Sayama, C. Wong, Modeling discrete distributed heterogeneous systems, in: Proc. Int. Conf. on Modeling, Simulation and Visualization Methods, MSV 2012, 2012, 7 pages.
[83] A.A. Hagberg, D.A. Schult, P.J. Swart, Exploring network structure, dynamics, and function using NetworkX, in: G. Varoquaux, T. Vaught, J. Millman (Eds.), Proc. 7th Python in Science Conf., 2008, pp. 11-15.
[84] K.M. Carley, D. Columbus, M. DeReno, J. Reminga, I.C. Moon, ORA user’s guide 2008, The CASOS Technical Report CMU-ISR-08-125, Carnegie Mellon University, Pittsburgh, PA, 2008.
[85] Sayama, H., An algorithm for automatically discovering dynamical rules of adaptive network evolution from empirical data, (Suzuki, J.; Nakano, T., Proc. 5th Intl. ICST Conf. on Bio-Inspired Models of Network, Information, and Computing Systems, BIONETICS 2010, (2012), Springer Berlin, Heidelberg), 497-504
[86] Schmidt, J.; Bush, B. J.; Sayama, H., A python implementation of generative network automata, (Unifying Themes in Complex Systems Volume VIII: Proc. Eighth Intl. Conf. on Complex Systems, ICCS 2011, (2011), NECSI Knowledge Press Cambridge, MA), 439-440
[87] J. Schmidt, PyGNA: designing and evaluating algorithms for automated discovery of adaptive network models based on generative network automata, Master’s Thesis, Binghamton University, State University of New York, December 2012.
[88] Leskovec, J.; Kleinberg, J.; Faloutsos, C., Graphs over time: densification laws, shrinking diameters and possible explanations, (Proc. Eleventh ACM SIGKDD Intl. Conf. on Knowledge Discovery in Data Mining, (2005), ACM New York), 177-187
[89] Bhattacharyya, A., On a measure of divergence between two statistical populations defined by their probability distributions, Bull. Calcutta Math. Soc., 35, 99-109, (1943) · Zbl 0063.00364
[90] O’Reilly, C. A.; Chatman, J.; Caldwell, D. F., People and organizational culture: a profile comparison approach to assessing person-organization fit, Acad. Manage. J., 34, 487-516, (1991)
[91] Chatterjee, L.; Lubatkin, M.; Schweiger, D.; Weber, Y., Cultural differences and shareholder value in related mergers: linking equity and human capital, Strategic Manage. J., 13, 319-334, (1992)
[92] Granovetter, M., The strength of weak ties, Am. J. Sociol., 78, 1360-1380, (1973)
[93] Wasserman, S.; Faust, K., Social network analysis: methods and applications, (1994), Cambridge University Press Cambridge, UK
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.