- java.lang.Object
-
- org.jgrapht.alg.scoring.BetweennessCentrality<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- 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.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static interface
BetweennessCentrality.MyQueue<T,D>
static class
BetweennessCentrality.OverflowStrategy
Strategy followed when counting paths.private class
BetweennessCentrality.UnweightedQueue
private class
BetweennessCentrality.WeightedQueue
-
Field Summary
Fields Modifier and Type Field Description private Graph<V,E>
graph
Underlying graphprivate boolean
normalize
Whether to normalize scoresprivate BetweennessCentrality.OverflowStrategy
overflowStrategy
Strategy for overflow when counting paths.private java.util.Map<V,java.lang.Double>
scores
The actual scores
-
Constructor Summary
Constructors Constructor Description BetweennessCentrality(Graph<V,E> graph)
Construct a new instance.BetweennessCentrality(Graph<V,E> graph, boolean normalize)
Construct a new instance.BetweennessCentrality(Graph<V,E> graph, boolean normalize, BetweennessCentrality.OverflowStrategy overflowStrategy)
Construct a new instance.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
compute()
Compute the centrality indexprivate void
compute(V s)
java.util.Map<V,java.lang.Double>
getScores()
Get a map with the scores of all verticesjava.lang.Double
getVertexScore(V v)
Get a vertex score
-
-
-
Field Detail
-
normalize
private final boolean normalize
Whether to normalize scores
-
scores
private java.util.Map<V,java.lang.Double> scores
The actual scores
-
overflowStrategy
private BetweennessCentrality.OverflowStrategy overflowStrategy
Strategy for overflow when counting paths.
-
-
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 graphnormalize
- 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 graphnormalize
- whether to normalize by dividing the closeness by $(n-1) \cdot (n-2)$, where $n$ is the number of vertices of the graphoverflowStrategy
- 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 interfaceVertexScoringAlgorithm<V,E>
- Returns:
- a map with all scores
-
getVertexScore
public java.lang.Double getVertexScore(V v)
Get a vertex score- Specified by:
getVertexScore
in interfaceVertexScoringAlgorithm<V,E>
- Parameters:
v
- the vertex- Returns:
- the score
-
compute
private void compute()
Compute the centrality index
-
compute
private void compute(V s)
-
-