Optimizing Connections: Mathematical Optimization within Graphs
In this post, we delve into the world of mathematical optimization within graphs, exploring key concepts, algorithms, and practical applications. Graph problems can be found in many places. Obvious ones are in logistics or social network analysis, like finding the optimal route for a delivery company or the lowest amount of connections between two people. But did you know that graphs are also applicable in urban planning, disease transmission modeling, fraud detection, recommendation engines, and cybersecurity? By leveraging optimization algorithms specifically designed for graphs, data scientists can uncover optimal solutions, allocate resources efficiently, and make data-driven decisions.
First, we'll start with an introduction section, to explain the basics of graphs. Then we dive into common graph problems and algorithms trying to solve these problems.
Graph Basics
As a recap, below the basics on Graph Theory.
What is a graph?
A graph consists of vertices (or nodes) and edges. If the vertices are related in a certain way, they are connected with an edge. To define a graph, you need the names of all the vertices and you need to know which vertices are connected.
Below a graph that has vertices {A, B, C, D, E} and edges {{A, D}, {A, E}, {B, C}, {B, D}, {C, D}}.
Sometimes, graphs can contain loops. A loop is an edge that has the same start and end node (a node is connected with itself).
Other terms that are nice to know in graph theory:
- The order of a graph is equal to its number of vertices.
- The size of a graph is the number of edges (sometimes plus the number of vertices).
- The degree of a vertex is the amount of edges it has (a loop is counted twice for the beginning and end point).
Common variations
The previous graph example is also called a simple graph, because it only contains vertices and (undirected) edges. But you can easily make it a bit more complex, and often more interesting, by providing additional information.
Below an example of a directed graph (a.k.a digraph), where the edges are pointed in a certain direction:
Another graph that is a fit in many situations is a weighted graph. In a weighted graph, the edges are associated with a weight: this can be anything, e.g. length or costs.
The last interesting graph variation discussed here is a multigraph. In a multigraph, the same edge can occur more than once:
Note: There are many special types of graphs with their own properties. E.g. a graph in which each pair of vertices is connected with an edge is called a complete graph.
From Problem to Graph
How to create a graph out of a problem? Let's go through some examples:
Locations and Distances
A classic problem is a problem for which you have locations and distances between the locations. In the adjacency matrix below, the distances between the locations are provided (if there is a distance greater than 0, there is an edge). From this matrix, you can easily create a graph.
A B C D E F G H I
A 0 3 1 2 0 0 0 0 0
B 3 0 1 0 4 3 0 0 0
C 1 1 0 0 0 3 0 0 0
D 2 0 0 0 0 1 0 6 0
E 0 4 0 0 0 0 2 0 0
F 0 3 3 1 0 0 3 1 0
G 0 0 0 0 2 3 0 0 1
H 0 0 0 6 0 1 0 0 5
I 0 0 0 0 0 0 1 5 0
You can also create matrices from a graph, common ones are the incidence and the degree matrix.
Let's replace the weights by the name of the edge:
No we can create the incidence matrix, it has a row for each node and a column for each edge. It shows which nodes are connected by an edge:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
A 1 1 1 0 0 0 0 0 0 0 0 0 0 0
B 1 0 0 1 1 1 0 0 0 0 0 0 0 0
C 0 1 0 1 0 0 1 0 0 0 0 0 0 0
D 0 0 1 0 0 0 0 1 1 0 0 0 0 0
E 0 0 0 0 1 0 0 0 0 1 0 0 0 0
F 0 0 0 0 0 1 1 1 0 0 1 1 0 0
G 0 0 0 0 0 0 0 0 0 1 1 0 0 1
H 0 0 0 0 0 0 0 0 1 0 0 1 1 0
I 0 0 0 0 0 0 0 0 0 0 0 0 1 1For a weighted graph, we can replace the ones by the weights of the corresponding edge.
The degree matrix is a diagonal matrix and counts the number of edges attached to each node. A loop is counted twice. For the previous graph, the degree matrix would be:
A B C D E F G H I
A 3 0 0 0 0 0 0 0 0
B 0 4 0 0 0 0 0 0 0
C 0 0 3 0 0 0 0 0 0
D 0 0 0 3 0 0 0 0 0
E 0 0 0 0 2 0 0 0 0
F 0 0 0 0 0 5 0 0 0
G 0 0 0 0 0 0 3 0 0
H 0 0 0 0 0 0 0 3 0
I 0 0 0 0 0 0 0 0 2Note: Official matrix form is without index row and index column. For clarity they are added.
Flows
Directed graphs often deal with network flows. E.g. in networks where data is transmitted, in transportation, or in pipelines. If you know how much the maximum capacity is between two nodes, you can create a network flow graph:
The source (s) and the sink (t) are the starting and ending point of the flow. The edges are directed, they show the direction of the flow between nodes.
Tree graphs
A special type of graph is a tree graph. You can find them in many different places: competition schedules, family trees, organizational charts and evolutionary trees. A tree is undirected, acyclic and connected. It should not contain a cycle or directed edges, and all nodes are connected to the tree.
A tree has interesting properties:
- It always has
n-1edges (wherenis the number of nodes). - There is a unique path between any pair of nodes in a tree.
- Removing a single edge will disconnect the graph (split the graph in two).
Social Network
Connections between people are nice to visualize in a graph. By analyzing relationships and visualizing them, you can extract valuable insights. Here is an example of 7 people, if they are connected on social media, they are connected with an edge:
Questions that can arise by looking at this graph are:
- Who are the most important people?
- Which persons are most similar to each other?
- Can we predict missing links?
- How can we cluster these people in the best way?
Common algorithms applied to graphs
After modeling a situation as graph, you can solve the problem at hand. For the different examples in the previous paragraph, we will apply algorithms to find the shortest path, calculate the Maximum Flow and minimum cut, determine the minimum spanning tree and touch upon topics in graph analysis.
Shortest Path
The first problem to solve is the shortest path problem: how should we go from A to B while keeping the route as short as possible?
Let's consider the following graph:
An algorithm that is used often for solving this problem is Dijkstra's algorithm. It works as follows:
Step 1. The starting node has distance 0. Set the rest of the nodes at distance infinity, this is their provisional distance. There are three types of nodes: visited, unvisited and the current node. For the first run the current node is the starting node.
Step 2. Look at the direct neighbors of the current node and calculate the distance to them (via the current node). If this distance is smaller than the smallest distance so far, replace the old distance with the new distance. To discover the fastest route, mark the new route if the distance is accepted (and remove previous marked route if that exists).
Step 3. Now the first node can be marked as visited (green), and the new current node will be the unvisited node with the lowest provisional distance (yellow node in the image below has distance 1). Continue with step 2 for this node, and repeat step 2 and 3 until the end node is reached.
If we repeat these steps, in the end the solved graph looks like this:
Now we found the shortest distance from the start node to every other node, together with the corresponding routes (green edges)! Dijkstra's algorithm is applied widely and popular because it is efficient and avoids unnecessary computations.
There are many more fun shortest path problems, like the Chinese postman problem, where you have to discover the shortest route while visiting all edges, or the traveling salesman problem where you have to visit all the nodes. The traveling salesman problem can be solved in many different ways, for example with mixed integer programming (example 2) or with simulated annealing (example 1).
Maximum Flow & Minimum Cut
An important question in flow graphs is: How much flow can be send from the source to the sink? The weights at the edges correspond to the capacity of an edge and those capacities can never be exceeded. The incoming flow for every node should be equal to the outgoing flow (except for the source and the sink).
Below an example of a maximum flow problem:
How can we solve this problem and discover how much flow can reach the sink? There are several different algorithms for this. Let's solve this using the Ford-Fulkerson algorithm.
Step 1. Set the initial capacity to 0 on all edges.
Step 2. Find an augmenting path from source to sink. This is a path that has unused capacity greater than 0 on all edges and starts at the source and ends at the sink. You can find augmenting paths with e.g. breadth first search or depth first search.
Step 3. For the augmenting path from step 2, we can find the bottleneck, this is the edge with the smallest remaining capacity. We increase the capacity on all edges for the augmenting path with this value.
Step 4. Continue with step 2 and 3 until there is no augmenting path left.
After continuing doing this, in the end there are no more augmenting paths possible. The end result can look like this:
The maximum flow is easily found by adding 11 + 1 + 4 = 16. These are the flows of the edges directed to the sink. This problem can also be solved with linear programming.
Related to maximum flow is minimum cut. The minimum cut is finding the lowest sum of weight of connections you need to disconnect to split the network into two separate parts. It is closely related to maximum flow, because when you found the solution of maximum flow, you can derive the minimum cut as well. They are equal to each other.
Minimum cut is used in image segmentation, for example to separate an object from the background. Another critical application of minimum cut is analyzing the reliability of complex networks, such as power grids or communication networks, by identifying critical edges whose failure can lead to network disconnection or reduced performance.
Minimum Spanning Tree
Imagine you are the boss of a railway company and you want to discover how to connect seven cities with the lowest amount of railway possible. What you are looking for in this case is the Minimum Spanning Tree. If we visualize this problem it looks like this:
How can we calculate the minimum spanning tree in this graph? We can use Prim's algorithm, which is a greedy algorithm and quite easy to understand.
Step 1. Choose one node of the graph to start with, arbitrarily. This node is the first part of the tree.
Step 2. Grow the tree by one edge. Select the edge that has the minimum weight of all edges connected to the tree.
Step 3. Repeat step 2 until all nodes are in the tree.
The next edge we select is the one with weight 3:
In the end, we found the minimum spanning tree with a total length of 17.
The minimum spanning tree has many different applications. The most straightforward one is network design, when a network has to be fully connected with the lowest weight. Examples of such networks are telecommunication networks, computer networks, electrical power distribution systems and transportation networks. Did you know that minimum spanning trees are also used in taxonomy, cluster analysis, feature extraction for computer vision and in handwriting recognition? If you dive into the applications of minimum spanning trees, you discover there are quite a lot!
Centrality & Similarity
Graph analysis leverages the tools and techniques developed in graph theory to gain insights and make informed decisions in different domains, such as social networks, transportation networks, computer networks, biology, and many others.
Centrality and similarity are two core concepts in graph analysis. You might have heard of the PageRank algorithm used by Google Search. PageRank is a centrality algorithm used to measure the importance or influence of nodes in a network, particularly in web page ranking and hyperlink analysis. It assigns a numerical score to each node based on the number and quality of incoming links, helping identify key nodes in a network.
Betweenness centrality is another measure of centrality. The node with the highest betweenness centrality acts as the most important bridge among all the other nodes. To find the betweenness centrality of a node, we need to look at all the pairs of nodes and see how many times each node appears on the shortest path between two other nodes. The node who appears on the most shortest paths is the one with the highest betweenness centrality.
In social networks or real-world systems, nodes (e.g. people, places, or entities) with high betweenness centrality play a crucial role in maintaining communication and connections between different parts of the network. They act as important mediators, ensuring efficient communication and keeping the network connected.
It can also be useful to find out how similar certain nodes are. This can be done by calculating node similarity. Jaccard Similarity is often used for unweighted graphs. It calculates the similarity between two nodes based on the number of common neighbors they share, divided by the total number of unique neighbors they have.
Let's calculate the Jaccard Similarity for node 2 and 4 in the graph. They share 2 neighbors (node 3 and 5), and the total number of unique neighbors is 5 (node 1, 2, 3, 4 and 5). 2 divided by 5 gives a Jaccard Similarity of 0.4.
Node similarity is used in collaborative filtering techniques to recommend items to users based on the similarity of their preferences with other users. It can also be used to predict missing or future links in a network or for detecting clusters and communities.
What's next?
This was just a glimpse into the world of graph theory and graph analysis. Beyond what we've explored here, there are many more exciting problems and applications waiting to be discovered. The beauty of graph theory lies in its versatility; it offers a way to tackle real-world challenges by transforming them into graph-based puzzles solvable with clever algorithms.
From social networks to logistics, countless real-world problems find their perfect match in the realm of graphs. Unraveling communities, uncovering hidden connections, and exploring the unique properties of different graph types are interesting aspects of graph theory.
In the realm of data science, graphs become allies, enabling the creation of features that can have a huge impact on model performance. Graph embeddings hold the key to unlocking new dimensions of understanding within vast datasets.
Hopefully, this post made you curious to dive deeper into the wonders of graph theory!
Related
Five ways to combine Mathematical Optimization and Machine Learning
Constraint Programming Explained
An Introduction to a Powerful Optimization Technique: Simulated Annealing
