The Louvain method for community detection aims to optimize modularity and hence detect communities in the given graph. In case of a weighted graph would it be valid to assume that an edge with a higher weight would be prioritized to be part of a community as against an edge with a lower weight while optimizing modularity ?
Asked
Active
Viewed 1,341 times
2
-
I would say vice versa. Weight - should be thought as length of path, so high weight - nodes are far from each other - should be prioritized as separate communities members. Hope I did not forget something ... – Alexander Chervov Oct 20 '20 at 22:33
1 Answers
2
Yes, weights are interpreted as a strength of connection in the context of modularity. This is perhaps easiest to see using the interpretation of unweighted modularity as
The fraction of edges within communities minus the expected such fraction in a random graph with the same degree sequence.
Switching the adjacency matrix to the weighted adjacency matrix to get the weighted modularity just changes this to
The fraction of total weights within communities minus the expected such fraction in a random weighted graph with the same total weights at each vertex.
That said, you do have to be careful. There are community detection methods that do treat weights as distances:
SO: meaning of weights in community detection algorithms
It may be worth running a simple example when first using a specific algorithm implementation; e.g., with $G=C_4$, weight one perfect matching very much higher than the other, the communities should end up being two $K_2$s, and you want to know whether they contain the high- or low- weight edges.
Ben Reiniger
- 11,094
- 3
- 16
- 53