2 * Copyright (c) 2003, the JUNG Project and the Regents of the University
6 * This software is open-source under the BSD license; see either
8 * http://jung.sourceforge.net/license.txt for a description.
10 package edu.uci.ics.jung.algorithms.importance;
12 import java.util.ArrayList;
13 import java.util.Collection;
14 import java.util.HashMap;
15 import java.util.List;
17 import java.util.Stack;
19 import org.apache.commons.collections15.Buffer;
20 import org.apache.commons.collections15.buffer.UnboundedFifoBuffer;
22 import edu.uci.ics.jung.graph.Graph;
23 import edu.uci.ics.jung.graph.UndirectedGraph;
26 * Computes betweenness centrality for each vertex and edge in the graph. The result is that each vertex
27 * and edge has a UserData element of type MutableDouble whose key is 'centrality.BetweennessCentrality'.
28 * Note: Many social network researchers like to normalize the betweenness values by dividing the values by
29 * (n-1)(n-2)/2. The values given here are unnormalized.<p>
31 * A simple example of usage is:
33 * BetweennessCentrality ranker = new BetweennessCentrality(someGraph);
35 * ranker.printRankings();
38 * Running time is: O(n^2 + nm).
39 * @see "Ulrik Brandes: A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25(2):163-177, 2001."
41 * @author Tom Nelson converted to jung2
44 public class BetweennessCentrality<V,E> extends AbstractRanker<V,E> {
46 public static final String CENTRALITY = "centrality.BetweennessCentrality";
49 * Constructor which initializes the algorithm
50 * @param g the graph whose nodes are to be analyzed
52 public BetweennessCentrality(Graph<V,E> g) {
53 initialize(g, true, true);
56 public BetweennessCentrality(Graph<V,E> g, boolean rankNodes) {
57 initialize(g, rankNodes, true);
60 public BetweennessCentrality(Graph<V,E> g, boolean rankNodes, boolean rankEdges)
62 initialize(g, rankNodes, rankEdges);
65 protected void computeBetweenness(Graph<V,E> graph) {
67 Map<V,BetweennessData> decorator = new HashMap<V,BetweennessData>();
68 Map<V,Number> bcVertexDecorator =
69 vertexRankScores.get(getRankScoreKey());
70 bcVertexDecorator.clear();
71 Map<E,Number> bcEdgeDecorator =
72 edgeRankScores.get(getRankScoreKey());
73 bcEdgeDecorator.clear();
75 Collection<V> vertices = graph.getVertices();
77 for (V s : vertices) {
79 initializeData(graph,decorator);
81 decorator.get(s).numSPs = 1;
82 decorator.get(s).distance = 0;
84 Stack<V> stack = new Stack<V>();
85 Buffer<V> queue = new UnboundedFifoBuffer<V>();
88 while (!queue.isEmpty()) {
92 for(V w : getGraph().getSuccessors(v)) {
94 if (decorator.get(w).distance < 0) {
96 decorator.get(w).distance = decorator.get(v).distance + 1;
99 if (decorator.get(w).distance == decorator.get(v).distance + 1) {
100 decorator.get(w).numSPs += decorator.get(v).numSPs;
101 decorator.get(w).predecessors.add(v);
106 while (!stack.isEmpty()) {
109 for (V v : decorator.get(w).predecessors) {
111 double partialDependency = (decorator.get(v).numSPs / decorator.get(w).numSPs);
112 partialDependency *= (1.0 + decorator.get(w).dependency);
113 decorator.get(v).dependency += partialDependency;
114 E currentEdge = getGraph().findEdge(v, w);
115 double edgeValue = bcEdgeDecorator.get(currentEdge).doubleValue();
116 edgeValue += partialDependency;
117 bcEdgeDecorator.put(currentEdge, edgeValue);
120 double bcValue = bcVertexDecorator.get(w).doubleValue();
121 bcValue += decorator.get(w).dependency;
122 bcVertexDecorator.put(w, bcValue);
127 if(graph instanceof UndirectedGraph) {
128 for (V v : vertices) {
129 double bcValue = bcVertexDecorator.get(v).doubleValue();
131 bcVertexDecorator.put(v, bcValue);
133 for (E e : graph.getEdges()) {
134 double bcValue = bcEdgeDecorator.get(e).doubleValue();
136 bcEdgeDecorator.put(e, bcValue);
140 for (V vertex : vertices) {
141 decorator.remove(vertex);
145 private void initializeData(Graph<V,E> g, Map<V,BetweennessData> decorator) {
146 for (V vertex : g.getVertices()) {
148 Map<V,Number> bcVertexDecorator = vertexRankScores.get(getRankScoreKey());
149 if(bcVertexDecorator.containsKey(vertex) == false) {
150 bcVertexDecorator.put(vertex, 0.0);
152 decorator.put(vertex, new BetweennessData());
154 for (E e : g.getEdges()) {
156 Map<E,Number> bcEdgeDecorator = edgeRankScores.get(getRankScoreKey());
157 if(bcEdgeDecorator.containsKey(e) == false) {
158 bcEdgeDecorator.put(e, 0.0);
164 * the user datum key used to store the rank scores
168 public String getRankScoreKey() {
174 computeBetweenness(getGraph());
177 class BetweennessData {
180 List<V> predecessors;
186 predecessors = new ArrayList<V>();