An Introduction to Graph Theory and Network Analysis (with Python codes)

Introduction

Graphs provide a powerful way to represent and analyze relationships and connections between objects. A graph consists of a set of vertices (also called nodes) which are connected by edges. Many real-world phenomena can be represented as graphs, from social networks to transportation routes, computer networks, and biological and chemical structures.

Graph theory is the study of graphs and their properties. It has a long and rich history dating back to the 18th century, but has seen a surge of interest and applications in recent decades due to the growth of computer science, social networks, and large datasets. Analyzing graphs provides valuable insights about the structure, relationships, and dynamics of many complex systems.

Graph theory and network analysis have become important tools in data science and machine learning. They are used for tasks such as:

• Analyzing social networks to find key influencers, communities, and viral trends
• Optimizing transportation and logistics networks
• Studying the spread of diseases, information, and fake news
• Recommending products and friends in online networks
• Analyzing computer and communication networks for performance and security
• Modeling chemical and biological structures and reactions

With the scale and ubiquity of data in today‘s world, graph algorithms and network analysis are more important and applicable than ever for data scientists. The Python programming language provides powerful tools to represent and analyze graph data. In this article, we will provide an introduction to the key concepts in graph theory, demonstrate how to work with graphs in Python, and walk through an example analysis on a real-world dataset.

History of Graph Theory

The origins of graph theory date back to 1736 when the Swiss mathematician Leonhard Euler published a paper on the famous Seven Bridges of Königsberg problem. The city of Königsberg (now Kaliningrad, Russia) was divided by a river with two islands, connected by seven bridges. Euler proved that it was impossible to walk a path that crossed each bridge exactly once and returned to the starting point, laying the foundations for graph theory.

Over the next two centuries, important contributions were made by a number of mathematicians:

• 1845: Gustav Kirchhoff used graph theoretical ideas in his study of electrical networks
• 1852: Francis Guthrie posed the four color problem, proving that any map can be colored using four colors so that no two adjacent regions have the same color
• 1856: Thomas Kirkman and William Hamilton studied cycles on polyhedra and invented the concept of a Hamiltonian cycle
• 1857: Arthur Cayley used trees to enumerate isomers of saturated hydrocarbons
• 1869: Jordan defined graph automorphism and congruence
• 1890: Petersen graph discovered, leading to concepts of factorization, thickness, and coloration

In the 20th century, graph theory became more applied and interdisciplinary, interacting with fields such as physics, psychology, biology, and sociology. Dénes Kőnig‘s 1936 paper on bipartite graphs was influential in establishing graph theory as its own field of study. Other pioneering graph theorists of this period include Erdős, Brooks, Menger, Kuratowski, Hall, Tutte, and Ore.

From the 1960s to today, computers have made it possible to study graphs on a much larger scale, leading to the analysis of real-world networks with millions or billions of nodes. In recent decades graph theory has become an important part of computer science and data science, with applications in optimization, machine learning, computer vision, network science and more.

Graph Theory Concepts and Terminology

Here are some of the key concepts in graph theory:

• Vertices/Nodes: The fundamental units of a graph, which represent objects or entities. Usually represented by a circle with a label.

• Edges: The connections between vertices in a graph, representing relationships or interactions between them. Represented by a line between two vertices.

• Directed vs Undirected Graphs: In a directed graph, edges have an orientation from one vertex to another. In an undirected graph, edges have no direction associated with them.

• Degree: The number of edges connected to a vertex. In a directed graph, vertices have both an in-degree and out-degree.

• Adjacency: Two vertices are adjacent if they are connected by an edge. Two edges are adjacent if they share a common vertex.

• Path: A sequence of edges connecting a sequence of vertices. The length of a path is the number of edges traversed.

• Cycle: A path that starts and ends at the same vertex, with no repeated edges. A graph with no cycles is acyclic.

• Connectedness: A graph is connected if there is a path between all pairs of vertices. A connected component is a maximal connected subgraph.

• Tree: A connected acyclic graph. A forest is a disjoint union of trees.

• Complete Graph: A graph where every pair of vertices is connected by an edge. The complete graph on n vertices is denoted K_n.

• Bipartite Graph: A graph whose vertices can be divided into two disjoint sets, such that every edge connects a vertex in one set to one in the other set.

• Subgraph: A graph formed from a subset of vertices and edges of a larger graph. An induced subgraph includes all edges whose endpoints are both in the vertex set.

• Clique: A complete subgraph, i.e. a subset of vertices such that every pair is connected by an edge.

These fundamental concepts form the building blocks for more advanced algorithms and metrics in graph theory and network science. We‘ll explore some of these later in this article.

Creating and Analyzing Graphs in Python

The Python programming language provides several libraries for working with graph data. One of the most popular and full-featured is NetworkX. It provides a simple interface to create, manipulate, and study the structure and dynamics of complex networks.

First, let‘s install and import networkx and matplotlib for visualization:

!pip install networkx matplotlib
import networkx as nx
import matplotlib.pyplot as plt
%matplotlib inline

Now let‘s create a simple undirected graph with 5 nodes and 4 edges:

G = nx.Graph() 
G.add_nodes_from([1,2,3,4,5])
G.add_edges_from([(1,2),(1,3),(2,3),(3,4)])

We can access the nodes and edges of the graph using:

G.nodes()
G.edges()

To visualize the graph:

plt.figure(figsize=(8,5))
nx.draw_networkx(G, with_labels=True, node_size=500, node_color=‘lightblue‘, font_size=20)

NetworkX provides many functions to compute graph metrics and algorithms. Here are a few examples:

# Number of nodes and edges
G.number_of_nodes() 
G.number_of_edges()

# Degree of each node
G.degree()

# Shortest path between two nodes
nx.shortest_path(G, source=1, target=5)

# Centrality measures
nx.degree_centrality(G)
nx.betweenness_centrality(G)
nx.closeness_centrality(G)

# Connected components  
nx.number_connected_components(G)
list(nx.connected_components(G))

# Clustering 
nx.clustering(G)

# Check if graph is bipartite
nx.is_bipartite(G) 

These just scratch the surface of NetworkX‘s capabilities. It contains over 100 graph algorithms, with new ones added regularly, including community detection, link prediction, network simplex, and many more. It also supports directed graphs, weighted graphs, and multigraphs.

Analyzing Airline Routes Network

To demonstrate some of these concepts on real data, let‘s analyze a dataset of airline routes. The dataset contains over 60,000 routes between over 3,000 airports on more than 500 airlines around the world. Each row contains the airline, origin and destination airports, and the number of stops.

First load the data into a pandas DataFrame:

import pandas as pd
df = pd.read_csv(‘airline_routes.csv‘)
df.head()

Clean and prepare the data:

# Drop rows with missing values
df = df.dropna() 

# Rename columns
df = df.rename(columns={‘airline‘:‘Airline‘, ‘source airport‘:‘Source‘, ‘destination apirport‘:‘Destination‘})

# Remove rows with unknown airport codes
df = df[(df.Source != ‘\\N‘) & (df.Destination != ‘\\N‘)]

Create a graph where nodes represent airports and edges represent routes:

G = nx.from_pandas_edgelist(df, source=‘Source‘, target=‘Destination‘, create_using=nx.Graph())
print(nx.info(G))

Name: 
Type: Graph
Number of nodes: 3372
Number of edges: 19256
Average degree:  11.42

Let‘s visualize the graph, using the longitude/latitude of airports for layout:

pos = {}
for airport, data in G.nodes(data=True):
    pos[airport] = (data[‘Longitude‘], data[‘Latitude‘])

plt.figure(figsize=(12,8)) 
nx.draw_networkx(G, pos=pos, node_size=10, alpha=0.4, node_color=‘blue‘)
plt.axis(‘off‘)
plt.show()

Although quite dense, this visualization shows the structure of the global airline network, with major hubs and continents clearly visible.

We can compute various statistics on this graph:

# Most connected airports
deg = nx.degree(G)
sorted([(airport,d) for airport, d in deg], key=lambda x: x[1], reverse=True)[:10]

[(‘ATL‘, 213),
 (‘FRA‘, 194),
 (‘CDG‘, 186),
 (‘ORD‘, 185),
 (‘AMS‘, 175),
 (‘IST‘, 171),
 (‘PEK‘, 168),
 (‘DXB‘, 168),
 (‘LHR‘, 165),
 (‘DFW‘, 165)]

# Longest flight
nx.edge_dfs(G, source=‘LHR‘, orientation=‘ignore‘)[-1][-1]

(‘SYD‘, ‘JFK‘)

# Average shortest path length
nx.average_shortest_path_length(G)

3.77

# Most central airports by betweenness centrality
centrality = nx.betweenness_centrality(G)
sorted(centrality.items(), key=lambda x: x[1], reverse=True)[:10]  

[(‘AMS‘, 0.14605390835973646),
 (‘FRA‘, 0.1447565158993157),
 (‘CDG‘, 0.13407600611805026),
 (‘IST‘, 0.10794287307284481),
 (‘LHR‘, 0.09723741699181314),
 (‘ATL‘, 0.08028392922756635),
 (‘PEK‘, 0.06635453526754358),
 (‘ORD‘, 0.06557924171498199),
 (‘KUL‘, 0.061726275976891655),
 (‘DXB‘, 0.05911601661786581)]

Lastly, let‘s find the shortest flight path between two airports:

nx.shortest_path(G, source=‘LAX‘, target=‘SIN‘, weight=‘stops‘)

[‘LAX‘, ‘NRT‘, ‘SIN‘]

This analysis demonstrates some of the insights that can be gained from applying graph theory to real-world network datasets using Python. By measuring the connectedness, centrality, and paths in the airline network, we can identify important hub airports, find efficient travel routes, and better understand the overall structure of global transportation.

Conclusion

In this article, we‘ve provided an introduction to the key concepts and techniques of graph theory and network analysis.
We‘ve covered:

• What graphs are and why they are useful for data science
• A brief history of graph theory from Euler to modern applications
• Essential graph terminology like nodes, edges, paths, centrality, etc.
• How to create and analyze graphs in Python using NetworkX
• An example analysis of a global airline transportation network

Graph theory offers a powerful set of tools for understanding and analyzing complex systems of interacting entities. As the volume of data and the scale of networks continues to grow, these techniques are becoming increasingly critical in data science, machine learning, computer science and related fields.

To learn more, here are some recommended resources on graph theory and network analysis:

• Easley and Kleinberg, Networks, Crowds, and Markets (2010) – An accessible textbook introduction to modern network science
• Barabasi, Network Science (2016) – A comprehensive textbook by a leading researcher in network theory
• NetworkX Documentation and Examples – Official guide to the NetworkX Python package
• Social and Economic Networks MOOC on Coursera – A popular online course taught by Matthew Jackson of Stanford
• The KONECT Project – A clearinghouse of large network datasets for testing algorithms

Armed with the concepts and tools we‘ve covered here, you‘re well equipped to start applying graph theory to real-world data science problems. We encourage you to explore this fascinating field further and see what insights you can uncover!