Package org.jgrapht.alg.scoring

Class ClosenessCentrality<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    VertexScoringAlgorithm<V,​java.lang.Double>
    Direct Known Subclasses:
    HarmonicCentrality
    public class ClosenessCentrality<V,​E>
extends java.lang.Object
implements VertexScoringAlgorithm<V,​java.lang.Double>
    Closeness centrality.

    Computes the closeness centrality of each vertex of a graph. The closeness of a vertex $x$ is defined as the reciprocal of the farness, that is $H(x)= 1 / \sum_{y \neq x} d(x,y)$, where $d(x,y)$ is the shortest path distance from $x$ to $y$. When normalization is used, the score is multiplied by $n-1$ where $n$ is the total number of vertices in the graph. For more details see wikipedia and

    • Alex Bavelas. Communication patterns in task-oriented groups. J. Acoust. Soc. Am, 22(6):725–730, 1950.

    This implementation computes by default the closeness centrality using outgoing paths and normalizes the scores. This behavior can be adjusted by the constructor arguments.

    When the graph is disconnected, the closeness centrality score equals $0$ for all vertices. In the case of weakly connected digraphs, the closeness centrality of several vertices might be 0. See HarmonicCentrality for a different approach in case of disconnected graphs.

    Shortest paths are computed either by using Dijkstra's algorithm or Floyd-Warshall depending on whether the graph has edges with negative edge weights. Thus, the running time is either $O(n (m +n \log n))$ or $O(n^3)$ respectively, where $n$ is the number of vertices and $m$ the number of edges of the graph.

    Author:
    Dimitrios Michail

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected Graph<V,​E> graph
      Underlying graph
      protected boolean incoming
      Whether to use incoming or outgoing paths
      protected boolean normalize
      Whether to normalize scores
      protected java.util.Map<V,​java.lang.Double> scores
      The actual scores

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      protected void compute()
      Compute the centrality index
      java.util.Map<V,​java.lang.Double> getScores()
      Get a map with the scores of all vertices
      protected ShortestPathAlgorithm<V,​E> getShortestPathAlgorithm()
      Get the shortest path algorithm for the paths computation.
      java.lang.Double getVertexScore​(V v)
      Get a vertex score

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Field Detail

      • graph

        protected final Graph<V,​E> graph
        Underlying graph

      • incoming

        protected final boolean incoming
        Whether to use incoming or outgoing paths

      • normalize

        protected final boolean normalize
        Whether to normalize scores

      • scores

        protected java.util.Map<V,​java.lang.Double> scores
        The actual scores

    • Constructor Detail

      • ClosenessCentrality

        public ClosenessCentrality​(Graph<V,​E> graph)
        Construct a new instance. By default the centrality is normalized and computed using outgoing paths.
        Parameters:
        graph - the input graph

      • ClosenessCentrality

        public ClosenessCentrality​(Graph<V,​E> graph,
                           boolean incoming,
                           boolean normalize)
        Construct a new instance.
        Parameters:
        graph - the input graph
        incoming - if true incoming paths are used, otherwise outgoing paths
        normalize - whether to normalize by multiplying the closeness by $n-1$, where $n$ is the number of vertices of the graph

    • Method Detail

      • getScores

        public java.util.Map<V,​java.lang.Double> getScores()
        Get a map with the scores of all vertices
        Specified by:
        getScores in interface VertexScoringAlgorithm<V,​E>
        Returns:
        a map with all scores

      • getVertexScore

        public java.lang.Double getVertexScore​(V v)
        Get a vertex score
        Specified by:
        getVertexScore in interface VertexScoringAlgorithm<V,​E>
        Parameters:
        v - the vertex
        Returns:
        the score

      • getShortestPathAlgorithm

        protected ShortestPathAlgorithm<V,​E> getShortestPathAlgorithm()
        Get the shortest path algorithm for the paths computation.
        Returns:
        the shortest path algorithm

      • compute

        protected void compute()
        Compute the centrality index