public class BetweennessCentrality extends Object implements Algorithm
The betweenness centrality counts how many shortest paths between each pair of nodes of the graph pass by a node. It does it for all nodes of the graph.
This algorithm, by default, stores the centrality values for each node inside the "Cb" attribute. You can change this attribute name at construction time.
This algorithm does not accept multi-graphs (p-graphs with p>1) yet.
This algorithm does not take into account edge direction yet.
By default the
weight attribute name is "weight", you can activate the weights using
setWeighted()
. You can change the weight attribute name using the
dedicated constructor or the setWeightAttributeName(String)
method.
This method implicitly enable weights in the computation. Use
setUnweighted()
to disable weights.
The result of the computation is stored on each node inside the "Cb"
attribute. You can change the name of this attribute using the dedicated
constructor or the setCentralityAttributeName(String)
method.
As the computing of centrality can take a lot of time, you can provide a
progress 'callback' to get notified each time the algorithm finished
processing a node (however the centrality values are usable only when the
algorithm finished). See the registerProgressIndicator(Progress)
method.
By default the algorithm performs on a graph considered as not weighted with complexity O(nm). You can specify that the graph edges contain weights in which case the algorithm complexity is O(nm + n^2 log n).
Graph graph = new SingleGraph("Betweenness Test"); // E----D AB=1, BC=5, CD=3, DE=2, BE=6, EA=4 // /| | Cb(A)=4 // / | | Cb(B)=2 // A | | Cb(C)=0 // \ | | Cb(D)=2 // \| | Cb(E)=4 // B----C Node A = graph.addNode("A"); Node B = graph.addNode("B"); Node E = graph.addNode("E"); Node C = graph.addNode("C"); Node D = graph.addNode("D"); graph.addEdge("AB", "A", "B"); graph.addEdge("BE", "B", "E"); graph.addEdge("BC", "B", "C"); graph.addEdge("ED", "E", "D"); graph.addEdge("CD", "C", "D"); graph.addEdge("AE", "A", "E"); bcb.setWeight(A, B, 1); bcb.setWeight(B, E, 6); bcb.setWeight(B, C, 5); bcb.setWeight(E, D, 2); bcb.setWeight(C, D, 3); bcb.setWeight(A, E, 4); BetweennessCentrality bcb = new BetweennessCentrality(); bcb.setWeightAttributeName("weight"); bcb.init(graph); bcb.compute(); System.out.println("A="+ graph.getNode("A").getAttribute("Cb")); System.out.println("B="+ graph.getNode("B").getAttribute("Cb")); System.out.println("C="+ graph.getNode("C").getAttribute("Cb")); System.out.println("D="+ graph.getNode("D").getAttribute("Cb")); System.out.println("E="+ graph.getNode("E").getAttribute("Cb"));
This is based on the algorithm described in "A Faster Algorithm for Betweenness Centrality", Ulrik Brandes, Journal of Mathematical Sociology, 2001, and in "On variants of shortest-path betweenness centrality and their generic computation", of the same author, 2008.
Modifier and Type | Class and Description |
---|---|
protected class |
BetweennessCentrality.BrandesNodeComparatorLargerFirst
Increasing comparator used for priority queues.
|
protected class |
BetweennessCentrality.BrandesNodeComparatorSmallerFirst
Decreasing comparator used for priority queues.
|
static interface |
BetweennessCentrality.Progress
Interface allowing to be notified of the algorithm progress.
|
Modifier and Type | Field and Description |
---|---|
protected String |
centralityAttributeName
Store the centrality value in this attribute on nodes and edges.
|
protected String |
deltaAttributeName
The delta value.
|
protected String |
distAttributeName
The distance value.
|
protected boolean |
doEdges
Compute the centrality of edges.
|
protected Graph |
graph
The graph to modify.
|
protected static double |
INFINITY |
protected String |
predAttributeName
The predecessors.
|
protected BetweennessCentrality.Progress |
progress
The progress call-back method.
|
protected String |
sigmaAttributeName
The sigma value.
|
protected boolean |
unweighted
Do not use weights ?
|
protected String |
weightAttributeName
Name of the attribute used to retrieve weights on edges.
|
Constructor and Description |
---|
BetweennessCentrality()
New centrality algorithm that will perform as if the graph was
unweighted.
|
BetweennessCentrality(String centralityAttributeName)
New centrality algorithm that will perform as if the graph was
unweighted.
|
BetweennessCentrality(String centralityAttributeName,
String weightAttributeName)
New centrality algorithm that will perform on a weighted graph, taking
the weight of each edge in the given
weightAttributeName . |
Modifier and Type | Method and Description |
---|---|
protected void |
addToPredecessorsOf(Node node,
Node predecessor)
Add a node to the predecessors of another.
|
void |
betweennessCentrality(Graph graph)
Compute the betweenness centrality on the given graph for each node and
eventually edges.
|
double |
centrality(Element elt)
The centrality value of the given node or edge.
|
void |
cleanEdges()
Delete attributes used by this algorithm in edges of the graph
|
private void |
cleanElement(Iterable<? extends Element> it)
Delete attributes used by this algorithm in elements of a graph
|
void |
cleanGraph()
Delete attributes used by this algorithm in nodes and edges of the graph
|
void |
cleanNodes()
Delete attributes used by this algorithm in nodes of the graph
|
protected void |
clearPredecessorsOf(Node node)
Remove all predecessors of the given node.
|
void |
compute()
Compute the betweenness centrality on the given graph for each node.
|
void |
computeEdgeCentrality(boolean on)
Activate or deactivate the centrality computation on edges.
|
protected double |
delta(Node node)
The delta value of the given node.
|
protected PriorityQueue<Node> |
dijkstraExplore(Node source,
Graph graph)
Compute single-source multiple-targets paths on a weighted graph.
|
protected PriorityQueue<Node> |
dijkstraExplore2(Node source,
Graph graph)
The implementation of the Brandes paper.
|
protected double |
distance(Node node)
The distance value of the given node.
|
String |
getCentralityAttributeName()
Name of the attribute used to store centrality values on nodes.
|
String |
getWeightAttributeName()
Name of the attribute used to retrieve weights on edges.
|
void |
init(Graph graph)
Setup the algorithm to work on the given graph.
|
protected void |
initAllEdges(Graph graph)
Set a default centrality of 0 to all edges.
|
protected void |
initAllNodes(Graph graph)
Set a default centrality of 0 to all nodes.
|
protected Set<Node> |
predecessorsOf(Node node)
List of predecessors of the given node.
|
void |
registerProgressIndicator(BetweennessCentrality.Progress progress)
Specify an interface to call in order to indicate the algorithm progress.
|
protected void |
replacePredecessorsOf(Node node,
Node predecessor)
Remove all predecessors of the given node and then add it a first
predecessor.
|
void |
setCentrality(Element elt,
double centrality)
Set the centrality of the given node or edge.
|
void |
setCentralityAttributeName(String centralityAttributeName)
Specify the name of the attribute used to store the computed centrality
values for each node.
|
protected void |
setDelta(Node node,
double delta)
Set the delta value of the given node.
|
protected void |
setDistance(Node node,
double distance)
Set the distance value of the given node.
|
protected void |
setSigma(Node node,
double sigma)
Set the sigma value of the given node.
|
void |
setUnweighted()
Consider all the edges to have the weight.
|
protected void |
setupAllNodes(Graph graph)
Add a default value for attributes used during computation.
|
void |
setWeight(Node from,
Node to,
double weight)
Set the weight of the edge between 'from' and 'to'.
|
void |
setWeightAttributeName(String weightAttributeName)
Specify the name of the weight attribute to retrieve edge attributes.
|
void |
setWeighted()
Consider the edges to have a weight.
|
protected double |
sigma(Node node)
The sigma value of the given node.
|
protected PriorityQueue<Node> |
simpleExplore(Node source,
Graph graph)
Compute single-source multiple-targets shortest paths on an unweighted
graph.
|
protected void |
updatePriority(PriorityQueue<Node> Q,
Node node)
Update the given priority queue if the given node changed its priority
(here distance) and if the node is already part of the queue.
|
double |
weight(Node from,
Node to)
The weight of the edge between 'from' and 'to'.
|
protected static double INFINITY
protected String centralityAttributeName
protected String predAttributeName
protected String sigmaAttributeName
protected String distAttributeName
protected String deltaAttributeName
protected String weightAttributeName
protected boolean unweighted
protected BetweennessCentrality.Progress progress
protected boolean doEdges
public BetweennessCentrality()
public BetweennessCentrality(String centralityAttributeName)
centralityAttributeName
argument.centralityAttributeName
- The name of the attribute used to store the result of the
algorithm on each node.public BetweennessCentrality(String centralityAttributeName, String weightAttributeName)
weightAttributeName
.
The result of the algorithm is stored for each node using the given
centralityAttributeName
. If an edge has no weight attribute,
it is considered as having a weight of one.centralityAttributeName
- Name to use to store the centrality results on each node.weightAttributeName
- Name to use to retrieve the edge weights.public String getWeightAttributeName()
public String getCentralityAttributeName()
public void setWeightAttributeName(String weightAttributeName)
public void setWeighted()
setWeightAttributeName(String)
. If an edge has no weight the
value 1.0 is used.public void setUnweighted()
public void computeEdgeCentrality(boolean on)
on
- If true, the edges centrality is also computed.public void setCentralityAttributeName(String centralityAttributeName)
public void registerProgressIndicator(BetweennessCentrality.Progress progress)
public void compute()
compute
in interface Algorithm
Algorithm.init(Graph)
public void betweennessCentrality(Graph graph)
init(Graph)
then compute()
.protected PriorityQueue<Node> simpleExplore(Node source, Graph graph)
source
- The source node.graph
- The graph.protected PriorityQueue<Node> dijkstraExplore(Node source, Graph graph)
source
- The source node.graph
- The graph.protected PriorityQueue<Node> dijkstraExplore2(Node source, Graph graph)
protected void updatePriority(PriorityQueue<Node> Q, Node node)
Q
- The queue.node
- The node.protected double sigma(Node node)
node
- Extract the sigma value of this node.protected double distance(Node node)
node
- Extract the distance value of this node.protected double delta(Node node)
node
- Extract the delta value of this node.public double centrality(Element elt)
elt
- Extract the centrality of this node or edge.protected Set<Node> predecessorsOf(Node node)
node
- Extract the predecessors of this node.protected void setSigma(Node node, double sigma)
node
- The node to modify.sigma
- The sigma value to store on the node.protected void setDistance(Node node, double distance)
node
- The node to modify.distance
- The delta value to store on the node.protected void setDelta(Node node, double delta)
node
- The node to modify.delta
- The delta value to store on the node.public void setCentrality(Element elt, double centrality)
elt
- The node or edge to modify.centrality
- The centrality to store on the node.public void setWeight(Node from, Node to, double weight)
from
- The source node.to
- The target node.weight
- The weight to store on the edge between 'from' and 'to'.public double weight(Node from, Node to)
from
- The origin node.to
- The target node.protected void replacePredecessorsOf(Node node, Node predecessor)
node
- The node to modify.predecessor
- The predecessor to add.protected void addToPredecessorsOf(Node node, Node predecessor)
node
- Modify the predecessors of this node.predecessor
- The predecessor to add.protected void clearPredecessorsOf(Node node)
node
- Remove all predecessors of this node.protected void initAllNodes(Graph graph)
graph
- The graph to modify.protected void initAllEdges(Graph graph)
graph
- The graph to modify.protected void setupAllNodes(Graph graph)
graph
- The graph to modify.public void cleanGraph()
public void cleanNodes()
public void cleanEdges()
private void cleanElement(Iterable<? extends Element> it)
it
- the list of elementsWebARTS Library Licensed Under the GNU - General Public License. Other Libraries licensed under their respective Open Source Licenses