Introduction to Graph Clustering

Previously I wrote a blog on how to divide the countries of the world into 10 even groups. While I did the grouping manually and intuitively, I wonder if there is a more scientific way to do the same. After some research, there are indeed many methodologies in doing similar task. In this blog, I will go through some of these.

Before we begin, let me explain some basic terminology in the science of map and grouping:

• Vector: a list of numbers.
• Matrix: a table of numbers.
• Graph: a group of related and connected objects. In our case, it is the world map.
• Vertex or node: the object in a graph, e.g. the numbered circles in the diagram below. In our case, these are the countries.
• Edge: the line connecting the vertices. In our case, these can be the country borders.
• Clustering: the process of grouping nodes, which is what I am trying to do here.

To explain the different methods, in this blog I will attempt to divide the South American countries into two groups. South America is used because it is relatively simple with only 12 countries (excluding France), and there are no island countries (because for island countries we need to decide how to set the edges, more on that later).

Hierarchical clustering is to build clusters like a family tree. It can either starts bottom-up by merging smaller clusters into larger ones, or top-down by breaking down large clusters into smaller ones. Here I will use the first method on the South American countries.

First treat the 12 countries as 12 clusters, and calculate the distance between each of them (I am using the capitals here).

It turns out that Argentina (Buenos Aires) and Uruguay (Montevideo) are the closest together, so let's merge them to form a new cluster. Now, recentre Argentina + Uruguay and recalculate the distance between it and the remaining nodes:

The next closest pair is Guyana + Suriname (346 km). So merge these, recalculate the distance and repeat the process until it forms the number of desired clusters (in my case, until two left). The whole process can be drawn out like a tree (no this is not the result of the Copa América 😛):

K-means is a popular way to group points closed to each other into k number of clusters. It starts by having an educated guess on the centroids of the clusters and then iteratively improving the location of the centroids until they converge (i.e. they stop changing).

In my example, I am trying to form 2 groups (k = 2). Again I use the capitals to represent the location of each country, and I start by randomly setting the two centroids at Lat/Long {0, -70} (near the border between Colombia & Brazil) and {-20, -50} (southwest of Brasilia).

The next step is to check whether the capitals are closer to Point 1 or Point 2.

This gives us the preliminary grouping of the capitals/countries. The next step is to recalculate the two centroids based on the two groups.

• Point 1 (green): {-0.1435, -68.2838}
• Point 2 (blue): {-28.7952, -58.1563}

You can see how the centroids move and "improve". Now repeat the calculation of the distances between the capitals and the two new centroids:

You can see that Bolivia is now switched to Group 2. Keep repeating the same until the centroids and the groupings do not change anymore, and now you have the two clusters.

So far the two methods above are purely based on the distance between the country capitals. We have not considered the country border (edges) yet. The issue is that in the case of non-bordering countries that are near each other (e.g. Djibouti & Yemen), these will likely be put into the same cluster although they are 7 edges apart.

To properly consider the relationship between countries based on borders, we do need to look at the edges and turn the countries into a graph as I mentioned earlier. (Again for simplicity sake, I am ignoring France and Panama)

Spectral clustering requires some basic understanding of linear algebra which I will not go into the details of the maths behind it (I don't know that well myself either 😅). Rather I would show you how it is done. In this method, there are three steps involved:

1. Construct a Laplacian matrix representation of the graph.
2. Compute the eigenvalue and eigenvector of the matrix.
3. Apply the eigenvector to the nodes to form the clusters.

Let's see how it is done. In simple term, the Laplacian matrix is a table of numbers that represents the above graph. You can read the Wikipedia page to learn more, but basically the formula is L = D - A, or put simply, a table where the diagonal is the number of edges (number of bordering countries), and the rest of the numbers are either 0 if they don't border each other, or -1 if they do. (Note that all rows and columns sum up to 0). So for South America, the Laplacian matrix looks like this:

The next step is to find the eigenvalue and eigenvector of the above matrix. In simple term, the eigenvector (v) is a special vector of a matrix (T) such that multiplying by it will scale the vector linearly by a constant eigenvalue (λ), i.e. Tv = λv. You can think of it as a way to enlarge a photo without distorting it.

There is no magic formula to calculate the eigenvalue and eigenvector of a matrix. The simplest way is to use the Excel Goal Seek tool under What-If Analysis to iterate until it finds the best possible answer. I will not go through the method here, but you can check out YouTube videos such as this and this on how this can be done. (Or if you are already using Matlab then you don't need me to teach you how).

With that, it calculates the second smallest eigenvalue of our Laplacian matrix to be 1.08958 (you don't want the eigenvalue of 0 which is useless to us), and the corresponding eigenvector is

Applying the eigenvector to our list of countries and sorting it, we have a group of countries with negative numbers and another group with positive numbers. i.e.

As you can see, since the South American countries are all well interconnected, it is difficult to form two distinct clusters. But when I apply the same calculation to both North and South America, the result is much more obvious.

Modularity is a way to quantify how closely related the nodes are within a cluster. In this method, we try to maximise the combined modularity score of the clusters so that we are putting closely related nodes together rather than unrelated ones.

The formula for calculating modularity looks quite daunting but it is actually much simpler than what it seems. Let me explain:

where
Q = modularity score, what we are trying to calculate for our clusters
m = total number of edges in our graph, i.e. total number of country borders
A_ij = adjacency score between node i and j, 1 if node i borders node j, or 0 if they don't
γ = resolution factor, equals to 1 by default unless you want to add weight to the expected probability of node i and j being connected
k_i and k_j = degrees of node i and j. In the standard case where we treat all borders equal, this is the number of borders (edges) that country i and j (node i and j) have.
δ(c_i, c_j) = Kronecker delta, just a fancy way to say that if i = j then it is 0 else 1, i.e. only add up when country i and j are different, e.g. count Argentina-Chile, not Argentina-Argentina.

So how does it work? Let's say we want to examine the modularity score of the two clusters formed by spectral clustering above. First there are in total 23 edges in the graph (23 borders, m=23). For Group 1, we need to sum up for all node pairs, e.g. for Chile - Argentina:

• A_ij = 1 (they do border each other)
• k_i = 3 (Chile borders 3 other countries)
• k_j = 5 (Argentina borders 5)

And for say Colombia - Bolivia,
 A_ij - (k_i k_j / 2m) = 0 - (4 x 5) / (2 x 23) = -0.435

So on so forth. The calculation gives Q₁ = 0.0681 and Q₂ = 0.0647, and hence a total score of 0.133.

Let's say I want to even out the number of countries in each group so I move Colombia to Group 2. Redoing the same calculation gives a new total score of 0.148, so it is not a bad idea! And if I want to have exactly 6 countries in each group so I move Peru to Group 2 too, the calculation gives a new total score of 0.124. So I should probably think twice before doing that.

There are many other methods of clustering, some are focusing on the finding the nodes that are closely connected to each other, others are trying to find nodes with similar topology, e.g. countries like Brazil, Germany, DR Congo are similar as they tie other countries together. Some methodology is limited to finding a small number of clusters (e.g. 2) and fails when trying to form larger number of clusters (e.g. 10 groups of COTW), or when there is no clear distinction among the nodes to form a cluster, or unable to ensure each cluster has the similar number of nodes.

Another consideration comes to how we define the edges, especially for island countries. There are only 4 bridges/tunnels in the world that connect non-neighbouring countries together, namely:

• United Kingdom - France: Channel Tunnel
• Denmark - Sweden: Øresund Bridge
• Bahrain - Saudi Arabia: King Fahd Causeway
• Singapore - Malaysia: Johor Causeway and others

For others, how should the edges be defined? For example, should Japan be connected to Russia, and Taiwan? and South Korea? Or should United States be connected to Russia? The Bahamas? Kiribati? How about the territories (e.g. Canada-Denmark)? And don't get me started on Cyprus (to Greece or not to Greece, that is the question 😄).

Besides, should all borders and edges be treated equal? They are in my calculation above, but not all borders are the same, e.g. there is no land crossing between Colombia and Panama. Some bordering countries are culturally and geopolitically very far apart, e.g. Russia-North Korea, China-Afghanistan.

After reading all these, you may ask the question why? Why do we spend so much effort into clustering? It is very obvious to anyone that North and South America form two different groups without all these calculation. But we cannot always do it manually and visually, especially when the number of nodes is huge and the edges are complex.

The application of clustering goes far beyond countries and maps. What if these countries are high-schoolers and the graph represents their social network on TikTok? Should I push ad selling American goods to the popular Brazilian influencer who has so many connections? Clustering can help identify how genes are grouped together, or help AI identify objects in photos, or identify fraudulent activities in your credit card transactions, or for Natural Language Processing (NLP) to understand words (or dog barks) with similar meanings. And the opportunities are endless.

As you can see, doing these calculation manually is almost impossible (it's tedious and error-prone). People would write Python scripts and let machine learning do the hard work. If you find this interesting, study Discrete Maths and Data Science in university and your future is bright!

Advertisement time: I do have few quizzes here with graphs, have fun with these!