The Louvain method for community detection is a greedy optimization method intended to extract non-overlapping communities from large networks created by Blondel et al. from the University of Louvain (the source of this method's name).
Modularity optimization The inspiration for this method of community detection is the optimization of modularity as the algorithm progresses. Modularity is a scale value between −1/2 (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 / 2 , 1 ] {\displaystyle [-1/2,1]} that measures the density of links inside communities compared to links between communities. For a weighted graph, modularity is defined as:
Q = 1 2 m ∑ i = 1 N ∑ j = 1 N [ A i j − k i k j 2 m ] δ ( c i , c j ) , {\displaystyle Q={\frac {1}{2m}}\sum _{i=1}^{N}\sum _{j=1}^{N}{\bigg [}A_{ij}-{\frac {k_{i}k_{j}}{2m}}{\bigg ]}\delta (c_{i},c_{j}),}
where:
A i j {\displaystyle A_{ij}} represents the edge weight between nodes i and j; see Adjacency matrix; k i {\displaystyle k_{i}} and k j {\displaystyle k_{j}} are the sum of the weights of the edges attached to nodes i and j, respectively; m is the sum of all of the edge weights in the graph; N is the total number of nodes in the graph; c i {\displaystyle c_{i}} and c j {\displaystyle c_{j}} are the communities to which the nodes i and j belong; and
δ {\displaystyle \delta } is Kronecker delta function:
δ ( c i , c j ) = { 1 if c i and c j are the same cluster 0 otherwise {\displaystyle {\begin{aligned}\delta (c_{i},c_{j})&={\begin{cases}1&{\text{if }}c_{i}{\text{ and }}c_{j}{\text{ are the same cluster}}\\0&{\text{otherwise}}\end{cases}}\end{aligned}}}
Based on the above equation, the modularity of a community c can be calculated as:
… excerpt ends here. Continue reading the full article.
