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,​java.lang.Double>
    public class ClusteringCoefficient<V,​E>
extends java.lang.Object
implements VertexScoringAlgorithm<V,​java.lang.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 Detail

      • ClusteringCoefficient

        public ClusteringCoefficient​(Graph<V,​E> graph)
        Construct a new instance
        Parameters:
        graph - the input graph
        Throws:
        java.lang.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 java.util.Map<V,​java.lang.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 java.lang.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