third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/BetweennessCentrality.java

   1 /**
   2  * Copyright (c) 2008, the JUNG Project and the Regents of the University
   3  * of California
   4  * All rights reserved.
   5  *
   6  * This software is open-source under the BSD license; see either
   7  * "license.txt" or
   8  * http://jung.sourceforge.net/license.txt for a description.
   9  * Created on Sep 16, 2008
  10  *
  11  */
  12 package edu.uci.ics.jung.algorithms.scoring;
  13
  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;
  19 import java.util.Map;
  20 import java.util.Queue;
  21 import java.util.Stack;
  22
  23 import org.apache.commons.collections15.Transformer;
  24 import org.apache.commons.collections15.functors.ConstantTransformer;
  25
  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;
  29
  30 /**
  31  * Computes betweenness centrality for each vertex and edge in the graph.
  32  *
  33  * @see "Ulrik Brandes: A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25(2):163-177, 2001."
  34  */
  35 public class BetweennessCentrality<V, E>
  36         implements VertexScorer<V, Double>, EdgeScorer<E, Double>
  37 {
  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;
  42
  43         /**
  44          * Calculates betweenness scores based on the all-pairs unweighted shortest paths
  45          * in the graph.
  46          * @param graph the graph for which the scores are to be calculated
  47          */
  48         @SuppressWarnings("unchecked")
  49         public BetweennessCentrality(Graph<V, E> graph)
  50         {
  51                 initialize(graph);
  52                 computeBetweenness(new LinkedList<V>(), new ConstantTransformer(1));
  53         }
  54
  55         /**
  56          * Calculates betweenness scores based on the all-pairs weighted shortest paths in the
  57          * graph.
  58          *
  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
  63          */
  64         public BetweennessCentrality(Graph<V, E> graph,
  65                         Transformer<E, ? extends Number> edge_weights)
  66         {
  67                 // reject negative-weight edges up front
  68                 for (E e : graph.getEdges())
  69                 {
  70                         double e_weight = edge_weights.transform(e).doubleValue();
  71                 if (e_weight < 0)
  72                         throw new IllegalArgumentException(String.format(
  73                                         "Weight for edge '%s' is < 0: %d", e, e_weight));
  74                 }
  75
  76                 initialize(graph);
  77                 computeBetweenness(new MapBinaryHeap<V>(new BetweennessComparator()),
  78                         edge_weights);
  79         }
  80
  81         protected void initialize(Graph<V,E> graph)
  82         {
  83                 this.graph = 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>();
  87
  88                 for (V v : graph.getVertices())
  89                         this.vertex_scores.put(v, 0.0);
  90
  91                 for (E e : graph.getEdges())
  92                         this.edge_scores.put(e, 0.0);
  93         }
  94
  95         protected void computeBetweenness(Queue<V> queue,
  96                         Transformer<E, ? extends Number> edge_weights)
  97         {
  98                 for (V v : graph.getVertices())
  99                 {
 100                         // initialize the betweenness data for this new vertex
 101                         for (V s : graph.getVertices())
 102                                 this.vertex_data.put(s, new BetweennessData());
 103
 104 //                      if (v.equals(new Integer(0)))
 105 //                              System.out.println("pause");
 106
 107             vertex_data.get(v).numSPs = 1;
 108             vertex_data.get(v).distance = 0;
 109
 110             Stack<V> stack = new Stack<V>();
 111 //            Buffer<V> queue = new UnboundedFifoBuffer<V>();
 112 //            queue.add(v);
 113             queue.offer(v);
 114
 115             while (!queue.isEmpty())
 116             {
 117 //                V w = queue.remove();
 118                 V w = queue.poll();
 119                 stack.push(w);
 120                 BetweennessData w_data = vertex_data.get(w);
 121
 122                 for (E e : graph.getOutEdges(w))
 123                 {
 124                         // TODO (jrtom): change this to getOtherVertices(w, e)
 125                         V x = graph.getOpposite(w, e);
 126                         if (x.equals(w))
 127                                 continue;
 128                         double wx_weight = edge_weights.transform(e).doubleValue();
 129
 130
 131 //                for(V x : graph.getSuccessors(w))
 132 //                {
 133 //                      if (x.equals(w))
 134 //                              continue;
 135
 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.
 140
 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
 149                         //   update 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
 154
 155                         BetweennessData x_data = vertex_data.get(x);
 156                         double x_potential_dist = w_data.distance + wx_weight;
 157
 158                     if (x_data.distance < 0)
 159                     {
 160 //                        queue.add(x);
 161 //                        vertex_data.get(x).distance = vertex_data.get(w).distance + 1;
 162                         x_data.distance = x_potential_dist;
 163                         queue.offer(x);
 164                     }
 165
 166                     // note:
 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)
 170                     {
 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);
 177                     }
 178 //                  if (vertex_data.get(x).distance == vertex_data.get(w).distance + 1)
 179                     //
 180 //                    if (x_data.distance == x_potential_dist)
 181 //                    {
 182 //                        x_data.numSPs += w_data.numSPs;
 183 ////                        vertex_data.get(x).predecessors.add(w);
 184 //                        x_data.incomingEdges.add(e);
 185 //                    }
 186                 }
 187                 for (E e: graph.getOutEdges(w))
 188                 {
 189                         V x = graph.getOpposite(w, e);
 190                         if (x.equals(w))
 191                                 continue;
 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)
 196                     {
 197                         x_data.numSPs += w_data.numSPs;
 198 //                        vertex_data.get(x).predecessors.add(w);
 199                         x_data.incomingEdges.add(e);
 200                     }
 201                 }
 202             }
 203                 while (!stack.isEmpty())
 204                 {
 205                     V x = stack.pop();
 206
 207 //                  for (V w : vertex_data.get(x).predecessors)
 208                     for (E e : vertex_data.get(x).incomingEdges)
 209                     {
 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);
 221                     }
 222                     if (!x.equals(v))
 223                     {
 224                         double x_score = vertex_scores.get(x).doubleValue();
 225                         x_score += vertex_data.get(x).dependency;
 226                         vertex_scores.put(x, x_score);
 227                     }
 228                 }
 229         }
 230
 231         if(graph instanceof UndirectedGraph)
 232         {
 233                 for (V v : graph.getVertices()) {
 234                         double v_score = vertex_scores.get(v).doubleValue();
 235                         v_score /= 2.0;
 236                         vertex_scores.put(v, v_score);
 237                 }
 238                 for (E e : graph.getEdges()) {
 239                         double e_score = edge_scores.get(e).doubleValue();
 240                         e_score /= 2.0;
 241                         edge_scores.put(e, e_score);
 242                 }
 243         }
 244
 245         vertex_data.clear();
 246         }
 247
 248 //      protected void computeWeightedBetweenness(Transformer<E, ? extends Number> edge_weights)
 249 //      {
 250 //              for (V v : graph.getVertices())
 251 //              {
 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;
 257 //
 258 //            Stack<V> stack = new Stack<V>();
 259 ////            Buffer<V> queue = new UnboundedFifoBuffer<V>();
 260 //            SortedSet<V> pqueue = new TreeSet<V>(new BetweennessComparator());
 261 ////          queue.add(v);
 262 //            pqueue.add(v);
 263 //
 264 ////            while (!queue.isEmpty())
 265 //            while (!pqueue.isEmpty())
 266 //            {
 267 ////              V w = queue.remove();
 268 //              V w = pqueue.first();
 269 //              pqueue.remove(w);
 270 //                stack.push(w);
 271 //
 272 ////                for(V x : graph.getSuccessors(w))
 273 //                for (E e : graph.getOutEdges(w))
 274 //                {
 275 //                      // TODO (jrtom): change this to getOtherVertices(w, e)
 276 //                      V x = graph.getOpposite(w, e);
 277 //                      if (x.equals(w))
 278 //                              continue;
 279 //                      double e_weight = edge_weights.transform(e).doubleValue();
 280 //
 281 //                    if (vertex_data.get(x).distance < 0)
 282 //                    {
 283 ////                        queue.add(x);
 284 //                      pqueue.add(v);
 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;
 288 //                    }
 289 //
 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)
 293 //                    {
 294 //                        vertex_data.get(x).numSPs += vertex_data.get(w).numSPs;
 295 //                        vertex_data.get(x).predecessors.add(w);
 296 //                    }
 297 //                }
 298 //            }
 299 //            updateScores(v, stack);
 300 //        }
 301 //
 302 //        if(graph instanceof UndirectedGraph)
 303 //            adjustUndirectedScores();
 304 //
 305 //        vertex_data.clear();
 306 //      }
 307
 308         public Double getVertexScore(V v)
 309         {
 310                 return vertex_scores.get(v);
 311         }
 312
 313         public Double getEdgeScore(E e)
 314         {
 315                 return edge_scores.get(e);
 316         }
 317
 318     private class BetweennessData
 319     {
 320         double distance;
 321         double numSPs;
 322 //        List<V> predecessors;
 323         List<E> incomingEdges;
 324         double dependency;
 325
 326         BetweennessData()
 327         {
 328             distance = -1;
 329             numSPs = 0;
 330 //            predecessors = new ArrayList<V>();
 331             incomingEdges = new ArrayList<E>();
 332             dependency = 0;
 333         }
 334
 335         @Override
 336         public String toString()
 337         {
 338                 return "[d:" + distance + ", sp:" + numSPs +
 339                         ", p:" + incomingEdges + ", d:" + dependency + "]\n";
 340 //                      ", p:" + predecessors + ", d:" + dependency + "]\n";
 341         }
 342     }
 343
 344     private class BetweennessComparator implements Comparator<V>
 345     {
 346                 public int compare(V v1, V v2)
 347                 {
 348                         return vertex_data.get(v1).distance > vertex_data.get(v2).distance ? 1 : -1;
 349                 }
 350     }
 351 }