Module org.jgrapht.core
Package org.jgrapht.alg.scoring

Class BetweennessCentrality<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    VertexScoringAlgorithm<V,​java.lang.Double>
    public class BetweennessCentrality<V,​E>
extends java.lang.Object
implements VertexScoringAlgorithm<V,​java.lang.Double>
    Betweenness centrality.

    Computes the betweenness centrality of each vertex of a graph. The betweenness centrality 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. The algorithm is based on

    • Brandes, Ulrik (2001). "A faster algorithm for betweenness centrality". Journal of Mathematical Sociology. 25 (2): 163–177.
    The running time is $O(nm)$ and $O(nm +n^2 \log n)$ for unweighted and weighted graph respectively, where $n$ is the number of vertices and $m$ the number of edges of the graph. The space complexity is $O(n + m)$. Note that this running time assumes that arithmetic is performed between numbers whose representation needs a number of bits which is logarithmic in the instance size. There are instances where this is not true and path counters might grow super exponential. This class allows the user to adjust whether an exception is thrown in case overflow occurs. Default behavior is to ignore overflow issues.

    • Field Detail

      • graph

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

      • normalize

        private final boolean normalize
        Whether to normalize scores

      • scores

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

    • Constructor Detail

      • BetweennessCentrality

        public BetweennessCentrality​(Graph<V,​E> graph)
        Construct a new instance.
        Parameters:
        graph - the input graph

      • BetweennessCentrality

        public BetweennessCentrality​(Graph<V,​E> graph,
                             boolean normalize)
        Construct a new instance.
        Parameters:
        graph - the input graph
        normalize - whether to normalize by dividing the closeness by $(n-1) \cdot (n-2)$, where $n$ is the number of vertices of the graph

      • BetweennessCentrality

        public BetweennessCentrality​(Graph<V,​E> graph,
                             boolean normalize,
                             BetweennessCentrality.OverflowStrategy overflowStrategy)
        Construct a new instance.
        Parameters:
        graph - the input graph
        normalize - whether to normalize by dividing the closeness by $(n-1) \cdot (n-2)$, where $n$ is the number of vertices of the graph
        overflowStrategy - strategy to use if overflow is detected

    • 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

      • compute

        private void compute()
        Compute the centrality index

      • compute

        private void compute​(V s)