Line | Hits | Source |
---|---|---|
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 | */ | |
58 | 2 | public BetweennessCentrality(Graph g) { |
59 | 2 | initialize(g, true, true); |
60 | 2 | } |
61 | ||
62 | 5 | public BetweennessCentrality(Graph g, boolean rankNodes) { |
63 | 5 | initialize(g, rankNodes, true); |
64 | 5 | } |
65 | ||
66 | public BetweennessCentrality(Graph g, boolean rankNodes, boolean rankEdges) | |
67 | 0 | { |
68 | 0 | initialize(g, rankNodes, rankEdges); |
69 | 0 | } |
70 | ||
71 | protected void computeBetweenness(Graph graph) { | |
72 | ||
73 | 7 | BetweennessDataDecorator decorator = new BetweennessDataDecorator(); |
74 | 7 | NumericDecorator bcDecorator = new NumericDecorator(CENTRALITY, UserData.SHARED); |
75 | ||
76 | ||
77 | 7 | Set vertices = graph.getVertices(); |
78 | ||
79 | // clean up previous decorations, if any; otherwise the new calculations will | |
80 | // incorporate the old data | |
81 | 7 | UserDataUtils.cleanup(vertices, getRankScoreKey()); |
82 | 7 | UserDataUtils.cleanup(graph.getEdges(), getRankScoreKey()); |
83 | ||
84 | 7 | for (Iterator vIt = vertices.iterator(); vIt.hasNext();) { |
85 | 62 | Vertex s = (Vertex) vIt.next(); |
86 | ||
87 | 62 | initializeData(graph,decorator); |
88 | ||
89 | 62 | decorator.data(s).numSPs = 1; |
90 | 62 | decorator.data(s).distance = 0; |
91 | ||
92 | 62 | Stack stack = new Stack(); |
93 | 62 | Buffer queue = new UnboundedFifoBuffer(); |
94 | 62 | queue.add(s); |
95 | ||
96 | 420 | while (!queue.isEmpty()) { |
97 | 358 | Vertex v = (Vertex) queue.remove(); |
98 | 358 | stack.push(v); |
99 | ||
100 | 358 | for (Iterator nIt = v.getSuccessors().iterator(); nIt.hasNext();) { |
101 | 780 | Vertex w = (Vertex) nIt.next(); |
102 | ||
103 | 780 | if (decorator.data(w).distance < 0) { |
104 | 296 | queue.add(w); |
105 | 296 | decorator.data(w).distance = decorator.data(v).distance + 1; |
106 | } | |
107 | ||
108 | 780 | if (decorator.data(w).distance == decorator.data(v).distance + 1) { |
109 | 327 | decorator.data(w).numSPs += decorator.data(v).numSPs; |
110 | 327 | decorator.data(w).predecessors.add(v); |
111 | } | |
112 | } | |
113 | } | |
114 | ||
115 | 420 | while (!stack.isEmpty()) { |
116 | 358 | Vertex w = (Vertex) stack.pop(); |
117 | ||
118 | 358 | for (Iterator v2It = decorator.data(w).predecessors.iterator(); v2It.hasNext();) { |
119 | 327 | Vertex v = (Vertex) v2It.next(); |
120 | 327 | double partialDependency = (decorator.data(v).numSPs / decorator.data(w).numSPs); |
121 | 327 | partialDependency *= (1.0 + decorator.data(w).dependency); |
122 | 327 | decorator.data(v).dependency += partialDependency; |
123 | 327 | Edge currentEdge = v.findEdge(w); |
124 | 327 | MutableDouble edgeValue = (MutableDouble) bcDecorator.getValue(currentEdge); |
125 | 327 | edgeValue.add(partialDependency); |
126 | } | |
127 | 358 | if (w != s) { |
128 | 296 | MutableDouble bcValue = (MutableDouble) bcDecorator.getValue(w); |
129 | 296 | bcValue.add(decorator.data(w).dependency); |
130 | } | |
131 | } | |
132 | } | |
133 | ||
134 | 7 | if (PredicateUtils.enforcesEdgeConstraint(graph, Graph.UNDIRECTED_EDGE)) { |
135 | 3 | for (Iterator v3It = vertices.iterator(); v3It.hasNext();) { |
136 | 27 | MutableDouble bcValue = (MutableDouble) bcDecorator.getValue((Vertex) v3It.next()); |
137 | 27 | bcValue.setDoubleValue(bcValue.doubleValue() / 2.0); |
138 | } | |
139 | 3 | for (Iterator eIt = graph.getEdges().iterator(); eIt.hasNext();) { |
140 | 23 | MutableDouble bcValue = (MutableDouble) bcDecorator.getValue((Edge) eIt.next()); |
141 | 23 | bcValue.setDoubleValue(bcValue.doubleValue() / 2.0); |
142 | } | |
143 | } | |
144 | ||
145 | 7 | for (Iterator vIt = vertices.iterator(); vIt.hasNext();) { |
146 | 62 | Vertex vertex = (Vertex) vIt.next(); |
147 | 62 | decorator.removeValue(vertex); |
148 | } | |
149 | ||
150 | 7 | } |
151 | ||
152 | private void initializeData(Graph g, BetweennessDataDecorator decorator) { | |
153 | 62 | for (Iterator vIt = g.getVertices().iterator(); vIt.hasNext();) { |
154 | 568 | Vertex vertex = (Vertex) vIt.next(); |
155 | ||
156 | 568 | if (vertex.getUserDatum(CENTRALITY) == null) { |
157 | 62 | vertex.addUserDatum(CENTRALITY, new MutableDouble(), UserData.SHARED); |
158 | } | |
159 | ||
160 | 568 | decorator.setData(new BetweennessData(), vertex); |
161 | } | |
162 | 62 | for (Iterator eIt = g.getEdges().iterator(); eIt.hasNext();) { |
163 | 557 | Edge e = (Edge) eIt.next(); |
164 | ||
165 | 557 | if (e.getUserDatum(CENTRALITY) == null) { |
166 | 60 | e.addUserDatum(CENTRALITY, new MutableDouble(), UserData.SHARED); |
167 | } | |
168 | } | |
169 | 62 | } |
170 | ||
171 | /** | |
172 | * the user datum key used to store the rank scores | |
173 | * @return the key | |
174 | */ | |
175 | public String getRankScoreKey() { | |
176 | 167 | return CENTRALITY; |
177 | } | |
178 | ||
179 | protected double evaluateIteration() { | |
180 | 7 | computeBetweenness(getGraph()); |
181 | 7 | 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 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |