jcoverage | summary | package | file

Coverage details for edu.uci.ics.jung.algorithms.importance.BetweennessCentrality

LineHitsSource
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.Iterator;
14 import java.util.List;
15 import java.util.Set;
16 import java.util.Stack;
17  
18 import org.apache.commons.collections.Buffer;
19 import org.apache.commons.collections.buffer.UnboundedFifoBuffer;
20  
21 import edu.uci.ics.jung.graph.Edge;
22 import edu.uci.ics.jung.graph.Element;
23 import edu.uci.ics.jung.graph.Graph;
24 import edu.uci.ics.jung.graph.Vertex;
25 import edu.uci.ics.jung.graph.decorators.Decorator;
26 import edu.uci.ics.jung.graph.decorators.NumericDecorator;
27 import edu.uci.ics.jung.utils.MutableDouble;
28 import edu.uci.ics.jung.utils.PredicateUtils;
29 import edu.uci.ics.jung.utils.UserData;
30 import edu.uci.ics.jung.utils.UserDataUtils;
31  
32 /**
33  * Computes betweenness centrality for each vertex and edge in the graph. The result is that each vertex
34  * and edge has a UserData element of type MutableDouble whose key is 'centrality.BetweennessCentrality'.
35  * Note: Many social network researchers like to normalize the betweenness values by dividing the values by
36  * (n-1)(n-2)/2. The values given here are unnormalized.<p>
37  *
38  * A simple example of usage is:
39  * <pre>
40  * BetweennessCentrality ranker = new BetweennessCentrality(someGraph);
41  * ranker.evaluate();
42  * ranker.printRankings();
43  * </pre>
44  *
45  * Running time is: O(n^2 + nm).
46  * @see "Ulrik Brandes: A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25(2):163-177, 2001."
47  * @author Scott White
48  */
49  
50 public class BetweennessCentrality extends AbstractRanker {
51  
52     public static final String CENTRALITY = "centrality.BetweennessCentrality";
53  
54     /**
55      * Constructor which initializes the algorithm
56      * @param g the graph whose nodes are to be analyzed
57      */
582    public BetweennessCentrality(Graph g) {
592        initialize(g, true, true);
602    }
61  
625    public BetweennessCentrality(Graph g, boolean rankNodes) {
635        initialize(g, rankNodes, true);
645    }
65  
66     public BetweennessCentrality(Graph g, boolean rankNodes, boolean rankEdges)
670    {
680        initialize(g, rankNodes, rankEdges);
690    }
70     
71     protected void computeBetweenness(Graph graph) {
72  
737        BetweennessDataDecorator decorator = new BetweennessDataDecorator();
747        NumericDecorator bcDecorator = new NumericDecorator(CENTRALITY, UserData.SHARED);
75  
76         
777        Set vertices = graph.getVertices();
78         
79         // clean up previous decorations, if any; otherwise the new calculations will
80         // incorporate the old data
817        UserDataUtils.cleanup(vertices, getRankScoreKey());
827        UserDataUtils.cleanup(graph.getEdges(), getRankScoreKey());
83  
847        for (Iterator vIt = vertices.iterator(); vIt.hasNext();) {
8562            Vertex s = (Vertex) vIt.next();
86  
8762            initializeData(graph,decorator);
88  
8962            decorator.data(s).numSPs = 1;
9062            decorator.data(s).distance = 0;
91  
9262            Stack stack = new Stack();
9362            Buffer queue = new UnboundedFifoBuffer();
9462            queue.add(s);
95  
96420            while (!queue.isEmpty()) {
97358                Vertex v = (Vertex) queue.remove();
98358                stack.push(v);
99  
100358                for (Iterator nIt = v.getSuccessors().iterator(); nIt.hasNext();) {
101780                    Vertex w = (Vertex) nIt.next();
102  
103780                    if (decorator.data(w).distance < 0) {
104296                        queue.add(w);
105296                        decorator.data(w).distance = decorator.data(v).distance + 1;
106                     }
107  
108780                    if (decorator.data(w).distance == decorator.data(v).distance + 1) {
109327                        decorator.data(w).numSPs += decorator.data(v).numSPs;
110327                        decorator.data(w).predecessors.add(v);
111                     }
112                 }
113             }
114  
115420            while (!stack.isEmpty()) {
116358                Vertex w = (Vertex) stack.pop();
117  
118358                for (Iterator v2It = decorator.data(w).predecessors.iterator(); v2It.hasNext();) {
119327                    Vertex v = (Vertex) v2It.next();
120327                    double partialDependency = (decorator.data(v).numSPs / decorator.data(w).numSPs);
121327                    partialDependency *= (1.0 + decorator.data(w).dependency);
122327                    decorator.data(v).dependency += partialDependency;
123327                    Edge currentEdge = v.findEdge(w);
124327                    MutableDouble edgeValue = (MutableDouble) bcDecorator.getValue(currentEdge);
125327                    edgeValue.add(partialDependency);
126                 }
127358                if (w != s) {
128296                    MutableDouble bcValue = (MutableDouble) bcDecorator.getValue(w);
129296                    bcValue.add(decorator.data(w).dependency);
130                 }
131             }
132         }
133  
1347        if (PredicateUtils.enforcesEdgeConstraint(graph, Graph.UNDIRECTED_EDGE)) {
1353            for (Iterator v3It = vertices.iterator(); v3It.hasNext();) {
13627                MutableDouble bcValue = (MutableDouble) bcDecorator.getValue((Vertex) v3It.next());
13727                bcValue.setDoubleValue(bcValue.doubleValue() / 2.0);
138             }
1393            for (Iterator eIt = graph.getEdges().iterator(); eIt.hasNext();) {
14023                MutableDouble bcValue = (MutableDouble) bcDecorator.getValue((Edge) eIt.next());
14123                bcValue.setDoubleValue(bcValue.doubleValue() / 2.0);
142             }
143         }
144  
1457        for (Iterator vIt = vertices.iterator(); vIt.hasNext();) {
14662            Vertex vertex = (Vertex) vIt.next();
14762            decorator.removeValue(vertex);
148         }
149  
1507    }
151  
152     private void initializeData(Graph g, BetweennessDataDecorator decorator) {
15362        for (Iterator vIt = g.getVertices().iterator(); vIt.hasNext();) {
154568            Vertex vertex = (Vertex) vIt.next();
155  
156568            if (vertex.getUserDatum(CENTRALITY) == null) {
15762                vertex.addUserDatum(CENTRALITY, new MutableDouble(), UserData.SHARED);
158             }
159  
160568            decorator.setData(new BetweennessData(), vertex);
161         }
16262        for (Iterator eIt = g.getEdges().iterator(); eIt.hasNext();) {
163557            Edge e = (Edge) eIt.next();
164  
165557            if (e.getUserDatum(CENTRALITY) == null) {
16660                e.addUserDatum(CENTRALITY, new MutableDouble(), UserData.SHARED);
167             }
168         }
16962    }
170  
171     /**
172      * the user datum key used to store the rank scores
173      * @return the key
174      */
175     public String getRankScoreKey() {
176167        return CENTRALITY;
177     }
178  
179     protected double evaluateIteration() {
1807        computeBetweenness(getGraph());
1817        return 0;
182     }
183  
184     class BetweennessDataDecorator extends Decorator {
185         public BetweennessDataDecorator() {
186             super("centrality.BetwennessData", UserData.REMOVE);
187         }
188  
189         public BetweennessData data(Element udc) {
190             return (BetweennessData) udc.getUserDatum(getKey());
191         }
192  
193         public void setData(BetweennessData value, Element udc) {
194             udc.setUserDatum(getKey(), value, getCopyAction());
195         }
196  
197     }
198  
199     class BetweennessData {
200         double distance;
201         double numSPs;
202         List predecessors;
203         double dependency;
204  
205         BetweennessData() {
206             distance = -1;
207             numSPs = 0;
208             predecessors = new ArrayList();
209             dependency = 0;
210         }
211     }
212 }

jcoverage | summary | package | file

this report was generated by version 1.0.5 of jcoverage.
visit www.jcoverage.com for updates.

copyright © 2003, jcoverage ltd. all rights reserved.
Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.