org.jgrapht.alg.scoring

Class 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.

Computes the local clustering coefficient of each vertex of a graph. The local clustering coefficient of a node $v$ is given by the expression: $g(v)= \sum_{s \neq v \neq t}\frac{\sigma_{st}(v)}{\sigma_{st}}$ where $\sigma_{st}$ is the total number of shortest paths from node $s$ to node $t$ and $\sigma_{st}(v)$ is the number of those paths that pass through $v$. For more details see wikipedia.

This implementation computes both the global, the local and the average clustering coefficient in an undirected or a directed network.

Global clustering coefficient 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

Local clustering coefficient 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

This implementation also computes the global clustering coefficient as well as the average clustering coefficient.

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 and Description
ClusteringCoefficient(Graph<V,E> graph)
Construct a new instance
• Method Summary

All Methods
Modifier and Type Method and Description
double getAverageClusteringCoefficient()
Computes the average clustering coefficient.
double getGlobalClusteringCoefficient()
Computes the global clustering coefficient.
Map<V,Double> getScores()
Get a map with the local clustering coefficients of all vertices
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:
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 Map<V,Double> getScores()
Get a map with the local clustering coefficients of all vertices
Specified by:
getScores in interface VertexScoringAlgorithm<V,Double>
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,Double>
Parameters:
v - the vertex
Returns:
the local clustering coefficient