## Class ApBetweennessCentrality<V,​E>

• java.lang.Object
• org.jgrapht.alg.scoring.ApBetweennessCentrality<V,​E>
• Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
VertexScoringAlgorithm<V,​org.apfloat.Apfloat>

public class ApBetweennessCentrality<V,​E>
extends java.lang.Object
implements VertexScoringAlgorithm<V,​org.apfloat.Apfloat>
Betweenness centrality with arbitrary precision arithmetic.

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 thus it is not safe to assume that arithmetic takes constant time. This class uses arbitrary precision arithmetic (except for the execution of Dijkstra's algorithm). The precision can be adjusted by the constructor parameters.
Author:
Assaf Mizrachi
• ### Constructor Summary

Constructors
Constructor Description
ApBetweennessCentrality​(Graph<V,​E> graph)
Construct a new instance.
ApBetweennessCentrality​(Graph<V,​E> graph, boolean normalize)
Construct a new instance.
ApBetweennessCentrality​(Graph<V,​E> graph, boolean normalize, long precision)
Construct a new instance.
• ### Method Summary

All Methods
Modifier and Type Method Description
java.util.Map<V,​org.apfloat.Apfloat> getScores()
Get a map with the scores of all vertices
org.apfloat.Apfloat 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
• ### Constructor Detail

• #### ApBetweennessCentrality

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

public ApBetweennessCentrality​(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
• #### ApBetweennessCentrality

public ApBetweennessCentrality​(Graph<V,​E> graph,
boolean normalize,
long precision)
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
precision - precision for arbitrary precision arithmetic
• ### Method Detail

• #### getScores

public java.util.Map<V,​org.apfloat.Apfloat> 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 org.apfloat.Apfloat getVertexScore​(V v)
Get a vertex score
Specified by:
getVertexScore in interface VertexScoringAlgorithm<V,​E>
Parameters:
v - the vertex
Returns:
the score