Louvain method

The inspiration for this method of community detection is the optimization of modularity as the algorithm progresses. Modularity is a scale value between −1 (non-modular clustering) and 1 (fully modular clustering) that measures the relative density of edges inside communities with respect to edges outside communities. Optimizing this value theoretically results in the best possible grouping of the nodes of a given network. But because going through all possible configurations of the nodes into groups is impractical, heuristic algorithms are used. In the Louvain Method of community detection, first small communities are found by optimizing modularity locally on all nodes, then each small community is grouped into one node and the first step is repeated. The method is similar to the earlier method by Clauset, Newman and Moore that connects communities whose amalgamation produces the largest increase in modularity. Although the Louvain algorithm can correctly identify the community structure when its evidence is sufficiently strong in artificial networks, in particular those sampled from the assortative stochastic block model., it is prone to finding spurious communities in random graphs and has been shown to systematically overfit empirical data . ==Algorithm description==

Modularity The value to be optimized is modularity, defined as a value in the range [-1,1] that measures the density of links inside communities compared to links between communities. \begin{align} Q_c &= \dfrac{1}{2m}\sum_{i}\sum_{j}A_{ij}\mathbf{1}\left\{c_{i}=c_{j}=c \right\} - \left(\sum_{i} \dfrac{k_i}{2m} \mathbf{1}\left\{c_{i}=c \right\} \right)^2 \\ &= \frac{\Sigma_{in}}{2m} - \left(\frac{\Sigma_{tot}}{2m}\right)^2 \end{align} where • \Sigma_{in} is the sum of edge weights between nodes within the community (each edge is considered twice); and • \Sigma_{tot} is the sum of all edge weights for nodes within the community (including edges which link to other communities). As nodes in different communities do not contribute to the modularity , it can be written as: Q = \sum_c Q_c The Louvain method algorithm The Louvain method works by repeating two phases. but other sources claim the time complexity is "essentially linear in the number of links in the graph," meaning the time complexity would instead be O(m), where is the number of edges in the graph. Unfortunately, no source has published an analysis of the Louvain method's time complexity so one is attempted here. In the pseudo-code above, the function controls the execution of the algorithm. It's clear to see that inside of , will be repeated until it is no longer possible to combine nodes into communities. This depends on two factors: how much the modularity of the graph can improve and, in the worst case, if the modularity can improve with every iteration of , it depends on how quickly will reduce the graph down to a single node. If, in each iteration of , is only able to move one node into a community, then will only be able to reduce the size of the graph by one. This would cause to repeat times. Since iterates through all nodes in a graph, this would result in a time complexity of \mathcal{O}(n^2), where is the number of nodes. It is unclear if this situation is possible, so the above result should be considered a loose bound. Blondel et al. state in their original publication that most of the run time is spent in the early iterations of the algorithm because "the number of communities decreases drastically after just a few passes." This can be understood by considering a scenario where is able to move each node so that every community has two nodes. In this case, would return a graph half the size of the original. If this continued, then the Louvain method would have a runtime of n \log_2{n}, although it is unclear if this would be the worst case, best case, average case, or none of those. Additionally, there is no guarantee the size of the graph would be reduced by the same factor with each iteration, and so no single logarithm function can perfectly describe the time complexity. ==Previous uses==

• Twitter social Network (2.4 Million nodes, 38 million links) by Josep Pujol, Vijay Erramilli, and Pablo Rodriguez: The authors explore the problem of partitioning Online Social Networks onto different machines. • Mobile phone Network (4 Million nodes, 100 Million links) by Derek Greene, Donal Doyle, and Padraig Cunningham: Community-tracking strategies for identifying dynamic communities of different dynamic social networks. • Detecting species in network-based dynamical model. ==Disadvantages==

Louvain produces only non-overlapping communities, which means that each node can belong to at most one community. This is highly unrealistic in many real-world applications. For example, in social networks, most people belong to multiple communities: their family, their friends, their co-workers, old school buddies, etc. In biological networks, most genes or proteins belong to more than one pathway or complex. Furthermore, Louvain has been shown to sometimes produce arbitrarily badly connected communities, and has been effectively superseded (at least in the non-overlapping case) by the Leiden algorithm. A worst case example of an arbitrarily badly connected community is a internally disconnected community. An internally disconnected community arises through the Louvain algorithm when a node that had been acting as a "bridge" between two groups of nodes in its community is moved to a new community, leaving the old one disconnected. The remaining nodes in the old community may also be relocated, but if their connection to the community is strong enough despite the removal of the "bridge" node, they will instead remain in place. For an example of this, see the image to the right; note how the removal of the bridge node, node 0, caused the red community to be split into two disjoint subgroups. While this is the worst-case scenario, there are other, more subtle problems with the Louvain algorithm that can also lead to arbitrarily badly connected communities, such as the formation of communities using nodes that are only weakly connected. Another common issue with the Louvain algorithm is the resolution limit of modularity - that is, multiple small communities being grouped together into a larger community. This causes the smaller communities to be hidden; for an example of this, see the visual depiction of the resolution limit to the right. Note how, when the green community is absorbed into the blue community to increase the graph's modularity, the smaller group of nodes that it represented is lost. There is no longer a way to differentiate those nodes from the nodes that were already in the blue community. Conversely, the nodes that were already in the blue community no longer appear distinct from those that were in the green community; in other words, whatever difference caused them to initially be placed in separate communities has been obscured. Both the resolution limit of modularity and the arbitrarily badly connected community problem are further exasperated by each iteration of the algorithm. Ultimately, the only thing the Louvain algorithm guarantees is that the resulting communities cannot be merged further; in other words, they're well-separated. To avoid the problems that arise from arbitrarily badly connected communities and the resolution limit of modularity, it is recommended to use the Leiden algorithm instead, as its refinement phase and other various adjustments have corrected these issues. ==Comparison to other methods of non-overlapping community detection==

When comparing modularity optimization methods, the two measures of importance are the speed and the resulting modularity value. A higher speed is better as it shows a method is more efficient than others and a higher modularity value is desirable as it points to having better-defined communities. The compared methods are, the algorithm of Clauset, Newman, and Moore, and Wakita and Tsurumi. -/- in the table refers to a method that took over 24hrs to run. This table (from) shows that the Louvain method outperforms many similar modularity optimization methods in both the modularity and the time categories. ==See also==