Session 3 - Network Analysis

Session 3 - Network Analysis #

Dr Panagiotis Angeloudis


Part 1 - Modelling Networks #

In the first part of this session, we focus on graph theory - the field mathematics that focuses on the analysis of graphs.

Download slides

Part 2 - Shortest Paths #

Download slides

We will be experimenting with Dijkstra’s algorithm during our tutorial session, and in the Notebooks provided later below.

Guide on the use of loose-end tables

Part 3 - Clustering Methods #

Download slides

Part 4 - The Transportation Problem #

Download slides

Guide on the use of the stepping-stone method

Jupyter Notebooks #

We have prepared the following three Jupyter Notebooks to demonstrate the concepts covered in Parts 1 to 4. Don’t worry, we haven’t forgotten about The Transportation Problem - we will be looking at it in more detail in our next session.

There are two ways to view these notebooks. The first one is the simplest - the links below point to their HTML versions. Please note however that these are static files - you cannot modify any code or interact with them in any way.

Notebook 3.1 - Introduction to NetworkX #

In this notebook we introduce NetworkX - a Python package that includes a wide range of graph theory algorithms. We will learn how to create a graph, visualize it, and also how to obtain the shortest paths. We are also experimenting with a few centrality measures.

Along the way, we will be learning how to load external files and store them in Pandas objects.

Notebook 3.2 - Weighted and Directed Graphs #

In this notebook we will be using NetworkX to study weighted and directed graphs. We will be building on the concepts that we followed in Notebook 2.1a, and will also introduce and use custom function definitions, which will allow us to reuse parts of our code without copying-pasting all the time.

Notebook 3.3 - Studying the London Underground #

Here apply the concepts that we covered in the previous notebook into the study of a much larger network - the London Night Tube.

We will be using some more advanced Pandas features to filter and clean up our dataset, as we seek to highlight certain outputs of our analysis.

Notebook 3.4 - K-means Clustering #

In this final notebook for this session, we will be demonstrating the use of the K-means algorithms provided by the sklearn package.

Running the notebooks #

I would strongly urge you to run the notebooks on your computers to understand how they work. It is a matter of time anyway until you will have to apply these concepts in practice in Assignment 2, which will be released next week.

Download notebooks

Tutorial session #

Tutorial 3 - Questions

Tutorial 3 - Answers

Files #

You can find a handy list of all files that we used this week here (Box).