C5.4 Networks - Archived material for the year 2016-2017

Dr Heather Harrington
General Prerequisites: 

None [in particular, C5.3 (Statistical Mechanics) is not required], though some intuition from modules like C5.3, the Part B graph theory course, and probability courses (at the level that everybody has to take anyway) can be useful. However, everything is self-contained, and none of these courses are required. Some computational experience is also helpful, and ideas from linear algebra will certainly be helpful.

Course Term: 
Course Lecture Information: 

16 lectures

Course Weight: 
1.00 unit(s)
Course Level: 

Assessment type:

Course Overview: 

This course aims to provide an introduction to network science, which can be used to study complex systems of interacting agents. Networks are interesting both mathematically and computationally, and they are pervasive in physics, biology, sociology, information science, and myriad other fields. The study of networks is one of the "rising stars'' of scientific endeavors, and networks have become among the most important subjects for applied mathematicians to study. Most of the topics to be considered are active modern research areas.

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 (2016) research papers in the field.

Course Synopsis: 

Introduction and Basic Concepts (1-2 lectures): nodes, edges, adjacencies, weighted networks, unweighted networks, degree and strength, degree distribution, other types of networks

Small Worlds (2 lectures): clustering coefficients, paths and geodesic paths, Watts-Strogatz networks [focus is on modelling and heuristic calculations]

Toy Models of Network Formation (2 lectures): preferential attachment, generalizations of preferential attachment, network optimization

Additional Summary Statistics and Other Useful Concepts (2 lectures): modularity and assortativity, degree-degree correlations, centrality measures, communicability, reciprocity and structural balance

Random Graphs (2 lectures): Erdős-Rényi graphs, configuration model, random graphs with clustering, other models of random graphs or hypergraphs; application of generating-function methods [focus is on modelling and heuristic calculations; material in this section forms an important basis for sections 6 and 7]

Community Structure and Mesoscopic Structure (2 lectures): linkage clustering, optimization of modularity and other quality functions, overlapping communities, other methods and generalizations

Dynamics on (and of) Networks (3-4 lectures): general ideas, models of biological and social contagions, percolation, voter and opinion models, temporal networks, other topics

Additional Topics (0-2 lectures): games on networks, exponential random graphs, network inference, other topics of special interest to students [depending on how much room there is and interest of current students]

Reading List: 

(most important are [2] and [3]):

  1. A. Barrat et al, Dynamical Processes on Complex Networks, Cambridge University Press, 2008
  2. M. E. J. Newman, Networks: An Introduction, Oxford University Press, 2010
  3. Various papers and review articles (see the Math C5.4 blog at http://networksoxford.blogspot.co.uk for examples). The instructor will indicate a small number of specific review articles that are required reading, and other helpful (but optional) articles will also be indicated.