java.lang.Object
org.jgrapht.alg.clustering.UndirectedModularityMeasurer<V,E>
- Type Parameters:
V
- the vertex typeE
- the edge type
A modularity measurer.
This is a utility class which computes the modularity function. It takes as input a list of vertex classes $C$ and a graph $G$ and calculates: $Q = \frac{1}{2m} \sum_{ij} \left( A_{ij} - \frac{k_i k_j}{2m} \right) \delta(C_i, C_j)$. Here $m$ is the total number of edges and $k_i$ is the degree of vertex $i$. $A_{ij}$ is either $1$ or $0$ depending on whether edge $(i,j)$ belongs to the graph and $\delta(C_i, C_j)$ is 1 if vertices $i$ and $j$ belong to the same class, $0$ otherwise.
-
Field Summary
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptiondouble
modularity
(List<Set<V>> partitions) Compute the modularity of a vertex partition.private void
precomputeDegrees
(Graph<V, E> graph) Pre-compute vertex (weighted) degrees.
-
Field Details
-
INVALID_PARTITION_OF_VERTICES
- See Also:
-
graph
-
m
private double m -
degrees
-
-
Constructor Details
-
UndirectedModularityMeasurer
Construct a new measurer- Parameters:
graph
- the input graph
-
-
Method Details
-
modularity
Compute the modularity of a vertex partition.- Parameters:
partitions
- the partitions- Returns:
- the modularity
-
precomputeDegrees
Pre-compute vertex (weighted) degrees.- Parameters:
graph
- the input graph
-