A Practical Guide to Graph Theory and its Applications
Introduction to Graph Theory
For many real-world problems like social networks, logistics and supply chains, and geographical locations, the relationship between elements can be extremely complicated. Traditional computational methods may fail to capture the dynamics, while graphs provide an intuitive alternative representation.
The two base elements of Graph Theory are node (or vertex) and edge.
A node represents an entity, which can be a person, company, object, word, activity, or even a statistic distribution, depending on the context. An edge connects different nodes, representing the relationship between entities. For example, in a social network, nodes can be users. Two nodes are connected if two users follow each other. Note that the edge can have directions: if only user1 follows user2, the edge will point from 1 to 2, and the graph becomes a directed acyclic graph (DAG).
The graph representation is very flexible. We can freely change our definition of nodes and edges to adapt to different situations. Still, under the context of a social network, we can relax the definition of nodes to include both users can hashtags. If a user posts with a hashtag, the one-sided edge is connected.
In another setting like finance, the entities can be companies and people, and edges can have different types. For example, if a node connects an individual with a company, it may mean that an individual works in this company. To give another example, if an edge connects company A to B, it may mean that company A is company B’s subsidiary, or it may mean that a transaction happened between them (depending on the edge type). Another example could be a policy change that applies to all companies, such as “interest rate increases for 0.01%”.
Other than simplifying the representation of relationships, graph theory generates efficient data structures, such as adjacency matrix and adjacency list, speeding up the process of querying large-scale network data. A set of high-efficiency algorithms comes with this data structure as well to deal with problems like pathfinding, network flow, and minimal spanning trees. The graph representation can also uncover hidden patterns and structures of data, like using community detection to find communities in social networks or identify important functional modules in biological networks.
First, let’s learn about some basic properties of a graph.
Graph Properties
When we first get a network, before running more advanced algorithms, it’s important to check for basic properties to understand the scale and nuances. Checking these properties also serves as a sanity check to see if the graph is constructed properly from raw data.
Size: the size of the network is measured by the number of nodes and edges inside. The larger these numbers are, the larger the network is.
Connectivity: a graph is said to be connected if every pair of nodes is connected by an edge. If the target is an isolated node, no matter how you apply the shortest path algorithm, you can never reach the target.
Degree: the degree of a node is the number of edges connected to it. It can be interpreted as the importance of this node. For example, in a social network, a node of a hashtag has a degree of 10k+, which indicates it’s a trending hashtag.
Degree Centrality: As opposed to the idea of degree measuring how many edges are connected to the node, Degree Centrality measures how many nodes are connected to this node across all available nodes. The larger this fraction is, the more central the node is.
Eigenvector Centrality: This is an alternative measure of the influence of a node in a network.
Density: Density is the ratio of the number of edges in the graph to the number of possible edges. Under the context of a geographical map, a denser network means there are more ways to get to the same location.
Below is an implementation to check for properties.
import networkx as nx
import matplotlib.pyplot as plt
# Randomly generate two sample networks
G1 = nx.gnp_random_graph(100, 0.05) # Network with 100 nodes and probability of edge creation 0.05
G2 = nx.barabasi_albert_graph(100, 5) # Network with 100 nodes and each new node attaching to 5 existing nodes
# Function to calculate and display network properties
def display_network_properties(G, title):
print(title)
print("Size (Number of Nodes, Number of Edges):", G.number_of_nodes(), G.number_of_edges())
print("Connectivity:", nx.is_connected(G))
print("Average Degree:", sum(dict(G.degree()).values()) / G.number_of_nodes())
print("Degree Centrality:", nx.degree_centrality(G))
print("Eigenvector Centrality:", nx.eigenvector_centrality(G))
print("Density:", nx.density(G))
plt.figure(figsize=(8, 6))
nx.draw(G, with_labels=True, node_color='darkorange', edge_color='black', node_size=500, font_size=10)
plt.title(title)
plt.show()
# Display properties of both networks
display_network_properties(G1, "Network 1 Properties")
display_network_properties(G2, "Network 2 Properties")
Network 1 Properties
Size (Number of Nodes, Number of Edges): 100 255
Connectivity: False
Average Degree: 5.1
Degree Centrality: {0: 0.04040404040404041, 1: 0.10101010101010102, 2: 0.04040404040404041, 3: 0.05050505050505051,...}
Eigenvector Centrality: {0: 0.08573698036589154, 1: 0.19821127617924633, 2: 0.06600198247158846, 3: 0.09301694162048013, ...}
Density: 0.051515151515151514
Network 2 Properties
Size (Number of Nodes, Number of Edges): 100 475
Connectivity: True
Average Degree: 9.5
Degree Centrality: {0: 0.24242424242424243, 1: 0.25252525252525254, 2: 0.020202020202020204,...}
Eigenvector Centrality: {0: 0.22568603949007462, 1: 0.22396458722124163, 2: 0.020094083599075205, 3: 0.14722235706904777, ...}
Density: 0.09595959595959595Community Detection Algorithm
The community detection algorithm is the process of putting interconnected nodes together as a cluster. In social networks, the same community could be people with similar friends or similar topics. Below are two commonly used algorithms:
Girvan-Newman algorithm performs hierarchical clustering on the network G. The algorithm iteratively removes edges from the network to identify communities of nodes that are more densely connected to each other than to the rest of the network. This is very slow on large networks.
Louvain algorithm is a simple method to extract the community structure of a network based on modularity optimization.
Let’s see how see perform differently on the same network.
import networkx as nx
import community as community_louvain
import matplotlib.pyplot as plt
import random
# Generating a random graph as an example dataset
G = nx.gnp_random_graph(100, 0.05)
# Community Detection with Girvan-Newman Algorithm
def apply_girvan_newman(graph):
start_time = time.time()
communities = nx.community.girvan_newman(graph)
top_level_communities = next(communities)
sorted_communities = sorted(map(sorted, top_level_communities))
end_time = time.time()
return sorted_communities, end_time - start_time
# Community Detection with Louvain Algorithm
def apply_louvain(graph):
start_time = time.time()
communities = nx.community.louvain_communities(graph)
top_level_communities = next(communities)
sorted_communities = sorted(map(sorted, top_level_communities))
end_time = time.time()
return sorted_communities, end_time - start_time
# Applying Girvan-Newman Algorithm
gn_communities, gn_runtime = apply_girvan_newman(G)
print("Number of clusters with Girvan-Newman:", len(gn_communities))
print("Girvan-Newman Runtime:", gn_runtime, "seconds")
# Applying Louvain Algorithm
l_communities, gn_runtime = apply_girvan_newman(G)
print("Number of clusters with Louvain:", len(l_communities))
print("Louvain Algorithm Runtime:", gn_runtime, "seconds")
# Visualization function
def visualize_communities(graph, partition, title):
plt.figure(figsize=(8, 8))
pos = nx.spring_layout(graph)
cmap = plt.cm.get_cmap('viridis', max(partition.values()) + 1)
nx.draw_networkx_nodes(graph, pos, partition.keys(), node_size=100,
cmap=cmap, node_color=list(partition.values()))
nx.draw_networkx_edges(graph, pos, alpha=0.5)
plt.title(title)
plt.show()
# Visualize Girvan-Newman Communities
visualize_communities(G, {node: i for i, comm in enumerate(gn_communities) for node in comm},
"Girvan-Newman Community Detection")
# Visualize Louvain Communities
visualize_communities(G, {node: i for i, comm in enumerate(l_communities) for node in comm},
"Louvain Community Detection")
'''
Number of clusters with Girvan-Newman: 3
Girvan-Newman Runtime: 0.201002836227417 seconds
Number of clusters with Louvain: 3
Louvain Algorithm Runtime: 0.19770240783691406 seconds
'''We can observe the number of communities detected is the same for this small network, but the elements are slightly different, with the second algorithm being slightly faster.
Shortest Path Algorithm
Another common algorithm with graphs is the Shortest Path Algorithm. This usually happens when a graph is densely connected, with more than one option to go from one node to the other, and we want to figure out the shortest way.
To calculate the shortest path, we use Dijkstra's algorithm.
Initialization
At the starting node, let the distance of the starting node to itself be 0, all others being infinity.
Iteration
Among all unvisited nodes, visit the unvisited node with the smallest distance from the starting node
For each unvisited node, calculate the distance from the starting node. If it’s smaller than the known distance, replace it with the calculated distance, and choose the one with the smallest distance as the path to the next node.
Repeat the whole process until all nodes are visited.
This algorithm may look complex, but after initialization, all operations at each step are exactly the same. Here is a clear visualization of this algorithm.
import networkx as nx
import matplotlib.pyplot as plt
import random
# Generate a random graph
G = nx.gnm_random_graph(10, 15)
source = random.choice(list(G.nodes()))
target = random.choice(list(G.nodes()))
# Calculate the shortest path using Dijkstra's algorithm
shortest_path = nx.shortest_path(G, source=source, target=target)
# Visualize the path
node_colors = ['lightblue' if node == source else 'lightgreen' if node == target else 'white' for node in G.nodes()]
edge_colors = ['blue' if (u, v) in zip(shortest_path, shortest_path[1:]) else 'gray' for u, v in G.edges()]
pos = nx.spring_layout(G, seed=42)
nx.draw(G, pos, node_color=node_colors, edge_color=edge_colors, with_labels=True, node_size=500, font_size=10, font_color='black')
edge_labels = {(u, v): f"{G[u][v].get('weight', 1):.2f}" for u, v in G.edges()}
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=8)
plt.title(f"Shortest Path from Node {source} to Node {target}")
plt.show()The shortest path is highlighted in blue.
Visualization Libraries
While a graph is indeed a simpler representation than numbers, when it grows larger and denser, visualization can become harder.
NetworkX
NetworkX (the one we’ve been using) is a popular library in Python with a wide range of graph algorithms. It has some flexibility with visualization, like reordering the nodes or circling them around a certain shape. But it’s static, which means when a network contains more than 100 nodes, we cannot locate each node exactly.
JavaScript
JavaScript libraries provide more interactive functionalities and are commonly used for websites and software. They allow users to zoom in and out, select and highlight certain nodes and edges with colors, and drag nodes to other places.
Cytoscape.js
Sigma.js
Neo4j
We are only scratching the surface...
If you're interested in learning more about how to implement your graph use case, feel free to reach out to us by leaving your contact information!
View certificate