Module org.jgrapht.core
Package org.jgrapht.alg.clustering

Class UndirectedModularityMeasurer<V,E>

java.lang.Object
org.jgrapht.alg.clustering.UndirectedModularityMeasurer<V,E>
Type Parameters:
V - the vertex type
E - the edge type
public class UndirectedModularityMeasurer<V,E> extends Object
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.

Author:
Dimitrios Michail

  • Constructor Details

    • UndirectedModularityMeasurer

      public UndirectedModularityMeasurer(Graph<V,E> graph)
      Construct a new measurer
      Parameters:
      graph - the input graph

  • Method Details

    • modularity

      public double modularity(List<Set<V>> partitions)
      Compute the modularity of a vertex partition.
      Parameters:
      partitions - the partitions
      Returns:
      the modularity