 java.lang.Object

 org.jgrapht.alg.scoring.ClusteringCoefficient<V,E>

 Type Parameters:
V
 the graph vertex typeE
 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 '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
Constructors Constructor Description ClusteringCoefficient(Graph<V,E> graph)
Construct a new instance

Method Summary
All Methods Instance Methods Concrete 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 verticesjava.lang.Double
getVertexScore(V v)
Get a vertex's local clustering coefficient



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 interfaceVertexScoringAlgorithm<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 interfaceVertexScoringAlgorithm<V,E>
 Parameters:
v
 the vertex Returns:
 the local clustering coefficient

