What are the ideas behind Louvain clustering and why it can be useful in machine-learning.
We try to understand it in this brief post.
Louvain Clustering idea:
Louvain clustering is a network technique to understand what is the best way to cluster into communities the data at our disposal.
Here is a slide that I presented recently and that summarizes the idea behind Louvain Clustering:
Let's break down these complex formulas. The first one, known as $Q^t$, is referred to as modularity. It's a concept that helps us understand whether the connections, or links, between two points (called nodes) in a network, specifically within a community, are random or not. In other words, it's about figuring out if these connections happen just by chance or if there's a pattern to them.
The Louvain method, a popular approach in network analysis, starts by trying to maximize this $Q^t$ value. Now, you might wonder, when is $Q^t$ at its highest? It reaches its peak when three conditions are met: first, the delta term is 1, indicating that i and j belong to the same community; second, the Adj_{ij} term is also 1, suggesting a direct connection between the nodes; and third, the fraction involving ks (which relates to the degree of nodes) is as small as possible, ideally zero. This latter term represents the expected number of edges between nodes i and j if they were randomly connected.
In other words, if the 3 conditions are met what the modularity is telling us is that city i and j belong to the same community, are connected on to the other and this is not by chance.
Ok now how does Louvain clustering algorithm works?
The Louvain clustering algorithm is a fascinating method for understanding the structure of networks. Here's a simplified explanation of how it works:
Maximizing Modularity: The first step involves looking at all the connections between pairs of nodes (points in the network) and figuring out how to group them into clusters in a way that maximizes the overall modularity. Remember, modularity ($Q^t$) is a measure that helps us understand how well-connected nodes are within their communities. In this step, we're essentially trying to find the best initial grouping of nodes that makes the most sense in terms of their connections.
Forming New Big Nodes: Once we have our initial clusters, we treat each cluster as if it were a single large node. This simplifies the network, turning it into a smaller version of itself where each 'big node' represents a cluster of the original nodes.
Iterative Refinement: The process is then repeated. We look at this simpler network and again try to find the best way to group these big nodes into clusters. With each iteration, we're looking to increase the modularity, refining the network's structure. We keep doing this until we can't improve the modularity any further – in other words, until our clusters are as meaningful and well-defined as they can be.
This iterative process of clustering, creating big nodes, and then re-clustering allows the Louvain algorithm to efficiently and effectively reveal the underlying structure of complex networks.
That's it. Nothing more!
How can Louvain clustering be useful in machine-learning applications?
In our recent research, we explored an intriguing question using a novel approach. We utilized the Louvain Clustering method, but with a twist. Our goal was to identify cities that are consistently similar to a given city 'i' over a period of years. In other words, we were looking for cities that remain in the same cluster as city 'i', indicating a stable similarity between them.
Here's the interesting part: we then selected these consistently similar cities, ranking them based on how often they were in the same cluster as city 'i'. These cities were used as a special training set for our prediction tasks. This approach allows for a more refined and relevant dataset, which is crucial for making accurate predictions about city 'i'.
For those who are keen to dive deeper into our findings and methodology, I'd recommend checking out the GEOINNO24 conference. You can download my presentation slides from the conference website for a more detailed overview. And if your curiosity is piqued, there's a QR code on the slides. Scanning this will take you directly to the latest version of our paper, where you can explore our work in greater depth. This is a great opportunity for anyone interested in the intersection of urban studies, data science, and machine learning.