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

   1 /*
   2 * Copyright (c) 2003, 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 */
  10 package edu.uci.ics.jung.algorithms.importance;
  11
  12 import java.util.ArrayList;
  13 import java.util.Collection;
  14 import java.util.HashMap;
  15 import java.util.List;
  16 import java.util.Map;
  17 import java.util.Stack;
  18
  19 import org.apache.commons.collections15.Buffer;
  20 import org.apache.commons.collections15.buffer.UnboundedFifoBuffer;
  21
  22 import edu.uci.ics.jung.graph.Graph;
  23 import edu.uci.ics.jung.graph.UndirectedGraph;
  24
  25 /**
  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>
  30  *
  31  * A simple example of usage is:
  32  * <pre>
  33  * BetweennessCentrality ranker = new BetweennessCentrality(someGraph);
  34  * ranker.evaluate();
  35  * ranker.printRankings();
  36  * </pre>
  37  *
  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."
  40  * @author Scott White
  41  * @author Tom Nelson converted to jung2
  42  */
  43
  44 public class BetweennessCentrality<V,E> extends AbstractRanker<V,E> {
  45
  46     public static final String CENTRALITY = "centrality.BetweennessCentrality";
  47
  48     /**
  49      * Constructor which initializes the algorithm
  50      * @param g the graph whose nodes are to be analyzed
  51      */
  52     public BetweennessCentrality(Graph<V,E> g) {
  53         initialize(g, true, true);
  54     }
  55
  56     public BetweennessCentrality(Graph<V,E> g, boolean rankNodes) {
  57         initialize(g, rankNodes, true);
  58     }
  59
  60     public BetweennessCentrality(Graph<V,E> g, boolean rankNodes, boolean rankEdges)
  61     {
  62         initialize(g, rankNodes, rankEdges);
  63     }
  64
  65         protected void computeBetweenness(Graph<V,E> graph) {
  66
  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();
  74
  75         Collection<V> vertices = graph.getVertices();
  76
  77         for (V s : vertices) {
  78
  79             initializeData(graph,decorator);
  80
  81             decorator.get(s).numSPs = 1;
  82             decorator.get(s).distance = 0;
  83
  84             Stack<V> stack = new Stack<V>();
  85             Buffer<V> queue = new UnboundedFifoBuffer<V>();
  86             queue.add(s);
  87
  88             while (!queue.isEmpty()) {
  89                 V v = queue.remove();
  90                 stack.push(v);
  91
  92                 for(V w : getGraph().getSuccessors(v)) {
  93
  94                     if (decorator.get(w).distance < 0) {
  95                         queue.add(w);
  96                         decorator.get(w).distance = decorator.get(v).distance + 1;
  97                     }
  98
  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);
 102                     }
 103                 }
 104             }
 105
 106             while (!stack.isEmpty()) {
 107                 V w = stack.pop();
 108
 109                 for (V v : decorator.get(w).predecessors) {
 110
 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);
 118                 }
 119                 if (w != s) {
 120                         double bcValue = bcVertexDecorator.get(w).doubleValue();
 121                         bcValue += decorator.get(w).dependency;
 122                         bcVertexDecorator.put(w, bcValue);
 123                 }
 124             }
 125         }
 126
 127         if(graph instanceof UndirectedGraph) {
 128             for (V v : vertices) {
 129                 double bcValue = bcVertexDecorator.get(v).doubleValue();
 130                 bcValue /= 2.0;
 131                 bcVertexDecorator.put(v, bcValue);
 132             }
 133             for (E e : graph.getEdges()) {
 134                 double bcValue = bcEdgeDecorator.get(e).doubleValue();
 135                 bcValue /= 2.0;
 136                 bcEdgeDecorator.put(e, bcValue);
 137             }
 138         }
 139
 140         for (V vertex : vertices) {
 141             decorator.remove(vertex);
 142         }
 143     }
 144
 145     private void initializeData(Graph<V,E> g, Map<V,BetweennessData> decorator) {
 146         for (V vertex : g.getVertices()) {
 147
 148                 Map<V,Number> bcVertexDecorator = vertexRankScores.get(getRankScoreKey());
 149                 if(bcVertexDecorator.containsKey(vertex) == false) {
 150                         bcVertexDecorator.put(vertex, 0.0);
 151                 }
 152             decorator.put(vertex, new BetweennessData());
 153         }
 154         for (E e : g.getEdges()) {
 155
 156                 Map<E,Number> bcEdgeDecorator = edgeRankScores.get(getRankScoreKey());
 157                 if(bcEdgeDecorator.containsKey(e) == false) {
 158                         bcEdgeDecorator.put(e, 0.0);
 159                 }
 160         }
 161     }
 162
 163     /**
 164      * the user datum key used to store the rank scores
 165      * @return the key
 166      */
 167     @Override
 168     public String getRankScoreKey() {
 169         return CENTRALITY;
 170     }
 171
 172     @Override
 173     public void step() {
 174         computeBetweenness(getGraph());
 175     }
 176
 177     class BetweennessData {
 178         double distance;
 179         double numSPs;
 180         List<V> predecessors;
 181         double dependency;
 182
 183         BetweennessData() {
 184             distance = -1;
 185             numSPs = 0;
 186             predecessors = new ArrayList<V>();
 187             dependency = 0;
 188         }
 189     }
 190 }