Large-scale networks with complex interaction patterns are common in nature and society (genetic pathways, ecological networks, social networks, networks of scientific collaboration, WWW, peer-to-peer networks, power grids, etc.). These constantly evolving, networked interactions are critical in determining how dynamical phenomena (like spreading, synchronization, and consensus) behave in complex systems. The aim of this course is to explore the statistical features of both dynamical processes over networks and the temporal evolution of the networks themselves. ‘Dynamics on networks’ refers to processes that take place on top of networks, like the spreading of diseases on human contact networks, the diffusion of ideas and innovations in online social networks, and opinion formation in politics. ‘Dynamics of networks’ refers to mechanisms that provoke changes in the topology of the network, like self-organization in biological systems, cumulative advantage in social hierarchies, and competition in culture. We will introduce the most common mathematical and computational techniques used to characterize dynamical systems on and of networks, including phenomena where both process and network coevolve in time.
Tentative course topics
Dynamical systems in the real world: Spreading, synchronization, and the emergence of consensus. Role of network topology. Mathematical/computational tools to study dynamics on/of networks. Plan of the course.
2 Percolation and network resilience
Removal/addition of nodes/edges. Percolation in real-world networks (directed and random attacks, cascading failures in infrastructure). Computer algorithms of percolation. K-core, explosive, and other types of percolation.
3 Epidemic spreading
Biological contagion. Simple models with susceptible, infected, and recovered agents (SI, SIS, SIR, etc.). More involved compartmental models. Stationary final states and time-dependent properties. Epidemic spreading and human mobility. Computational forecasting platforms (GLEAMviz).
4 Social contagion
Cascades of information and innovations. Social influence, homophily, and the environment. Complex vs. simple contagion. Threshold and generalized contagion models (Granovetter, Watts, and Centola-Macy models).
5 Opinion dynamics
Voter model, Majority rule model, and Sznajd model. Social impact theory. Bounded confidence models (Deffuant, Hegselmann-Krause). Empirical data in opinion formation (electoral turnouts, etc.). Opinion dynamics and human mobility.
6 Cultural dynamics
Social influence and homophily in cultural evolution. Axelrod model and variants. Models of language dynamics (evolutionary and quasispecies models, the Naming Game). Language competition.
Pendulumns, circadian rhythms, and butterflies. Coupled oscillators on networks. Kuramoto model. Stability of synchronized state. Applications in biological, technological, and social systems.
8 Dynamical systems on networks
Dynamical systems theory. Fixed points, linearization, and linear stability analysis. Application to synchronization. Master stability conditions and functions. Alternative approaches.
9 Approximation methods
Mean field, pair, and higher-order approximations for dynamics on networks. Heterogeneous mean-field approach and particle-network framework. Node- and degree-based approximations for the SI and threshold models. Approximate master equations for stochastic binary dynamics.
10 Network evolution
Network growth and decay. Preferential attachment (models of Simon, Price, and Barabási-Albert) and extensions; vertex-copying models. Network optimization. Link rewiring and small-world models. Introduction to temporal networks and dynamic networks.
11 Coevolution of states and topology
Adaptive networks in the real world. Self-organization in Boolean networks. Adaptive coupled oscillators. Cooperation in adaptive games. Coevolving epidemic spreading and opinion formation (adaptive SIS model, Holme & Newman model, Zanette & Gil model). Adaptive Deffuant and Axelrod models, etc.
12 Project presentations by students
Suggested reading and online resources
- D. Easley and J. Kleinberg, Networks, Crowds and Markets: Reasoning about a Highly Connected World (Cambridge University Press, 2010).
- S. N. Dorogovtsev, Lectures on Complex Networks (Oxford University Press, 2010).
- S. Lehmann and Y. Y. Ahn (Eds.), Complex Spreading Phenomena in Social Systems: Influence and Contagion in Real-World Social Networks (Springer Nature, 2018).
- M. A. Porter, J. P. Gleeson, Dynamical Systems on Networks. Frontiers in Applied Dynamical Systems: Reviews and Tutorials, Volume 4 (Springer, 2016).
- M. Newman, Networks: Second Edition (Oxford University Press, 2018).
- R. Albert, A.-L. Barabási, Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47-97 (2002).
- S. Boccaletti et al., Complex networks: Structure and dynamics. Phys. Rep. 424, 175-308 (2006).
- C. Castellano, S. Fortunato, V. Loreto, Statistical physics of social dynamics. Rev. Mod. Phys. 81, 591-645 (2009).
- M. W. Macy, R. Willer, From factors to actors: Computational sociology and agent-based modeling. Annu. Rev. Sociol. 28, 143-166 (2002).
- A. Vespignani, Predicting the behavior of techno-social systems. Science 325, 425-428 (2009).
- A. Vespignani, Modelling dynamical processes in complex socio-technical systems. Nat. Phys. 8, 32-39 (2012).
- SocioPatterns datasets http://www.sociopatterns.org/datasets/
- Stanford Large Network Dataset Collection http://snap.stanford.edu/data/
- The Colorado Index of Complex Networks https://icon.colorado.edu/#!/
Additional references and online resources will be provided during class.
Further information, such as the course website, assessment deadlines, office hours, contact details, etc. will be given during the course. The instructor reserves the right to modify this syllabus as deemed necessary any time during the term. Any modifications to the syllabus will be discussed with students during a class period. Students are responsible for information given in class.