Talk:Modularity (networks)

The value of the modularity lies in the range [−1,1]. It would be great if some more explanations can be provided. Like when the modularity equals 1 or -1.

From the article: all rows and columns of the modularity matrix sum to zero, which means that the modularity of an undivided network is also always zero. How come if you have an undirected graph with two vertices and an edge between them, the modularity is 0.25? --JulienBourdon (talk) 09:51, 4 August 2011 (UTC)

I found this article quite hard to understand, in part because the prose does not fit the headings and because it was a bit too mathsy in style. I didn't edit the resolution section (I don't really get it), but it really needs integrating into the main article and the repeated definition of modularity needs removing. I made some changes, but experts with subject specific knowledge might do a lot better than me - can someone explain to me why the formula in this Wiki article differs from that of Newman and Girvan (2003) http://pre.aps.org/abstract/PRE/v69/i2/e026113? A refernce for the formula that's already in there is really needed. And where do the differences in calculations of modularity arise from and are these differences really important??? Emble64 (talk) 17:08, 21 September 2011 (UTC)

In response to the earlier question: there are no graphs that have modularity of less than -1/2, especially not -1. I just fixed that inside the article. The -1 is obtained from a really "bad" lower bound, it is easy to calculate a better one as I just found out in my university's network anlysis exercise. ;) --134.61.64.96 (talk) 15:34, 15 December 2011 (UTC)

The caption of Fig. 2 says that the modularity of the example network is 0.4985. I am quite sure that the actual value is 0.489583(3). Can someone double-check this value? — Preceding unsigned comment added by 82.242.114.236 (talk) 09:13, 1 May 2012 (UTC)

There is a fee variable j in (4), is it correct? This should represent the difference between the number of expected edges and the number of actual edges in a cluster, as simple as it.

I've double checked this, and it amounts to

$Q={\frac {1}{2\cdot 12}}\left[2\left(2\cdot 3-{\frac {7^{2}}{2\cdot 12}}\right)+\left(2\cdot 4-{\frac {10^{2}}{2\cdot 12}}\right)\right]=0.489583333$

I might add that indeed the introduction is quite strange and can be improved upon. The usage of the $s_{i}$ variables limits the first formulation to only 2 communities, while it is completely unnecessary to do so. In fact, this description better fits the matrix description, since this formulation is useful when doing spectral decomposition. Why not simply use the formulation

$Q={\frac {1}{2m}}\sum _{ij}\left(A_{ij}-{\frac {k_{i}k_{j}}{2m}}\right)\delta (\sigma _{i},\sigma _{j})$

where $\sigma _{i}$ denotes the community of node $i$ and $\delta$ the dirac delta function, such that $\delta (\sigma _{i},\sigma _{j})=1$ if $\sigma _{i}=\sigma _{j}$ and zero otherwise. In other words, the sum runs over only those links which have both ends in the same community. Gathering terms per community then yields

$Q={\frac {1}{2m}}\sum _{s}e_{s}-{\frac {K_{s}^{2}}{2m}}$

where

$e_{s}=\sum _{ij:\sigma _{i},\sigma _{j}=s}A_{ij}$

(twice) the number of links within community $s$, and

$K_{s}=\sum _{i:\sigma _{i}=s}k_{i}$

the sum of the degrees within community $s$. This can then be explained as being the number of links within community $s$ minus the number of expected links within the community. In fact, one could also consider the more general formulation (based on Reichardt & Bornholdts formulation, see http://pre.aps.org/abstract/PRE/v74/i1/e016110)

$Q={\frac {1}{2m}}\sum _{ij}\left(A_{ij}-p_{ij}\right)\delta (\sigma _{i},\sigma _{j})$

where $p_{ij}$ represents the number of expected links between $i$ and $j$. 62.163.86.225 (talk) 09:20, 4 May 2012 (UTC)

Software Section

Hi, I would like to create a list of software that solves the graph clustering problem for modularity. A preliminary list of things that I would like to include are - https://github.com/vtraag/leidenalg (improve Louvain method, manages to produce less disconnected clusters) - https://sites.google.com/site/findcommunities/ (orginal implementation of Louvain method) - https://github.com/VieClus/VieClus (scalable memetic algorithm for the problem) - ...

Please let me know if there is anything that goes against such a list. — Preceding unsigned comment added by 91.112.12.190 (talk) 11:48, 19 November 2020 (UTC)

There is a free variable $j$ in formula (4) , probably a typo. This $e_{i,j}$ should be rather the actual number of edges within the cluster $i$.