LTCC Module on Graph Algorithms and Models 2019

Material related to the LTCC module "Graph algorithms and models".

Please also have a look at the module's website at:

[http://www.maths.qmul.ac.uk/~vnicosia/LTCC2019]

C implementations of all the algorithms presented in the module are available at:

[https://www.complex-networks.net]

Module structure

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.

The module consists of 10 face-to-face contact hours (lectures), and is assessed through a final independent project. Please see the section Assessment and the section Projects below.

Syllabus

• 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).

Lectures

The module consists of 5 2-hour lectures, as detailed below:

• Mon. 18/02/2018 -- 10:50-12:50
• Mon. 25/02/2018 -- 10:50-12:50
• Mon. 04/03/2018 -- 10:50-12:50
• Mon. 11/03/2018 -- 10:50-12:50
• Mon. 18/03/2018 -- 10:50-12:50

Lecture notes

The lecture will make available lecture notes in electronic format (PDF) after each lecture. Have a look to the folder lecture_notes.

Lecture reading

Students are supposed to read some material before each lecture. The relevant material is normally sent out by Wednesday on the week before the lecture. Have a look to the folder reading_material.

Assessment

The summative assessment of the module is based on two components, namely:

• A group presentation (20% of the final mark)
• An individual project (80% of the final mark)

The group presentation will be due two weeks after the end of the module (tentatively, during the first week of April). Independent projects will be due by Friday 19th April 2019.

The marking scheme is as follows:

• A Grade: The student shows a very good understanding of the material.

• B Grade: The student has demonstrated familiarity with a significant amount of material.

• C Grade: The student has demonstrated minimal familiarity with some of the material.

Projects and presentations

During the module, each student will work on an independent project in one of four available topics, namely:

1. Centrality git repo
2. Subgraphs git repo
3. Communities git repo
4. Random graphs git repo

For his/her project, each student will choose to work on one or two of the tasks proposed for the selected topic. More information about specific topics and tasks are available in the folder topics.

All the students working on a topic will join the corresponding git repository and will share all the material they find relevant for that topic with all the other students interested in that topic. This means that all the students working in a topic will contribute references, software, slides, links, papers, data sets, etc. through the corresponding topic repository, so that the material will be accessible and usable by all the members of that topic.

Basic information and tutorials about using git are available in the folder docs.

At the end of the module, all the students working on a topic will prepare a joint presentation to provide an overview to the topic, including also their findings and results. This presentation will contribute 20% of the final mark. The main aspect assessed through the joint presentation is the ability of students to collaborate with others, share results, and provide an informative synthesis of a piece of research.

Then, each student will prepare and submit an individual report about his/her own research on the topic. The project report will contribute 80% of the final mark. The main aspect assessed through the individual project report is the actual knowledge of the student on the selected topic.

IMPORTANT NOTE

Each student must share with the other students working on the same topic all the results, references, data sets, software, etc. that he/she will use for the individual project. Nevertheless, the individual report must be original, and must be completed by each student independently