So the algorithm that allows us to identify
high modularity score communities is- it's called uh,
the Louvain Algorithm, from the
University Louvain in Belgium.
That's why, uh, this name.
So it is a very scalable and very popularly- very popular algorithm.
Kind of it's a de facto thing you would use if you want to
partition the network into a set of clusters.
So Louvain algorithm is a greedy community detection algorithm that uh, scales uh, um,
ah, n log n,
where n is the number of nodes in the network so it can uh,
um, scale to large networks.
It supports weighted graphs, uh,
and it provides us hierarchical communities.
So it doesn't only provide us clustering at one level,
but it provides us kind of clustering of clusters.
So we get this notion of a tree or a dendrogram,
how individual nodes join into groups and how
these groups can then be further joined into the super groups uh, and so on.
Um, and as I said,
it is very widely used,
there are fast implementations available, uh,
It works very quickly,
ah, and works well in practice.
It finds uh, clusters,
communities that have a high modularity.
The algorithm operates in two phases,
where basically we wanna greedily assign the nodes to communities to maximize modularity.
Ah, and each uh,
iteration, each pass contains two phases.
So in phase 1,
modularity is optimized by allowing only local changes of nodes to communities,
so basically nodes get a chance to change community memberships.
And in phase 2, these identified communities are aggregated into
the super-nodes to build a new super-node network so that then another- um,
another part of community detection can be run.
So the idea is the following, the input network.
Uh, we start with an input network,
we optimize in phase 1 the modularity of it,
so we find clusters,
then we join these clusters into super-nodes to create this aggregate network.
Now we have a new network over which we can again run phase 1 to cluster it further.
In this way, we find clusters, clusters of clusters,
and so on, and we hierarchically uh, cluster the network.
Um, so now let me explain how phase 1 works.
Phase 1, we start by putting each node in the graph into a distinct community.
So each node says,
I am my own cluster,
I am my own community and each node i,
for each node i, the algorithm performs two calculations.
It computes the modularity when putting
this i into a community with some other neighbor j.
So basically we take the node i and say,
what if I put node i and put it into the community of node j?
Would that increase modularity?
And the idea is that i,
now for a given node i,
I try to put it into the commu- the same community
as every single of its neighbors is already a member of,
um, and whatever increases the modularity the most,
that's where I put i,- that's the community I put i into.
Um, and this phase 1 uh,
would kind of iterate all of the nodes until
no movement is possible that increases modularity.
So, th- the first phase stops when the local maxima in modularity is obtained.
Basically means no individual nodes can
move to a different community to improve modularity.
Um, note that the output of
the algorithm depends on the order in which we consider the nodes,
uh, in practice, it turns out that the ordering is not important.
So you fix some random ordering and that's how you process nodes.
And then for every node, you say,
what if I join you with the community with neighbor 1, neighbor 2,
neighbor 3, see which of these joinings increases the modularity the most,
and you move the node there.
If none of the moves increases modularity,
then you just don't move i to the community of node j.
So, um, what is elegant is that this modularity gain, right?
This Delta modularity where you say,
what if I take node i and move it from
the current community D to the new community C. Um,
this can be computed very efficiently.
And the way you can compute it is that you split it out into two terms.
One term is how will modularity change when I take node i and I
take it out from the cu- current community D?
And then how is the modularity going to change when I take
the same node i and put it into the new community C?
So the way you can think of picture is that, you know,
I'm right now looking- looking at node i,
let's say node i is assigned to some community D,
I pick some of its neighbors,
maybe I pick this uh, node uh,
here that belongs to the community C. So I say what happens if I
take i and kind of move it to the community C?
So first is, I have to compute the Delta modularity by taking i and moving it out of D,
and then I need to compute the Delta modularity for merging i back into the community uh,
C. And summing these two terms will give me the Delta modularity,
the increase or decrease in modularity when I move D uh, from uh,
when I move i from D to C. So let's derive
this Delta modularity when I move i into the community C. First,
we need to derive the modularity of uh,
community C as it is.
Let's call this Q of C. And the way we
derive this is we need kind of two sufficient statistic.
One is the sum Sigma inside which is the sum of the links, number of links,
or some of the link weights between the members of C,
um, and then um,
Sigma_tot will be the total number of links that all these nodes have, right?
So this is only inside the members,
and this is inside plus outside, right?
So here, I'm only summing degrees, uh, uh,
I'm only summing edge- counting edges that are inside the members of the C,
and when I compute the total,
I also account for all the edges.
So I just sum up the degrees of the- of wherever the edges go.
So now I have these two quantities, Sigma_in and Sigma_tot,
so uh, now I can rewrite modularity in terms of Sigma_in and Sigma_tot, right?
So here is modularity of a given community C,
it's this 1 over 2m we had before,
double summation over all pairs of nodes in C,
whether they are connected minus the normalized product of their degrees.
Um, if I distributed the summation inside,
I see here that this is basically now the number of edges between the uh,
members of the- of the group.
So this is Sigma_in divided by 2m,
and what I have here is a summation of the degrees of the nodes uh,
in C. Another summation of the degrees of nodes in C divided by 2m squared.
So that is uh,
Sigma_tot divided by 2m uh, squared.
Right? So uh, this is a- and- and this square
here comes because I take this 2m and distribute it inside.
So this means now that QC is large uh,
when most of the total links are within the community um,
and uh, um, very few cross to other uh, communities.
So now that we have defined, ah,
computed the modularity of C,
now we need to say how does this modularity change,
when we take this node I and put it into C. And, uh,
here we are going to use this, ah,
notion of, ah, um, uh, k_i,
in which is the number of edges node- that node i has,
to other members of C. And k_i is now the total,
uh, degree of node i, right?
So basically these two, um, uh,
these two, ah, terms, uh, are, ah,
equivalent or analogous to a Sigma in and a Sigma tot, right?
Is the total degree versus degree to oth- or the number of edges to other members,
uh, of C. And now,
ah, if I write this out, right,
so the, uh, the, uh, the,
the modularity I had before was,
um, uh, modularity of, of C,
that we have already defined plus the modularity of this,
let's say, ah, isolated community i so, ah,
it has- i doesn't have an edge with itself,
so with 0 minus, ah,
k_i times k_i with 2m,
so it's k_i squared.
Uh, and now after I have moved, uh,
in to the community,
see this node i, what do I get is the, uh,
sum of- number of edges inside Sigma in increases by k_i,
in, and the, uh,
total number of edges,
now increases bu- or total sum of the degrees now increases for the degree of node i.
So this is how I can write it, ah,
write it all, ah, all,
all, ah, all together now.
And then, right here is we said Delta modularity after I move i into community C is,
you know, after minus before.
Ah, this was- this is after, right?
I have the sum of the, uh,
the in deg- the degrees inside the community is increased by this theorem,
the total number of degrees is increased by the degree of node i,
so this is the after modularity.
This is the before modularity we have defined,
and now if I simplify this,
I basically- this is the- this is the expression,
um, the expression I get.
And what is nice, it depends on this sufficient statistic Sigma in and Sigma tot,
as well as the degree of node i,
and the number of edges that i has, ah,
to the nodes of community C. So this was the,
the term that we have just derived is this one.
Um, and then we can analogously determine,
er, derive a similar expression that says,
how does modularity change when I take node i outside community D,
sum these up together and I get a Delta modularity.
So, now that I know how to compute Delta modularity quickly, ah,
I basically iterate between,
ah, for every node I try to see,
is there an opportunity to increase modularity if I move it, uh,
to the, to a different community,
I compute this Delta modularity, um,
and I move the node into some new community, C prime, ah, based on,
uh, based on the- in a greedy way,
based on how the overall modularity, ah, is increased.
And this is essentially how the first phase of this,
ah, Louvain algorithm will operate.
So now, ah, now that I have,
ah, reached a local, ah, optimum,
I have moved, ah,
nodes to different communities until the modularity stopped increasing.
Then I moved to phase 2 which is called the restructuring, right?
So now, I wanna take these clusters communities obtained in phase 1.
And I can- I wanna contract them into a super-node,
ah, and, uh, create a new network,
a next level network,
where super-nodes are connected if there is at least one edge between the nodes,
ah, of the corresponding communities,
um, and the, ah, weights,
ah, of the edges between two super-nodes is
the sum of the edge weights across all edges between their corresponding communities.
And now I will have a super graph.
And I simply go and run,
ah, phase 1, ah, again.
All right, so the idea is,
I have my original network,
I run phase 1 to identify clusters.
Now I contract each cluster into a super-node.
I connect two clusters,
if there is at least one edge, ah, between them.
And now this will be a weighted network where the,
the edge weights are denoted here,
so this will be the total number of edges between C_1 and C_2.
And this would be the total number of edges, ah,
between the members of,
ah, C_2 ah, and so on.
And now that I have the super graph,
I simply apply my,
ah, phase 1 algorithm again.
So the way this will work is,
ah, you know, to summarize,
I have my original network,
I pick a node and, ah,
initially I put every node into its own community.
Um, and then I ask, ah, a node,
what if I move you to the same community as your member node 2 is up.
How would that change modular- modularity?
What if I move you to the community of node 3,
how would modularity change?
What if I move it to a community of node 5?
How would, ah, modularity, ah, change?
So, as I, ah, as I do this, ah,
moves, um, I then decide to move it to wherever the modularity changes the most.
And after the pas- the, the phase 1, ah,
finishes, this is the assignment of nodes to communities.
Now, I create this, ah,
phase 2 where I create a super graph,
where I contract all the nodes of the same community into a super-node,
and then this the, ah,
the edge, ah, the self loop is the,
the to- the total number of- twice the number of edges inside, ah,
the cross edges are how many edges from one cluster point to, ah, another cluster.
This gives me a super, super network,
super-node network, and now I simply apply, ah, phase, ah,
1 again, by clustering this, you know,
here I would get the following two clusters,
again I contract into super-nodes.
So here I have now basically,
ah, the two communities.
So what this means is that this original graph can be first split into two communities,
the violet and green one.
And then, you know, the,
the green one can be super,
ah, ah, ah, ah,
again split into two more communities and the violet,
into two more communities.
And then each of these four communities is denoted in this network.
So we get this, ah, hierarchical, ah, structure.
Um, and just to give you an example,
if you look, for example,
at a, ah, Belgian,
ah, mobile network, right?
Eh, Belgium is a,
is a place where,
uh, there are two, ah,
people speak two languages,
there's a strong French community,
and there's a, a strong Dutch speaking community.
And if you look at the social network,
ah, of phone calls,
you see very nicely how the- basically the,
the country splits into two, uh,
separate parts where, you know,
French speak to French,
Dutch speak to Dutch,
and there is relatively little connections, ah, between the two.
So to summarize, uh,
we have defined the notion of modularity,
which, ah, gives me the overall quality of the partitioning of a graph into communities.
Um, and now, ah, then we talked about, ah,
the Louvain algorithm for modularity maximization,
where basically it is a greedy strategy,
where we start with every node belonging into its own cluster,
and then we merge- we remove nodes between
clusters so that the overall modularity keeps increasing.
After no moves are possible anymore,
we join the clusters into super-nodes,
and again, repeat the clustering,
and this way we get this kind of nice hierarchical,
ah, community, ah, structure.
Um, Louvain works really well in practice,
scales to large networks and, ah,
people, ah, really like, ah, to use it.