The documentation of ModularityVertexPartition defines a modularity formula that I cannot find to be related to any Girman-Newman paper, neither the one that is cited by the documentation.
https://louvain-igraph.readthedocs.io/en/latest/reference.html#modularityvertexpartition
I ask to fix the citation and better specify the origin of such a formula.
This is the standard definition of modularity, which was indeed first introduced in the paper cited in the louvain-igraph documentation. The citation is correct. Have a look at Section IV and equation (5) in particular. Be sure to read the explanation as well, which should make it clear why equation (5) is mathematically equivalent to the formula you find in the louvain-igraph docs. The latter form is more intuitive, therefore you will see it much more commonly.
Essentially, the modularity of a partitioning is the fraction of edges within (not across) partitions minus the expected fraction of edges contained within partitions in a random graph with the same degrees. For a nice explanation of modularity I recommend section III.C of Fortunato’s review on community detection: [0906.0612] Community detection in graphs
I agree with you. For these reasons, the reference for https://louvain-igraph.readthedocs.io/en/latest/reference.html#modularityvertexpartition is wrong. Moreover, it is not the Gorman-Newman modularity, because there not exists any Girman-Newman modularity. It is the Louvain modularity.
So, please, change the documentation by removing the citation and by not naming it Girman-Newman.
Please note that this is the forum for igraph, not for the louvain-igraph package; perhaps it would be better to open an issue at Issues · vtraag/louvain-igraph · GitHub the next time. (Note: I am the author of that package.) I understand that the appearance of igraph in the name of the package might suggest otherwise, but this is not the case.
I do not really understand this. Newman & Girvan (20024) were the ones to introduce this definition. Why do you say there does not exist any Newman-Girvan modularity?
It is not: Blondel et. al (2008) did not formulate modularity, Newman & Girvan (2004) did.
I’m afraid that I disagree for the reasons outlined above. The definition was introduced by Newman & Girvan, and should therefore be cited.
Perhaps you refer to the fact that the exact formulation of modularity is not identical, even though they are mathematically equivalent? I do not consider these differences in notations and/or formulations to be relevant here. The reformulations are quite straightforward, and in particular the sum over communities that is included in the documentation is very close to Eq. (5) in Newman & Girvan (2005).
I just want to add another voice confirming that szhorvat and vtraag are correct, and a little more background.
Modularity is a quality of partition metric, which was defined by Newman (apparently in collaboration with Girvan). See section 7.13 of Newman’s (2010) book “Networks: An Introduction”, or section 7.7 of the 2018 2nd edition of this book, titled simply “Networks”, for detailed development and relationship to assortativity and Pearson’s r. Fortunato’s review is also a good source.
Finding the partition that yields maximum modularity is NP-hard, so the numerous algorithms proposed are almost all approximation algorithms. Blondel et al.'s Louvain Method is one of these, which performs well but has been improved with the Leiden method to eliminate some rare degenerate outcomes.
Gephi calls the Louvain method “Modularity”, resulting in much confusion (people think it is an algorithm, but it is a metric).
The definition of modularity has been introduced by Girman and Newman, but it is not the type of modularity that you are solving with that function.
The type of modualrity that you are solving, according the to formula in the documentation, is given in Blondel et al 2008.
The algorithms are different. Girman-Newman algorithm removes edges according to the edge betweenness score…that’s it. In contrast, the resolution of the formula that you give in the documentation is provided via a different algorithm in which nodes of the network are moved from one community to another in order to find the clustering that maximizes the value of the formula.
So, please change the documentation. Unfortunately, many people rely on the documentation of your package, which in this case is giving the wrong information. As a professor of computer science, I ask you to correct your documentation. Thank you
Vincenzo, you are confusing community detection algorithms with a quality metric for vertex partitionings. The discussion was on the latter. Please read the responses above, as well as the louvain-igraph documentation, carefully, before posting further.
I already answered this in my first comment … Equation (5), and be sure to read the preceding text within the paper.
In case this is where the confusion is coming from: Note that modularity does not characterize a network. It characterizes a specific partitioning of the vertices of a network. Different community detection methods produce different partitionings, which will have different modularity values.
It is eq 5 of Newman 2005 (https://www.pnas.org/doi/10.1073/pnas.0601602103) but the documentation is citing Girman-Newman 2004 ( Phys. Rev. E 69, 026113 (2004) - Finding and evaluating community structure in networks ).
