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,​Double>
    public class BetweennessCentrality<V,​E>
extends Object
implements VertexScoringAlgorithm<V,​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)$.
    Author:
    Assaf Mizrachi

    • 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