Networks permeate our modern societies. Everyday, we exchange information through the World Wide Web and other communication networks, modify our opinions and make decisions under the influence of our social interactions, commute across road networks, buy goods made available to us by production and distribution networks, use electrical power, gas and water that infrastructure networks bring directly to our homes, invest our savings in highly interconnected networks of financial funds, ... 

This course will focus on common principles at the heart of the functioning of these networks and will show how the same notions related to connectivity, resilience and fragility, centrality and influence arise in several different domains. It will both introduce mathematical tools from graph theory, random graphs, dynamical systems, optimization and game theory, and cover a wide variety of applications including: opinion dynamics and learning in social networks; economic and financial networks; communication networks and the Internet; consensus and gossiping; spread and control of epidemics; dynamics and control of transportation and power networks. 

This advanced/doctoral course has been offered by the Department of Automatic Control annually in VT LP2 since Spring 2015 and is worth 7.5 hp. Here is the course flier.

Basic information will be availble at this webpage. Course material etc will be made available to registered students via the Canvas course page. There will be four hand-ins (whose completion is compulsory to pass and whose on-time submission and most oustanding solutions give extra points for the grading) and a final exam (determining the grade along with the possible extra points collected from the hand-ins). For further inquiries, please contact the responsible for the course, Giacomo Como.

Official Course Syllabus

General Information

Elective for: C4, D4, E4-ra, F4, F4-fm, F4-r, F4-mai, I4-fir, Pi4, MMSR1
Language of instruction: The course will be given in English

Aim

Networks are ubiquitous in our modern society: infrastructure networks, providing communication, transportation, energy services; social networks, determining our information, influencing our opinions, and shaping our political views; economic and financial networks, determining the nature of economic interactions and financial linkages; and natural networks (e.g., biological and physical networks), governing the evolution and spread of natural phenomena.

This course will provide an introduction to and some analysis of the main mathematical models used to describe large networks and dynamical processes that evolve on networks. Motivation and applications will be drawn from social, economic, natural, and infrastructure networks, as well as networked decision systems such as sensor networks.

Learning outcomes

Knowledge and understanding
For a passing grade the student must

• know the basic principles of graph theory and apply them to model real-world networks
• have insight in the basic differences between different models of random graphs
• be familiar with the properties of random walks on graphs
• be able to analyze simple dynamical systems over networks
• understand emerging phenomena in large-scale networks
• be able to give an overview of modern directions in network science

Competences and skills
For a passing grade the student must

• be able to analyze properties of (random) graphs both quantitatively and qualitatively
• be able to handle basic analytical computations for random walks
• be able to analyze simple dynamical systems over networks and to relate their behavior to the network structure
• be able to use computer tools for simulation and analysis of networks

Judgement and approach
For a passing grade the student must

• be able to understand relations and limitations when simple models are used to describe complex networks
• be able to evaluate dominating emerging phenomena in network dynamics

Contents

• Basic graph theory: connectivity, degree distributions, trees, adjacency matrices, spectrum.
• Random graphs: Erdos-Renyi, configuration model, preferential attachment, small-world, branching process approximations
• Flows and games on graphs: max-flow, min-cut, optimal transport, Wardrop equilibria, evolutionary dynamics.
• Random walks on graphs: invariant distributions, hitting times, mixing times.
• Dynamical systems on graphs: distributed averaging, interacting particle systems, epidemics, opinion dynamics. Mean-field and branching process approximations.

Examination details

Grading scale: TH - (U,3,4,5) - (Fail, Three, Four, Five)
Assessment: Written exam (5 hours), four homework assignments. In the case of less than 5 registered students, the retake exams may be given in oral form.

The examiner, in consultation with Disability Support Services, may deviate from the regular form of examination in order to provide a permanently disabled student with a form of examination equivalent to that of a student without a disability.

Parts
Code: 0115. Name: Examination. 
Credits: 7,5. Grading scale: TH. 
Code: 0215. Name: Homework Assignment 1. 
Credits: 0. Grading scale: UG. 
Code: 0315. Name: Homework Assignment 2. 
Credits: 0. Grading scale: UG. 
Code: 0415. Name: Homework Assignment 3. 
Credits: 0. Grading scale: UG. 
Code: 0515. Name: Homework Assignment 4. 
Credits: 0. Grading scale: UG. 

Admission

Assumed prior knowledge: Basic knowledge within mathematics, mathematical statistics, and linear dynamical systems, including Linear Algebra, Calculus in Several Variables, Mathematical Statistics, Basic Course, and Linear Systems or Automatic Control, Basic Course. 
The number of participants is limited to: No

Reading list

• D. Easley & J. Kleinberg: Networks, crowds and markets, reasoning about a highly connected world. Cambridge University Press, 2010, ISBN: 978-0-521-19533-1. Supplement to lecturer's notes.
• R. Van Der Hofstad: Random Graphs and Complex Networks. Supplement to lecturer's notes. Online available at http://www.win.tue.nl/~rhofstad/.
• D. Levin, Y. Peres, E. Wilmer: Markov chains and mixing times. American Mathematical Society, 2009, ISBN: 978-0-8218-4739-8. Supplement to lecturer's notes.

Contact and other information

Course coordinator: Giacomo Como, giacomo.como@control.lth.se