- java.lang.Object
-
- org.jgrapht.alg.scoring.EdgeBetweennessCentrality<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
EdgeScoringAlgorithm<E,java.lang.Double>
public class EdgeBetweennessCentrality<V,E> extends java.lang.Object implements EdgeScoringAlgorithm<E,java.lang.Double>
Edge betweenness centrality.A natural extension of betweenness to edges by counting the total shortest paths that pass through an edge. See the paper: Ulrik Brandes: On Variants of Shortest-Path Betweenness Centrality and their Generic Computation. Social Networks 30(2):136-145, 2008, for a nice discussion of different variants of betweenness centrality. Note that this implementation does not work for graphs which have multiple edges. Self-loops do not influence the result and are thus ignored.
This implementation allows the user to compute centrality contributions only from a subset of the graph vertices, i.e. to start shortest path computations only from a subset of the vertices. This allows centrality approximations in big graphs. Note that in this case, the user is responsible for any normalization necessary due to duplicate shortest paths that might occur in undirected graphs.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private class
EdgeBetweennessCentrality.Algorithm
static class
EdgeBetweennessCentrality.OverflowStrategy
Strategy followed when counting paths.private class
EdgeBetweennessCentrality.WeightedAlgorithm
-
Field Summary
Fields Modifier and Type Field Description private boolean
divideByTwo
private Graph<V,E>
graph
private EdgeBetweennessCentrality.OverflowStrategy
overflowStrategy
private java.util.Map<E,java.lang.Double>
scores
private java.lang.Iterable<V>
startVertices
-
Constructor Summary
Constructors Constructor Description EdgeBetweennessCentrality(Graph<V,E> graph)
Construct a new instance.EdgeBetweennessCentrality(Graph<V,E> graph, EdgeBetweennessCentrality.OverflowStrategy overflowStrategy)
Construct a new instance.EdgeBetweennessCentrality(Graph<V,E> graph, EdgeBetweennessCentrality.OverflowStrategy overflowStrategy, java.lang.Iterable<V> startVertices)
Construct a new instance.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description java.lang.Double
getEdgeScore(E e)
Get an edge scorejava.util.Map<E,java.lang.Double>
getScores()
Get a map with the scores of all edges
-
-
-
Field Detail
-
startVertices
private final java.lang.Iterable<V> startVertices
-
divideByTwo
private final boolean divideByTwo
-
scores
private java.util.Map<E,java.lang.Double> scores
-
overflowStrategy
private final EdgeBetweennessCentrality.OverflowStrategy overflowStrategy
-
-
Constructor Detail
-
EdgeBetweennessCentrality
public EdgeBetweennessCentrality(Graph<V,E> graph)
Construct a new instance.- Parameters:
graph
- the input graph
-
EdgeBetweennessCentrality
public EdgeBetweennessCentrality(Graph<V,E> graph, EdgeBetweennessCentrality.OverflowStrategy overflowStrategy)
Construct a new instance.- Parameters:
graph
- the input graphoverflowStrategy
- strategy to use if overflow is detected
-
EdgeBetweennessCentrality
public EdgeBetweennessCentrality(Graph<V,E> graph, EdgeBetweennessCentrality.OverflowStrategy overflowStrategy, java.lang.Iterable<V> startVertices)
Construct a new instance.- Parameters:
graph
- the input graphoverflowStrategy
- strategy to use if overflow is detectedstartVertices
- vertices from which to start shortest path computations. This parameter allows the user to compute edge centrality contributions only from a subset of the vertices of the graph. If null the whole graph vertex set is used.
-
-
Method Detail
-
getScores
public java.util.Map<E,java.lang.Double> getScores()
Description copied from interface:EdgeScoringAlgorithm
Get a map with the scores of all edges- Specified by:
getScores
in interfaceEdgeScoringAlgorithm<V,E>
- Returns:
- a map with all scores
-
getEdgeScore
public java.lang.Double getEdgeScore(E e)
Description copied from interface:EdgeScoringAlgorithm
Get an edge score- Specified by:
getEdgeScore
in interfaceEdgeScoringAlgorithm<V,E>
- Parameters:
e
- the edge- Returns:
- the score
-
-