## 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,​java.lang.Double>

public class ClusteringCoefficient<V,​E>
extends java.lang.Object
implements VertexScoringAlgorithm<V,​java.lang.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 Summary

Constructors
Constructor Description
ClusteringCoefficient​(Graph<V,​E> graph)
Construct a new instance
• ### Method Summary

All Methods
Modifier and Type Method Description
double getAverageClusteringCoefficient()
Computes the average clustering coefficient.
double getGlobalClusteringCoefficient()
Computes the global clustering coefficient.
java.util.Map<V,​java.lang.Double> getScores()
Get a map with the local clustering coefficients of all vertices
java.lang.Double getVertexScore​(V v)
Get a vertex's local clustering coefficient
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Constructor Detail

• #### ClusteringCoefficient

public ClusteringCoefficient​(Graph<V,​E> graph)
Construct a new instance
Parameters:
graph - the input graph
Throws:
java.lang.NullPointerException - if graph is null
• ### Method Detail

• #### 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 java.util.Map<V,​java.lang.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 java.lang.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