Module org.jgrapht.core
Package 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. 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 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,​E>
        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,​E>
        Parameters:
        v - the vertex
        Returns:
        the local clustering coefficient