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.

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

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