Part of a series on
Network science
Theory
Graph Complex network Contagion Small-world Scale-free Community structure Percolation Evolution Controllability Graph drawing Social capital Link analysis Optimization Reciprocity Closure Homophily Transitivity Preferential attachment Balance theory Network effect Social influence
Network types
Informational (computing) Telecommunication Transport Social Scientific collaboration Biological Artificial neural Interdependent Semantic Spatial Dependency Flow on-Chip
Graphs
Features Clique Component Cut Cycle Data structure Edge Loop Neighborhood Path Vertex Adjacency list / matrix Incidence list / matrix Types Bipartite Complete Directed Hyper Labeled Multi Random Weighted
Metrics Algorithms
Centrality Degree Motif Clustering Degree distribution Assortativity Distance Modularity Efficiency
Models
Topology Random graph Erdős–Rényi Barabási–Albert Bianconi–Barabási Fitness model Watts–Strogatz Exponential random (ERGM) Random geometric (RGG) Hyperbolic (HGN) Hierarchical Stochastic block Blockmodeling Maximum entropy Soft configuration LFR Benchmark Dynamics Boolean network agent based Epidemic/SIR
Lists Categories
Topics Software Network scientists Category:Network theory Category:Graph theory
v t e

The Louvain method for community detection is a method to extract non-overlapping communities from large networks created by Blondel et al.^[1] from the University of Louvain (the source of this method's name). The method is a greedy optimization method that appears to run in time ${\displaystyle O(n\cdot \log n)}$ where ${\displaystyle n}$ is the number of nodes in the network.^[2]

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 −0.5 (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 iterations 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^[3] that connects communities whose amalgamation produces the largest increase in modularity. The Louvain algorithm was shown to correctly identify the community structure when it exists, in particular in the stochastic block model.^[4]

Algorithm

The value to be optimized is modularity, defined as a value in the range ${\displaystyle }$ that measures the density of links inside communities compared to links between communities.^[1] For a weighted graph, modularity is defined as:

${\displaystyle Q={\frac {1}{2m}}\sum _{i=1}^{N}\sum _{j=1}^{N}{\bigg }\delta (c_{i},c_{j}),}$

where:

• ${\displaystyle A_{ij}}$ represents the edge weight between nodes ${\displaystyle i}$ and ${\displaystyle j}$; see Adjacency matrix;
• ${\displaystyle k_{i}}$ and ${\displaystyle k_{j}}$ are the sum of the weights of the edges attached to nodes ${\displaystyle i}$ and ${\displaystyle j}$, respectively;
• ${\displaystyle m}$ is the sum of all of the edge weights in the graph;
• ${\displaystyle N}$ is the total number of nodes in the graph;
• ${\displaystyle c_{i}}$ and ${\displaystyle c_{j}}$ are the communities to which the nodes ${\displaystyle i}$ and ${\displaystyle j}$ belong; and
• ${\displaystyle \delta }$ is Kronecker delta function:

${\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 ${\displaystyle c}$ can be calculated as:^[5]

${\displaystyle {\begin{aligned}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{aligned}}}$

where

• ${\displaystyle \Sigma _{in}}$ is the sum of edge weights between nodes within the community ${\displaystyle c}$ (each edge is considered twice); and
• ${\displaystyle \Sigma _{tot}}$ is the sum of all edge weights for nodes within the community (including edges which link to other communities).

In order to maximize modularity efficiently, the Louvain Method has two phases that are repeated iteratively.

Phase 1:

1. First, each node in the network is assigned to its own community.

2. Next, for each node ${\displaystyle i}$, the change in modularity is calculated for removing ${\displaystyle i}$ from its own community and moving it into the community of each neighbor ${\displaystyle j}$ of ${\displaystyle i}$. This value is computed in two steps:

(a) Compute the change in modularity ${\displaystyle \Delta Q}$ for removing node ${\displaystyle i}$ from its original community.

(b) Compute the change in modularity ${\displaystyle \Delta Q}$ for inserting an isolated node ${\displaystyle i}$ (i.e. node ${\displaystyle i}$Zdroj:https://en.wikipedia.org?pojem=Louvain_modularity
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.