Graph algorithms and models
LTCC Advanced Module -- February-March 2018
Dr. Vincenzo Nicosia
School of Mathemathical Sciences
Queen Mary University of London
All the lecture notes, reading material, and documentation about the
module is available in the git repository of the module at the
The repository contains also detailed information about the available
topics for the final independent project.
The course will provide the students with a solid
understanding of theoretical aspects and algorithms related to the
computation of graph properties (components, paths, subgraphs,
clusters, centrality), to the sampling of graphs from random
ensembles, and to the modelling of real-world networks by means of
- Introduction to graphs and networks. Definition of
graph; definition of algorithm; elements of time complexity;
representing graphs; adjacency matrix; sparse representations.
Basic node and graph properties. Degree and degree
correlations; walks and connectedness; paths and distances;
eigenvector centrality; betweenness; PageRank.
Meso-scale properties. Small subgraphs and motifs;
Random graph ensembles. Erdos-Renyi graphs;
Watts-Strogatz graphs; configuration model; scale-free random
graphs and preferential attachment; (a few more advanced models,
if time allows for it).
The assessment for this module is based on a final independent
project. Each student will work on one of the proposed projects,
contributing and sharing material with all the other students
working on the same topic.
The final mark of each student will be obtained from:
- Quality of participation to the joint presentation (20%)
- Quality of the individual report (80%)
V. Latora, V. Nicosia, G. Russo, ``Complex Networks: Principles,
Methods and Applications'', Cambridge University Press (2017).
M. Newman, ``Networks: an introduction'', Oxford University Press
M. E. J. Newman, ``The structure and function of complex
networks'', SIAM Review 45, 167-256 (2003).
S. Boccaletti, et al. ``Complex Networks: Structure and
Dynamics'', Phys. Rep. 424, 175--308 (2006).