NetSci 06-2 Modularity and the Louvain Method

Given a partition of a network into potential communities, we can use modularity to measure corresponding community structure. This video explains the math behind modularity and gives a high-level explanation of how the popular Louvain approximation algorithm tries to find a partition with a high modularity score.

[@charlottepan6821]

Nice explanation about the calculation of modularity! Thanks!

[@aj_csc3595]

Please make a video on Leiden algorithm

[@cyberwalker]

Vary helpful, thank you a lot!

[@yinghaohu8784]

very clear

[@saintlee1660]

Thanks for the explanations! A small issue here is that Wasserman and Faust didn't introduce the concept of community in their book. The quote you have from them is their definition of "cohesive subgroups".

[@jinyuzhu1078]

Very helpful!

[@中二的水之立方]

Thanks for the explanation! But I still cannot connect resolution with random walk probability, I cannot see the time elapse in the formula QAQ I am not good at math....

[@kaleabwoldemariam4288]

Online communities could benefit from this pivot. Thanks. The equation looks quite like neural network optimization algorithms?

[@sudeshnadutta5702]

Can you please explain what exactly happens in phase 1? Do we go through all nodes once and find communities and then move to phase 2 where we again apply phase 1? Like how many iterations do we do in phase 1 for each node?

[@andrewbeveridge7476]

Thanks for this great question. Here is how Phase 1 works in the original paper. Every node starts in its own community. We then randomly order the nodes and then cycle through them. When processing node x, we ask: what happens if we move x into the community of each of its neighbors y? We update the communities by picking the option that maximizes the modularity score (including keeping x in its current community). We repeat this process for every vertex until no vertex wants to move. The actual number of rounds isn't known up front, and can depend on the ordering of the nodes. Likewise, the final partition into communities can also depend on the ordering you use. But when there is a healthy community structure, the end results are pretty similar. Again: this is an approximation algorithm that "usually" performs well (quickly, good result) for such networks.

[@joaquincarrascosa91]

Very helpful!
You mention researchers consider >0,3 a significant. Is there a simple way to compare scores between two networks ? A higher score would mean the network is more structured in communities?

[@andrewbeveridge7476]

Yes, higher scores correspond to "more community structure." As for comparing two networks, here are a few thoughts. First, you would really need for them to be of comparable sizes in order to consider comparing modularity scores. Second, you can't use modularity to resolve "close calls." In other words, the scores 0.30 and 0.31 are pretty much the same (and the Louvain method is an approximation algorithm). Third, there are also some subtleties involved. The original Louvain method has trouble detecting "small" communities (whose size is smaller than the square root of the number of nodes). If you are interested in this topic, then a good place to start is this paper that evaluates the output of various community detection methods. hal.archives-ouvertes.fr/hal-01976587/document

[@joaquincarrascosa91]

@@andrewbeveridge7476 Thanks for responding, I ll read the paper you recomended.
Regarding comparing between networks of different size this papers proposes a relative measure www.pnas.org/content/114/16/4165

[@PhamNgocSon1610]

I have a liitle bit confuse about the 2m as another adges because in the formula of Q, m is total egdes of Network?

[@proximo08]

When you explain modularity, you say there is 2m edges, but there is only m edges. The 2 is here because there are 2 directions for each edge

[@alwaaffa]

You can help me with a master’s thesis for my software part (coding) in Python?