Module org.jgrapht.core
Package org.jgrapht.alg.scoring

Class ClusteringCoefficient<V,E>

java.lang.Object
org.jgrapht.alg.scoring.ClusteringCoefficient<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
VertexScoringAlgorithm<V,Double>
public class ClusteringCoefficient<V,E> extends Object implements VertexScoringAlgorithm<V,Double>
Clustering coefficient. This implementation computes the global, the local and the average clustering coefficient in an undirected or a directed network.

The local clustering coefficient of a vertex in a graph quantifies how close its neighbors are to being a clique. For a vertex $v$ it counts how many of its direct neighbors are connected by an edge over the total number of neighbor pairs. In the case of undirected graphs the total number of possible neighbor pairs is only half compared to directed graphs.

The local clustering coefficient of a graph was introduced in D. J. Watts and Steven Strogatz (June 1998). "Collective dynamics of 'small-world' networks". Nature. 393 (6684): 440–442. doi:10.1038/30918. It is simply the average of the local clustering coefficients of all the vertices of the graph.

The global clustering coefficient of a graph is based on triplets of nodes. A triplet is three graph nodes which are connected either by two edges or by three edges. A triplet which is connected by two edges, is called an open triplet. A triplet which is connected with three edges is called a closed triplet. The global clustering coefficient is defined as the number of closed triplets over the total number of triplets (open and closed). It was introduced in R. D. Luce and A. D. Perry (1949). "A method of matrix analysis of group structure". Psychometrika. 14 (1): 95–116. doi:10.1007/BF02289146.

The running time is $O(|V| + \Delta(G)^2)$ where $|V|$ is the number of vertices and $\Delta(G)$ is the maximum degree of a vertex. The space complexity is $O(|V|)$.

Author:
Alexandru Valeanu

  • Constructor Details

    • ClusteringCoefficient

      public ClusteringCoefficient(Graph<V,E> graph)
      Construct a new instance
      Parameters:
      graph - the input graph
      Throws:
      NullPointerException - if graph is null

  • Method Details

    • getGlobalClusteringCoefficient

      public double getGlobalClusteringCoefficient()
      Computes the global clustering coefficient. The global clustering coefficient $C$ is defined as $C = 3 \times number\_of\_triangles / number\_of\_triplets$.

      A triplet is three nodes that are connected by either two (open triplet) or three (closed triplet) undirected ties.

      Returns:
      the global clustering coefficient

    • getAverageClusteringCoefficient

      public double getAverageClusteringCoefficient()
      Computes the average clustering coefficient. The average clustering coefficient $\={C}$ is defined as $\={C} = \frac{\sum_{i=1}^{n} C_i}{n}$ where $n$ is the number of vertices. Note: the average is $0$ if the graph is empty
      Returns:
      the average clustering coefficient

    • getScores

      public Map<V,Double> getScores()
      Get a map with the local clustering coefficients of all vertices
      Specified by:
      getScores in interface VertexScoringAlgorithm<V,E>
      Returns:
      a map with all local clustering coefficients

    • getVertexScore

      public Double getVertexScore(V v)
      Get a vertex's local clustering coefficient
      Specified by:
      getVertexScore in interface VertexScoringAlgorithm<V,E>
      Parameters:
      v - the vertex
      Returns:
      the local clustering coefficient