Network Algorithms - Jupyter Notebooks

We prepared the following Jupyter Notebooks to demonstrate the concepts covered this week.

The links below point to static (HTML-based) versions of the notebooks - they look just like the real thing, but you will not be able to modify the code within or interact with the visualizations. You can download the actual Jupyter notebooks from the link at the end of this page.

  • 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 obtain the shortest paths. We are also experimenting with a few centrality measures.

  • Working with datasets: This notebook introduces Pandas, a powerful library used to manipulate large and complex datasets.

  • Network Analytics: We will cover here the use of NetworkX to generate key metrics that describe the structure of a given network.

  • Weighted and directed graphs: We will now explore the definition and manipulation of more complex graph structures. We will also learn how to define custom functions, allowing us to reuse parts of our code efficiently.

  • Studying the London Underground: Here we will apply the concepts that we covered so far in a much larger network - a subset of the London Underground. We will also use more advanced Pandas features to filter and clean up our dataset as we seek to highlight specific outputs of our analysis.

  • k-means clustering: Here we demonstrate the use of the K-means algorithms provided by the sklearn module. Beyond its usefulness for network analysis, this technique is widely used by machine learning practitioners to classify large datasets.

  • Hungarian algorithm: In this final notebook, we discuss a few implementations of the Hungarian algorithm that you could use to solve assignment problems.

Running the notebooks

You can download a zip file that contains all notebooks (including the datasets used in the examples) from the link below.

Before you are able to run notebooks, you must make sure that you have correctly set up your Anaconda environment (as discussed in last week’s seminar).

The notebooks use a range of Python packages. Most of them will be installed by default through the Anaconda installation. If this is not the case, you can install them all using the following pip install command:

pip install numpy matplotlib pandas sklearn networkx yellowbrick seaborn

For a reminder on how to set up your Anaconda environment and install additional Python packages, you can refer to the documents provided in Seminar 1.