2 * Copyright (c) 2008, 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.
9 * Created on Sep 16, 2008
12 package edu.uci.ics.jung.algorithms.scoring;
14 import java.util.ArrayList;
15 import java.util.Comparator;
16 import java.util.HashMap;
17 import java.util.LinkedList;
18 import java.util.List;
20 import java.util.Queue;
21 import java.util.Stack;
23 import org.apache.commons.collections15.Transformer;
24 import org.apache.commons.collections15.functors.ConstantTransformer;
26 import edu.uci.ics.jung.algorithms.util.MapBinaryHeap;
27 import edu.uci.ics.jung.graph.Graph;
28 import edu.uci.ics.jung.graph.UndirectedGraph;
31 * Computes betweenness centrality for each vertex and edge in the graph.
33 * @see "Ulrik Brandes: A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25(2):163-177, 2001."
35 public class BetweennessCentrality<V, E>
36 implements VertexScorer<V, Double>, EdgeScorer<E, Double>
38 protected Graph<V,E> graph;
39 protected Map<V, Double> vertex_scores;
40 protected Map<E, Double> edge_scores;
41 protected Map<V, BetweennessData> vertex_data;
44 * Calculates betweenness scores based on the all-pairs unweighted shortest paths
46 * @param graph the graph for which the scores are to be calculated
48 @SuppressWarnings("unchecked")
49 public BetweennessCentrality(Graph<V, E> graph)
52 computeBetweenness(new LinkedList<V>(), new ConstantTransformer(1));
56 * Calculates betweenness scores based on the all-pairs weighted shortest paths in the
59 * <p>NOTE: This version of the algorithm may not work correctly on all graphs; we're still
60 * working out the bugs. Use at your own risk.
61 * @param graph the graph for which the scores are to be calculated
62 * @param edge_weights the edge weights to be used in the path length calculations
64 public BetweennessCentrality(Graph<V, E> graph,
65 Transformer<E, ? extends Number> edge_weights)
67 // reject negative-weight edges up front
68 for (E e : graph.getEdges())
70 double e_weight = edge_weights.transform(e).doubleValue();
72 throw new IllegalArgumentException(String.format(
73 "Weight for edge '%s' is < 0: %d", e, e_weight));
77 computeBetweenness(new MapBinaryHeap<V>(new BetweennessComparator()),
81 protected void initialize(Graph<V,E> graph)
84 this.vertex_scores = new HashMap<V, Double>();
85 this.edge_scores = new HashMap<E, Double>();
86 this.vertex_data = new HashMap<V, BetweennessData>();
88 for (V v : graph.getVertices())
89 this.vertex_scores.put(v, 0.0);
91 for (E e : graph.getEdges())
92 this.edge_scores.put(e, 0.0);
95 protected void computeBetweenness(Queue<V> queue,
96 Transformer<E, ? extends Number> edge_weights)
98 for (V v : graph.getVertices())
100 // initialize the betweenness data for this new vertex
101 for (V s : graph.getVertices())
102 this.vertex_data.put(s, new BetweennessData());
104 // if (v.equals(new Integer(0)))
105 // System.out.println("pause");
107 vertex_data.get(v).numSPs = 1;
108 vertex_data.get(v).distance = 0;
110 Stack<V> stack = new Stack<V>();
111 // Buffer<V> queue = new UnboundedFifoBuffer<V>();
115 while (!queue.isEmpty())
117 // V w = queue.remove();
120 BetweennessData w_data = vertex_data.get(w);
122 for (E e : graph.getOutEdges(w))
124 // TODO (jrtom): change this to getOtherVertices(w, e)
125 V x = graph.getOpposite(w, e);
128 double wx_weight = edge_weights.transform(e).doubleValue();
131 // for(V x : graph.getSuccessors(w))
136 // FIXME: the other problem is that I need to
137 // keep putting the neighbors of things we've just
138 // discovered in the queue, if they're undiscovered or
139 // at greater distance.
141 // FIXME: this is the problem, right here, I think:
142 // need to update position in queue if distance changes
143 // (which can only happen with weighted edges).
144 // for each outgoing edge e from w, get other end x
145 // if x not already visited (dist x < 0)
146 // set x's distance to w's dist + edge weight
147 // add x to queue; pri in queue is x's dist
148 // if w's dist + edge weight < x's dist
150 // update x in queue (MapBinaryHeap)
151 // clear x's incoming edge list
152 // if w's dist + edge weight = x's dist
153 // add e to x's incoming edge list
155 BetweennessData x_data = vertex_data.get(x);
156 double x_potential_dist = w_data.distance + wx_weight;
158 if (x_data.distance < 0)
161 // vertex_data.get(x).distance = vertex_data.get(w).distance + 1;
162 x_data.distance = x_potential_dist;
167 // (1) this can only happen with weighted edges
168 // (2) x's SP count and incoming edges are updated below
169 if (x_data.distance > x_potential_dist)
171 x_data.distance = x_potential_dist;
172 // invalidate previously identified incoming edges
173 // (we have a new shortest path distance to x)
174 x_data.incomingEdges.clear();
175 // update x's position in queue
176 ((MapBinaryHeap<V>)queue).update(x);
178 // if (vertex_data.get(x).distance == vertex_data.get(w).distance + 1)
180 // if (x_data.distance == x_potential_dist)
182 // x_data.numSPs += w_data.numSPs;
183 //// vertex_data.get(x).predecessors.add(w);
184 // x_data.incomingEdges.add(e);
187 for (E e: graph.getOutEdges(w))
189 V x = graph.getOpposite(w, e);
192 double e_weight = edge_weights.transform(e).doubleValue();
193 BetweennessData x_data = vertex_data.get(x);
194 double x_potential_dist = w_data.distance + e_weight;
195 if (x_data.distance == x_potential_dist)
197 x_data.numSPs += w_data.numSPs;
198 // vertex_data.get(x).predecessors.add(w);
199 x_data.incomingEdges.add(e);
203 while (!stack.isEmpty())
207 // for (V w : vertex_data.get(x).predecessors)
208 for (E e : vertex_data.get(x).incomingEdges)
210 V w = graph.getOpposite(x, e);
211 double partialDependency =
212 vertex_data.get(w).numSPs / vertex_data.get(x).numSPs *
213 (1.0 + vertex_data.get(x).dependency);
214 vertex_data.get(w).dependency += partialDependency;
215 // E w_x = graph.findEdge(w, x);
216 // double w_x_score = edge_scores.get(w_x).doubleValue();
217 // w_x_score += partialDependency;
218 // edge_scores.put(w_x, w_x_score);
219 double e_score = edge_scores.get(e).doubleValue();
220 edge_scores.put(e, e_score + partialDependency);
224 double x_score = vertex_scores.get(x).doubleValue();
225 x_score += vertex_data.get(x).dependency;
226 vertex_scores.put(x, x_score);
231 if(graph instanceof UndirectedGraph)
233 for (V v : graph.getVertices()) {
234 double v_score = vertex_scores.get(v).doubleValue();
236 vertex_scores.put(v, v_score);
238 for (E e : graph.getEdges()) {
239 double e_score = edge_scores.get(e).doubleValue();
241 edge_scores.put(e, e_score);
248 // protected void computeWeightedBetweenness(Transformer<E, ? extends Number> edge_weights)
250 // for (V v : graph.getVertices())
252 // // initialize the betweenness data for this new vertex
253 // for (V s : graph.getVertices())
254 // this.vertex_data.put(s, new BetweennessData());
255 // vertex_data.get(v).numSPs = 1;
256 // vertex_data.get(v).distance = 0;
258 // Stack<V> stack = new Stack<V>();
259 //// Buffer<V> queue = new UnboundedFifoBuffer<V>();
260 // SortedSet<V> pqueue = new TreeSet<V>(new BetweennessComparator());
264 //// while (!queue.isEmpty())
265 // while (!pqueue.isEmpty())
267 //// V w = queue.remove();
268 // V w = pqueue.first();
272 //// for(V x : graph.getSuccessors(w))
273 // for (E e : graph.getOutEdges(w))
275 // // TODO (jrtom): change this to getOtherVertices(w, e)
276 // V x = graph.getOpposite(w, e);
279 // double e_weight = edge_weights.transform(e).doubleValue();
281 // if (vertex_data.get(x).distance < 0)
285 //// vertex_data.get(x).distance = vertex_data.get(w).distance + 1;
286 // vertex_data.get(x).distance =
287 // vertex_data.get(w).distance + e_weight;
290 //// if (vertex_data.get(x).distance == vertex_data.get(w).distance + 1)
291 // if (vertex_data.get(x).distance ==
292 // vertex_data.get(w).distance + e_weight)
294 // vertex_data.get(x).numSPs += vertex_data.get(w).numSPs;
295 // vertex_data.get(x).predecessors.add(w);
299 // updateScores(v, stack);
302 // if(graph instanceof UndirectedGraph)
303 // adjustUndirectedScores();
305 // vertex_data.clear();
308 public Double getVertexScore(V v)
310 return vertex_scores.get(v);
313 public Double getEdgeScore(E e)
315 return edge_scores.get(e);
318 private class BetweennessData
322 // List<V> predecessors;
323 List<E> incomingEdges;
330 // predecessors = new ArrayList<V>();
331 incomingEdges = new ArrayList<E>();
336 public String toString()
338 return "[d:" + distance + ", sp:" + numSPs +
339 ", p:" + incomingEdges + ", d:" + dependency + "]\n";
340 // ", p:" + predecessors + ", d:" + dependency + "]\n";
344 private class BetweennessComparator implements Comparator<V>
346 public int compare(V v1, V v2)
348 return vertex_data.get(v1).distance > vertex_data.get(v2).distance ? 1 : -1;