org.graphstream.algorithm

Class BetweennessCentrality

java.lang.Object

org.graphstream.algorithm.BetweennessCentrality

All Implemented Interfaces:

Algorithm

public class BetweennessCentrality
extends java.lang.Object
implements Algorithm

Compute the "betweenness" centrality of each vertex of a given graph.

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.

Usage

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.

Complexity

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).

Example

                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"));
 

Reference

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.

Scientific Reference:

A Faster Algorithm for Betweenness Centrality, Ulrik Brandes, Journal of Mathematical Sociology, 2001, 25:2, pp. 163 - 177", "DOI: 10.1080/0022250X.2001.9990249", On variants of shortest-path betweenness centrality and their generic computation, Ulrik Brandes, Social Networks, vol 30:2", pp. 136 - 145, 2008, issn 0378-8733, "DOI: 10.1016/j.socnet.2007.11.001".

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	BetweennessCentrality.Progress Interface allowing to be notified of the algorithm progress.

Constructor Summary

Constructors

Constructor and Description
BetweennessCentrality() New centrality algorithm that will perform as if the graph was unweighted.
BetweennessCentrality(java.lang.String centralityAttributeName) New centrality algorithm that will perform as if the graph was unweighted.
BetweennessCentrality(java.lang.String centralityAttributeName, java.lang.String weightAttributeName) New centrality algorithm that will perform on a weighted graph, taking the weight of each edge in the given weightAttributeName.

Method Summary

Modifier and Type	Method and Description
void	betweennessCentrality(org.graphstream.graph.Graph graph) Compute the betweenness centrality on the given graph for each node and eventually edges.
double	centrality(org.graphstream.graph.Element elt) The centrality value of the given node or edge.
void	cleanEdges() Delete attributes used by this algorithm in edges of the 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
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.
java.lang.String	defaultMessage()
java.lang.String	getCentralityAttributeName() Name of the attribute used to store centrality values on nodes.
java.lang.String	getWeightAttributeName() Name of the attribute used to retrieve weights on edges.
void	init(org.graphstream.graph.Graph graph) Setup the algorithm to work on the given graph.
void	registerProgressIndicator(BetweennessCentrality.Progress progress) Specify an interface to call in order to indicate the algorithm progress.
void	setCentrality(org.graphstream.graph.Element elt, double centrality) Set the centrality of the given node or edge.
void	setCentralityAttributeName(java.lang.String centralityAttributeName) Specify the name of the attribute used to store the computed centrality values for each node.
void	setUnweighted() Consider all the edges to have the weight.
void	setWeight(org.graphstream.graph.Node from, org.graphstream.graph.Node to, double weight) Set the weight of the edge between 'from' and 'to'.
void	setWeightAttributeName(java.lang.String weightAttributeName) Specify the name of the weight attribute to retrieve edge attributes.
void	setWeighted() Consider the edges to have a weight.
double	weight(org.graphstream.graph.Node from, org.graphstream.graph.Node to) The weight of the edge between 'from' and 'to'.

Methods inherited from class java.lang.Object

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

Constructor Detail

BetweennessCentrality

public BetweennessCentrality()

New centrality algorithm that will perform as if the graph was unweighted. By default the centrality will be stored in a "Cb" attribute on each node.

BetweennessCentrality

public BetweennessCentrality(java.lang.String centralityAttributeName)

New centrality algorithm that will perform as if the graph was unweighted. The centrality for each node will be stored in an attribute whose name is specified by the centralityAttributeName argument.

Parameters:

centralityAttributeName - The name of the attribute used to store the result of the algorithm on each node.

BetweennessCentrality

public BetweennessCentrality(java.lang.String centralityAttributeName,
                             java.lang.String weightAttributeName)

New centrality algorithm that will perform on a weighted graph, taking the weight of each edge in the given 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.

Parameters:

centralityAttributeName - Name to use to store the centrality results on each node.

weightAttributeName - Name to use to retrieve the edge weights.

Method Detail

getWeightAttributeName

public java.lang.String getWeightAttributeName()

Name of the attribute used to retrieve weights on edges.

getCentralityAttributeName

public java.lang.String getCentralityAttributeName()

Name of the attribute used to store centrality values on nodes.

setWeightAttributeName

public void setWeightAttributeName(java.lang.String weightAttributeName)

Specify the name of the weight attribute to retrieve edge attributes. This automatically set the algorithm to perform on the graph as if it was weighted.

setWeighted

public void setWeighted()

Consider the edges to have a weight. By default the weight is stored in a "weight" attribute. You can change this attribute using setWeightAttributeName(String). If an edge has no weight the value 1.0 is used.

setUnweighted

public void setUnweighted()

Consider all the edges to have the weight.

computeEdgeCentrality

public void computeEdgeCentrality(boolean on)

Activate or deactivate the centrality computation on edges. By default it is activated. Notice that this does not change the complexity of the algorithm. Only one more access on the edges is done to store the centrality in addition to the node access.

Parameters:

on - If true, the edges centrality is also computed.

setCentralityAttributeName

public void setCentralityAttributeName(java.lang.String centralityAttributeName)

Specify the name of the attribute used to store the computed centrality values for each node.

registerProgressIndicator

public void registerProgressIndicator(BetweennessCentrality.Progress progress)

Specify an interface to call in order to indicate the algorithm progress. Pass null to remove the progress indicator. The progress indicator will be called regularly to indicate the computation progress.

init

public void init(org.graphstream.graph.Graph graph)

Setup the algorithm to work on the given graph.

Specified by:

init in interface Algorithm

Parameters:

graph - The graph this algorithm is using.

compute

public void compute()

Compute the betweenness centrality on the given graph for each node. The result is by default stored in the "Cb" attribute on each node.

Specified by:

compute in interface Algorithm

See Also:

Algorithm.init(Graph)

betweennessCentrality

public void betweennessCentrality(org.graphstream.graph.Graph graph)

Compute the betweenness centrality on the given graph for each node and eventually edges. This method is equivalent to a call in sequence to the two methods init(Graph) then compute().

centrality

public double centrality(org.graphstream.graph.Element elt)

The centrality value of the given node or edge.

Parameters:

elt - Extract the centrality of this node or edge.

Returns:

The centrality value.

setCentrality

public void setCentrality(org.graphstream.graph.Element elt,
                          double centrality)

Set the centrality of the given node or edge.

Parameters:

elt - The node or edge to modify.

centrality - The centrality to store on the node.

setWeight

public void setWeight(org.graphstream.graph.Node from,
                      org.graphstream.graph.Node to,
                      double weight)

Set the weight of the edge between 'from' and 'to'.

Parameters:

from - The source node.

to - The target node.

weight - The weight to store on the edge between 'from' and 'to'.

weight

public double weight(org.graphstream.graph.Node from,
                     org.graphstream.graph.Node to)

The weight of the edge between 'from' and 'to'.

Parameters:

from - The origin node.

to - The target node.

Returns:

The weight on the edge between 'form' and 'to'.

cleanGraph

public void cleanGraph()

Delete attributes used by this algorithm in nodes and edges of the graph

cleanNodes

public void cleanNodes()

Delete attributes used by this algorithm in nodes of the graph

cleanEdges

public void cleanEdges()

Delete attributes used by this algorithm in edges of the graph

defaultMessage

public java.lang.String defaultMessage()