Clustering algorithms.
The attribute labels_ assigns a label (cluster index) to each node of the graph.
The Louvain algorithm aims at maximizing the modularity. Several variants of modularity are available:
| Modularity | Formula |
|---|---|
Newman ('newman') |
Q = \frac{1}{w} \sum_{i,j}\left(A_{ij} - \gamma \frac{d_id_j}{w}\right)\delta_{c_i,c_j} |
Dugué ('dugue') |
Q = \frac{1}{w} \sum_{i,j}\left(A_{ij} - \gamma \frac{d^+_id^-_j}{w}\right)\delta_{c_i,c_j} |
Potts ('potts') |
Q = \sum_{i,j}\left(\frac{A_{ij}}{w} - \gamma \frac{1}{n^2}\right)\delta_{c_i,c_j} |
- where
- A is the adjacency matrix,
- c_i is the cluster of node i,
- d_i is the degree of node i,
- d^+_i, d^-_i are the out-degree, in-degree of node i (for directed graphs),
- w = 1^TA1 is the sum of degrees,
- \delta is the Kronecker symbol,
- \gamma \ge 0 is the resolution parameter.
Observe that for undirected graphs, the Newman and Dugué variants are equivalent.
For bipartite graphs, the considered adjacency matrix A depends on the modularity. For the Newman and Potts variants, the graph is considered as undirected so that:
A = \begin{pmatrix} 0 & B\\B^T & 0\end{pmatrix}
For the Dugué variant, the graph is considered as directed so that:
A = \begin{pmatrix} 0 & B\\0 & 0\end{pmatrix}
This is the default option and corresponds to Barber's modularity (see reference below).
When the graph is weighted, the degree of a node is replaced by its weight (sum of edge weights).
.. autoclass:: sknetwork.clustering.Louvain
.. autoclass:: sknetwork.clustering.Leiden
.. autoclass:: sknetwork.clustering.KCenters
.. autoclass:: sknetwork.clustering.PropagationClustering
.. autofunction:: sknetwork.clustering.reindex_labels
.. autofunction:: sknetwork.clustering.aggregate_graph
.. autofunction:: sknetwork.clustering.get_modularity