 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
VertexScoringAlgorithm<V,
Double>
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 'smallworld' 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

Method Summary
Modifier and TypeMethodDescriptiondouble
Computes the average clustering coefficient.double
Computes the global clustering coefficient.Get a map with the local clustering coefficients of all verticesgetVertexScore
(V v) Get a vertex's local clustering coefficient

Constructor Details

ClusteringCoefficient
Construct a new instance Parameters:
graph
 the input graph Throws:
NullPointerException
 ifgraph
isnull


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
Get a map with the local clustering coefficients of all vertices Specified by:
getScores
in interfaceVertexScoringAlgorithm<V,
E>  Returns:
 a map with all local clustering coefficients

getVertexScore
Get a vertex's local clustering coefficient Specified by:
getVertexScore
in interfaceVertexScoringAlgorithm<V,
E>  Parameters:
v
 the vertex Returns:
 the local clustering coefficient
