Find the best partition of a graph using the Louvain Community Detection
Algorithm.
Louvain Community Detection Algorithm is a simple method to extract the community
structure of a network. This is a heuristic method based on modularity optimization. [1]_
The algorithm works in 2 steps. On the first step it assigns every node to be
in its own community and then for each node it tries to find the maximum positive
modularity gain by moving each node to all of its neighbor communities. If no positive
gain is achieved the node remains in its original community.
The modularity gain obtained by moving an isolated node $i$ into a community $C$ can
easily be calculated by the following formula (combining [1]_[2] and some algebra):
where $m$ is the size of the graph, $k_{i,in}$ is the sum of the weights of the links
from $i$ to nodes in $C$, $k_i$ is the sum of the weights of the links incident to node $i$,
$Sigma_{tot}$ is the sum of the weights of the links incident to nodes in $C$ and $gamma$
is the resolution parameter.
For the directed case the modularity gain can be computed using this formula according to [3]
where $k_i^{out}$, $k_i^{in}$ are the outer and inner weighted degrees of node $i$ and
$Sigma_{tot}^{in}$, $Sigma_{tot}^{out}$ are the sum of in-going and out-going links incident
to nodes in $C$.
The first phase continues until no individual move can improve the modularity.
The second phase consists in building a new network whose nodes are now the communities
found in the first phase. To do so, the weights of the links between the new nodes are given by
the sum of the weight of the links between nodes in the corresponding two communities. Once this
phase is complete it is possible to reapply the first phase creating bigger communities with
increased modularity.
The above two phases are executed until no modularity gain is achieved (or is less than
the threshold).
Parameters:
threshold
G (easygraph)
weight (string or None, optional (default="weight")) – The name of an edge attribute that holds the numerical value
used as a weight. If None then each edge has weight 1.
Returns:
A list of sets (partition of G). Each set represents one community and contains
all the nodes that constitute it.
Return type:
list
Notes
The order in which the nodes are considered can affect the final output. In the algorithm
the ordering happens using a random shuffle.
Yields partitions for each level of the Louvain Community Detection Algorithm
Louvain Community Detection Algorithm is a simple method to extract the community
structure of a network. This is a heuristic method based on modularity optimization. [1]_
The partitions at each level (step of the algorithm) form a dendogram of communities.
A dendrogram is a diagram representing a tree and each level represents
a partition of the G graph. The top level contains the smallest communities
and as you traverse to the bottom of the tree the communities get bigger
and the overall modularity increases making the partition better.
Each level is generated by executing the two phases of the Louvain Community
Detection Algorithm.
Parameters:
threshold
G (easygraph)
weight (string or None, optional (default="weight")) – The name of an edge attribute that holds the numerical value
used as a weight. If None then each edge has weight 1.
Yields:
list – A list of sets (partition of G). Each set represents one community and contains
all the nodes that constitute it.