Dynamical Systems on Networks

Campus: 
Vienna
Academic Year: 
2019-2020
Term: 
Winter
US Credits: 
2
ECTS Credits: 
4
Course Code: 
DNDS 6022
Course Description: 

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

1 Introduction

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.

7 Synchronization

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

Books

- 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).

Review articles

- 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).

Datasets

- 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

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.

Learning Outcomes: 

By successfully completing the course, the students will:

  • Know the most common models used to understand the temporal evolution of dynamical phenomena in complex networks, including epidemic spreading, opinion and cultural evolution, synchronization, etc.
  • Be able to use analytical approximation methods to derive statistical properties of dynamical systems on networks, as well as perform computational simulations of the associated models.
  • Be able to analyze large-scale data on dynamical complex phenomena and use it to validate models of both state and network evolution.
  • Know how to reformulate research questions into a framework of data analysis, model development, and data-driven validation, by applying the course techniques in small-scale research projects.
Assessment: 

(1) Assessment type 1 (50% of final grade). Copy a paper together! Students will organize in small teams (depending on how many attend the course) and choose one research article from a pre-selected set. They will then have to reproduce the main results of the paper, deliver a written report, and present their work as a team. Pre-selected articles may include analysis of open-access data, analytical calculations of models, and computer simulations of models.

(2) Assessment type 2 (50% of final grade). Make a paper by yourself! In the final project, students will individually design a research project from scratch, deliver a written report, and present their results in class. The research project needs to involve a dynamical process on top of a network, a network evolving in time, or both. It also includes at least two of the following approaches: analysis of open-access data, analytical calculations of models, and computer simulations of models.

Prerequisites: 
  • Intermediate/advanced math skills: Linear algebra, calculus and differential equations, probability theory and statistics.
  • Knowledge of fundamental network science concepts.
  • Basic/intermediate programming skills, preferably in Python or C/C++ (e.g. familiarity with variables, loops and conditionals, functions, data structures, file I/O, classes, etc.).