# Graph algorithms and models

### LTCC Advanced Module -- February-March 2018

Lecturer
Dr. Vincenzo Nicosia
School of Mathemathical Sciences
Queen Mary University of London
v.nicosia@qmul.ac.uk

Resources (Top)
All the lecture notes, reading material, and documentation about the module is available in the git repository of the module at the address:
The repository contains also detailed information about the available topics for the final independent project.

Syllabus (Top)
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 random graphs.
• 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; Cycles; Communities.
• 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).
• Mon. 19/02/2018 -- 15:10-17:10
• Mon. 26/02/2018 -- 15:10-17:10
• Mon. 05/03/2018 -- 15:10-17:10
• Mon. 12/03/2018 -- 15:10-17:10
• Mon. 19/03/2018 -- 15:10-17:10
Assessment (Top)
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%)
References (Top)
• V. Latora, V. Nicosia, G. Russo, ``Complex Networks: Principles, Methods and Applications'', Cambridge University Press (2017).
• M. Newman, ``Networks: an introduction'', Oxford University Press (2010).
• 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).