Introduction to Graph Theory and Complex Networks Analysis

Multiple problems can be modeled based on entities and their relationships. Graph theory (GT) allows us to define nodes and connections between them to represent and analyze complex processes found in various areas of science and technology. Today, there is a large amount of data that can be used to understand our world from things and their relationship between them and its ecosystem.

In this course, we start with an introduction to GT and complex network analysis with an application using Social media data. We will explore widely used tools from GT, network’s topology metrics, most common centrality measures, and some applications. We will code in Python and will explore libraries to create, explore, analyze, and visualize complex networks. To this purpose, we will create graphs by using NetworkX library, NumPy and Pandas for data transformation, and Matplotlib for data visualization. We will get into longitudinal analysis of evolving networks based on topology and centrality metrics. At the end of these course, you will be able to create, analize, and visualize complex networks.

Learning Objectives

At the end of this course, you will learn about the followings:

• Introductory concepts about Graph Theory (GT) and its applications.

• Create, analyze, and visualize networks created using NetworkX module.

• Caracterize and compare networks using properties of network’s topology.

• Using traditional centrality metrics and distinguish between them for practical applications.

• Performing analyzes for networks which changes across time (longitudinal analyses).

Prerequisites

It requires experience in Python using NumPy and Matplotlib or other similar packages or programming languages. Basic notions of linear algebra are desirable.

References

This content is mainly based on two references:

1. Van Steen, M. (2010). Graph theory and complex networks. An introduction.

2. Newman, M. (2010). Networks: An Introduction.

The full list of references can be found at the very end of each section (jupyter notebook).

I should mention that the original material was from the course “Data Mining and Learning”, Master in Informatics program. Austral University of Chile, Faculty of Engineering Sciences, Chile. I have modified the contents to suit my own needs and preferences. I would like to thank the creators for this material.