General Prerequisites:
Basic notions of linear algebra, probability, dynamical systems, and some computational experience. The student may use the language of their choice for computational experiments. Relevant notions of graph theory will be reviewed and illustrated.
Course Term: Michaelmas
Course Lecture Information: 16 lectures
Course Weight: 1
Course Level: M
Course Overview:
Network Science provides generic tools to model and analyse systems in a broad range of disciplines, including biology, computer science and sociology. This course aims at providing an introduction to this interdisciplinary field of research, by integrating tools from graph theory, statistics and dynamical systems. Most of the topics to be considered are active modern research areas.
This year the course has been altered to incorporate some new material on dynamically evolving networks and the analysis of scaling properties of growing networks.
Learning Outcomes:
Students will have developed a sound knowledge and appreciation of some of the tools, concepts, models, and computations used in the study of networks. The study of networks is predominantly a modern subject, so the students will also be expected to develop the ability to read and understand current (2010-2022) research papers in the field.
Course Synopsis:
Roughly week by week:
1. PRELIMINARIES. Probability theory; Renewal processes; Random walks; Power-law distribu- tions; Matrix algebra; Markov chains.
2. BASIC STRUCTURAL PROPERTIES OF NETWORKS. Network Definitions; Degree distribu- tion; Measures from walks and paths; Clustering coefficient; Centrality Measures; Spectral properties.
3. RANDOM GRAPH MODELS. Random Graphs; Erdo ̈s-Re ́nyi random graph; Stochastic Block model; Configuration model; Small World model; Growing network with preferential attachment.
4. COMMUNITY DETECTION: spectral method; Modularity
5. DYNAMICALLY EVOLVING NETWORKS: Markov chains of random graphs, application to triadic closure, via a mean field analysis
7. RANDOM WALKS : Discrete-time random walks on networks; PageRank; Models of epidemics
8. SCALING PROPERTIES OF GROWING NETWORKS: sequentially combining networks to form large growing networks.