Lecture: Computational Modelling of Complex Networks – SS14

Lecturer: Prof. Luca Bortolussi
Assistant: Charalampos Kyriakopoulos

News: The oral exam will take place on the 2nd of October in Room 303.

Oral Exam:

  • 09.10: Sebastian Brost
  • 09.30: Dhiman Chakraborty
  • 09.50: Gerrit Grossmann
  • 10.10: Arthur Suleymanov
  • 10.30: Tahleen Rahman
  • —————————————-
  • 11.30: Rafaella Antonyan
  • 11.50: Sebastian Froede
  • 12.10: Mayank Goyal
  • 12.30: Shahd Zahran

Description: Two weeks block course. Click here to see a small presentation of the course.

Period: September 15, 2014  – September 26, 2014

Schedule: The overall course period will be from Monday the 15th of September until Friday the 26th of September. The lectures are going to be held from 10.15 – 11.45 everyday, while the tutorials are to be given later in the afternoon between 13.15 – 14.45.

Dates: 15.09 until 19.09 – Lecture hall 001, Building E 1 3

Dates: 22.09 until 24.09  – Seminar room 001, Bioinformatics Building E 2 1

Date: 25.09 – Seminar room 001, Cluster Building E 1 7

Dates 26.09 – 02.10 – Seminar room 001, Bioinformatics  Building E 2 1

Credits: 4 ECTS credits (Advanced course)

Overview: Many socio-technical and natural systems have a network structure. Examples are the Internet, the world-wide-web, social networks, power grids. Most of  these networks are the result of random processes shaping them. However, their topology is very different from the one of a random graph: the majority of nodes have few connections, while few nodes have a large number of links. This observation is at the heart of network science, aiming at understanding how such structure is formed, and how it impacts on the dynamics of processes happening on those networks (e.g. gossip spreading ).

Objectives:  This course is an introduction to modelling dynamics of complex networks. We will first discuss random graphs and models of complex network formation that can capture some of the topological properties of real networks. We will look at models of internet and the world wide web, but examples from biology (e.g. protein networks) can be considered as well.

Then, we will turn our attention to models of dynamical processes on networks, including percolation, avalanches, and cascade failures on power grids, and models of epidemic and gossip spreading in social networks. Case studies will be chosen with the goal of introducing  modelling and analysis techniques, from simulation to mean-field and pair approximation (which are set of differential equations capturing some aspect of the dynamics of the process). We will possibly also look at adaptive network models, in which processes on networks re-shape continuously its topology.

Prerequisites:
The course is open to all students of computer science. Some knowledge of Markov Chains, (basic) probability,  and (basic) graph theory is helpful but not mandatory.

Students that want to refresh their background in probability and Markov Chains can take a look at few chapters of the book (chapters 1, 2, 4, and appendix A):

Exercises:  9 optional exercise sheets will be given with both practical (implementation in a toolbox of MATLAB) and theoretical problems. Bonus points up to 10% will be shared to those who present the theoretical solutions in the class and/or send their implementations.

Exam schedule:  The final examination will be oral and based on the material will have been taught as well as the Exercise Sheets. One can also implement a small project and be examined on this too if he wishes. The oral exam will take place on the 2nd of October.

Bibliography. Some references that will be followed during the course are the following:

  • Alain Barrat, Marc Barthélemy, Alessandro Vespignani. Dynamical Processes on Complex Networks, Cambridge Univ. Press, 2008. *
  • Mark Newman.  The structure and function of complex networks. SIAM review, 2003. *
  • M. Tizzoni, P. Bajardi, C. Poletto, J. J. Ramasco, D. Balcan, B. Gonçalves, N. Perra, V. Colizza, and A. Vespignani, “Real-time numerical forecast of global epidemic spreading: case study of 2009 A/H1N1pdm,” BMC Medicine, vol. 10, no. 1, p. 165, Dec. 2012.
  • S. H. Strogatz, “Exploring complex networks,” Nature, vol. 410, no. 6825, pp. 268–276, 2001.
  • A.L. Barabasi. Network science book. http://barabasilab.neu.edu/networksciencebook/
  • M. E. Newman, “Power laws, Pareto distributions and Zipf’s law,” Contemporary physics, vol. 46, no. 5, pp. 323–351, 2005.
  • B. Bollobás, Random graphs. Cambridge; New York: Cambridge University Press, 2001. !!
  • M. E. Newman, “Random graphs as models of networks,” in Handbook of graphs and networks: From the genome to the internet, 2006.
  • S. N. Dorogovtsev and J. F. Mendes, Evolution of networks: From biological nets to the Internet and WWW. Oxford University Press, 2013. !!
  • R. Pastor-Satorras and A. Vespignani, “Epidemic dynamics and endemic states in complex networks,” Phys. Rev. E, vol. 63, no. 6, p. 066117, May 2001.
  • R. Pastor-Satorras and A. Vespignani, “Epidemic dynamics in finite size scale-free networks,” Phys Rev E Stat Nonlin Soft Matter Phys, vol. 65, no. 3 Pt 2A, p. 035108, Mar. 2002. !!
  • R. Pastor-Satorras and A. Vespignani, “Epidemic Spreading in Scale-Free Networks,” Physical Review Letters, vol. 86, no. 14, pp. 3200–3203, Apr. 2001.
  • T. Gross, C. J. D. D’Lima, and B. Blasius, “Epidemic Dynamics on an Adaptive Network,” Phys. Rev. Lett., vol. 96, no. 20, p. 208701, May 2006. !!
  • H. Sayama, I. Pestov, J. Schmidt, B. J. Bush, C. Wong, J. Yamanoi, and T. Gross, “Modeling complex systems with adaptive networks,” Computers & Mathematics with Applications, vol. 65, no. 10, pp. 1645–1664, May 2013.
  • T. Gross and B. Blasius, “Adaptive coevolutionary networks: a review,” Journal of the Royal Society Interface, vol. 5, no. 20, pp. 259–271, 2008. !!

Bibliography will keep on expanding during the course. Items marked with a “*” at the end are the most relevant ones, containing all the information really needed to pass the course (and much more). All other items are complementary lectures. Those marked with “!!” are mathematically challenging.