Module org.jgrapht.core

Package org.jgrapht.alg.scoring

Class EdgeBetweennessCentrality<V,E>

java.lang.Object

org.jgrapht.alg.scoring.EdgeBetweennessCentrality<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

EdgeScoringAlgorithm<E,Double>

public class EdgeBetweennessCentrality<V,E>
extends Object
implements EdgeScoringAlgorithm<E,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.

Author:

Dimitrios Michail

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static enum	EdgeBetweennessCentrality.OverflowStrategy	Strategy followed when counting paths.

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, Iterable<V> startVertices)	Construct a new instance.

Method Summary

Modifier and Type	Method	Description
Double	getEdgeScore(E e)	Get an edge score
Map<E,Double>	getScores()	Get a map with the scores of all edges

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

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 graph

overflowStrategy - strategy to use if overflow is detected

EdgeBetweennessCentrality

public EdgeBetweennessCentrality(Graph<V,E> graph,
 EdgeBetweennessCentrality.OverflowStrategy overflowStrategy,
 Iterable<V> startVertices)

Construct a new instance.

Parameters:

graph - the input graph

overflowStrategy - strategy to use if overflow is detected

startVertices - 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 Details

getScores

public Map<E,Double> getScores()

Description copied from interface: EdgeScoringAlgorithm

Get a map with the scores of all edges

Specified by:

getScores in interface EdgeScoringAlgorithm<V,E>

Returns:

a map with all scores

getEdgeScore

public Double getEdgeScore(E e)

Description copied from interface: EdgeScoringAlgorithm

Get an edge score

Specified by:

getEdgeScore in interface EdgeScoringAlgorithm<V,E>

Parameters:

e - the edge

Returns:

the score