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.HashMap; | |
13 | import java.util.HashSet; | |
14 | import java.util.Iterator; | |
15 | import java.util.Map; | |
16 | import java.util.Set; | |
17 | ||
18 | import edu.uci.ics.jung.algorithms.cluster.ClusterSet; | |
19 | import edu.uci.ics.jung.algorithms.cluster.WeakComponentClusterer; | |
20 | import edu.uci.ics.jung.graph.Edge; | |
21 | import edu.uci.ics.jung.graph.Element; | |
22 | import edu.uci.ics.jung.graph.Graph; | |
23 | import edu.uci.ics.jung.graph.Vertex; | |
24 | import edu.uci.ics.jung.utils.MutableDouble; | |
25 | import edu.uci.ics.jung.utils.NumericalPrecision; | |
26 | import edu.uci.ics.jung.utils.UserData; | |
27 | ||
28 | /** | |
29 | * Algorithm that extends the HITS algorithm by incorporating root nodes (priors). Whereas in HITS | |
30 | * the importance of a node is implicitly computed relative to all nodes in the graph, now importance | |
31 | * is computed relative to the specified root nodes. | |
32 | * <p> | |
33 | * A simple example of usage is: | |
34 | * <pre> | |
35 | * HITSWithPriors ranker = new HITSWithPriors(someGraph,0.3,rootSet); | |
36 | * ranker.evaluate(); | |
37 | * ranker.printRankings(); | |
38 | * </pre> | |
39 | * <p> | |
40 | * Running time: O(|V|*I) where |V| is the number of vertices and I is the number of iterations until convergence | |
41 | * | |
42 | * @author Scott White | |
43 | * @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003" | |
44 | */ | |
45 | public class HITSWithPriors extends RelativeAuthorityRanker { | |
46 | protected static final String AUTHORITY_KEY = "jung.algorithms.importance.AUTHORITY"; | |
47 | protected static final String HUB_KEY = "jung.algorithms.importance.HUB"; | |
48 | private static final String IN_EDGE_WEIGHT = "IN_EDGE_WEIGHT"; | |
49 | private String mKeyToUseForRanking; | |
50 | private Map mPreviousAuthorityScores; | |
51 | private Map mPreviousHubScores; | |
52 | private double mBeta; | |
53 | Set mReachableVertices; | |
54 | private Set mLeafNodes; | |
55 | ||
56 | /** | |
57 | * Constructs an instance of the ranker where the type of importance that is associated with the | |
58 | * rank score is the node's importance as an authority. | |
59 | * @param graph the graph whose nodes are to be ranked | |
60 | * @param bias the weight that should be placed on the root nodes (between 0 and 1) | |
61 | * @param priors the set of root nodes | |
62 | */ | |
63 | 0 | public HITSWithPriors(Graph graph, double bias, Set priors) { |
64 | 0 | mKeyToUseForRanking = AUTHORITY_KEY; |
65 | 0 | mBeta = bias; |
66 | 0 | setPriors(priors); |
67 | 0 | initialize(graph, null); |
68 | 0 | } |
69 | ||
70 | /** | |
71 | * More specialized constructor where the type of importance can be specified. | |
72 | * @param graph the graph whose nodes are to be ranked | |
73 | * @param useAuthorityForRanking | |
74 | * @param bias the weight that should be placed on the root nodes (between 0 and 1) | |
75 | * @param priors the set of root nodes | |
76 | */ | |
77 | 2 | public HITSWithPriors(Graph graph, boolean useAuthorityForRanking, double bias, Set priors, String edgeWeightKey) { |
78 | 2 | setUseAuthorityForRanking(useAuthorityForRanking); |
79 | 2 | mBeta = bias; |
80 | 2 | setPriors(priors); |
81 | 2 | initialize(graph, edgeWeightKey); |
82 | 2 | } |
83 | ||
84 | protected void initialize(Graph g, String edgeWeightKeyName) { | |
85 | ||
86 | 2 | super.initialize(g, true, false); |
87 | ||
88 | 2 | mPreviousAuthorityScores = new HashMap(); |
89 | 2 | mPreviousHubScores = new HashMap(); |
90 | ||
91 | ||
92 | // int numVertices = getVertices().size(); | |
93 | 2 | for (Iterator vIt = g.getVertices().iterator(); vIt.hasNext();) { |
94 | 8 | Vertex currentVertex = (Vertex) vIt.next(); |
95 | ||
96 | 8 | mPreviousAuthorityScores.put(currentVertex, new MutableDouble(0)); |
97 | 8 | mPreviousHubScores.put(currentVertex, new MutableDouble(0)); |
98 | ||
99 | 8 | setRankScore(currentVertex, 0, AUTHORITY_KEY); |
100 | 8 | setRankScore(currentVertex, 0, HUB_KEY); |
101 | ||
102 | 8 | setPriorRankScore(currentVertex, 0); |
103 | } | |
104 | ||
105 | 2 | WeakComponentClusterer wcExtractor = new WeakComponentClusterer(); |
106 | 2 | ClusterSet clusters = wcExtractor.extract(g); |
107 | 2 | mReachableVertices = new HashSet(); |
108 | ||
109 | 2 | double numPriors = getPriors().size(); |
110 | 2 | for (Iterator it = getPriors().iterator(); it.hasNext();) { |
111 | 2 | Vertex currentVertex = (Vertex) it.next(); |
112 | 2 | setPriorRankScore(currentVertex, 1.0 / numPriors); |
113 | 2 | for (Iterator cIt = clusters.iterator(); cIt.hasNext();) { |
114 | 2 | Set members = (Set) cIt.next(); |
115 | 2 | if (members.contains(currentVertex)) { |
116 | 2 | mReachableVertices.addAll(members); |
117 | } | |
118 | } | |
119 | } | |
120 | ||
121 | 2 | mLeafNodes = new HashSet(); |
122 | 2 | int numReachableVertices = mReachableVertices.size(); |
123 | 2 | for (Iterator vIt = mReachableVertices.iterator(); vIt.hasNext();) { |
124 | 8 | Vertex currentVertex = (Vertex) vIt.next(); |
125 | 8 | setRankScore(currentVertex, 1.0 / numReachableVertices, AUTHORITY_KEY); |
126 | 8 | setRankScore(currentVertex, 1.0 / numReachableVertices, HUB_KEY); |
127 | 8 | if (currentVertex.outDegree() == 0) { |
128 | 0 | mLeafNodes.add(currentVertex); |
129 | } | |
130 | } | |
131 | ||
132 | 2 | if (edgeWeightKeyName == null) { |
133 | 2 | assignDefaultEdgeTransitionWeights(); |
134 | } else { | |
135 | 0 | setUserDefinedEdgeWeightKey(edgeWeightKeyName); |
136 | 0 | normalizeEdgeTransitionWeights(); |
137 | } | |
138 | 2 | assignInlinkEdgeTransitionWeights(); |
139 | ||
140 | 2 | } |
141 | ||
142 | protected void finalizeIterations() { | |
143 | 2 | super.finalizeIterations(); |
144 | 2 | for (Iterator it = getVertices().iterator(); it.hasNext();) { |
145 | 8 | Vertex currentVertex = (Vertex) it.next(); |
146 | 8 | if (mKeyToUseForRanking.equals(AUTHORITY_KEY)) { |
147 | 4 | currentVertex.removeUserDatum(HUB_KEY); |
148 | } else { | |
149 | 4 | currentVertex.removeUserDatum(AUTHORITY_KEY); |
150 | } | |
151 | } | |
152 | ||
153 | 2 | } |
154 | ||
155 | protected double getInEdgeWeight(Edge e) { | |
156 | 250 | MutableDouble value = (MutableDouble) e.getUserDatum(IN_EDGE_WEIGHT); |
157 | 250 | return value.doubleValue(); |
158 | } | |
159 | ||
160 | protected void setInEdgeWeight(Edge e, double weight) { | |
161 | 10 | MutableDouble value = (MutableDouble) e.getUserDatum(IN_EDGE_WEIGHT); |
162 | 10 | if (value == null) { |
163 | 10 | e.setUserDatum(IN_EDGE_WEIGHT, new MutableDouble(weight), UserData.SHARED); |
164 | } else { | |
165 | 0 | value.setDoubleValue(weight); |
166 | } | |
167 | 10 | } |
168 | ||
169 | private void assignInlinkEdgeTransitionWeights() { | |
170 | ||
171 | 2 | for (Iterator vIt = getVertices().iterator(); vIt.hasNext();) { |
172 | 8 | Vertex currentVertex = (Vertex) vIt.next(); |
173 | ||
174 | // Set incomingEdges = null; | |
175 | // if (getGraph().isDirected()) { | |
176 | // incomingEdges = currentVertex.getInEdges(); | |
177 | // } else { | |
178 | // incomingEdges = currentVertex.getIncidentEdges(); | |
179 | // } | |
180 | 8 | Set incomingEdges = currentVertex.getInEdges(); |
181 | ||
182 | 8 | double total = 0; |
183 | 8 | for (Iterator edgeIt = incomingEdges.iterator(); edgeIt.hasNext();) { |
184 | 10 | Edge currentEdge = (Edge) edgeIt.next(); |
185 | 10 | total += getEdgeWeight(currentEdge); |
186 | } | |
187 | ||
188 | 8 | for (Iterator edgeIt = incomingEdges.iterator(); edgeIt.hasNext();) { |
189 | 10 | Edge currentEdge = (Edge) edgeIt.next(); |
190 | 10 | double weight = getEdgeWeight(currentEdge); |
191 | 10 | setInEdgeWeight(currentEdge, weight / total); |
192 | } | |
193 | } | |
194 | 2 | } |
195 | ||
196 | ||
197 | /** | |
198 | * the user datum key used to store the rank scores | |
199 | * @return the key | |
200 | */ | |
201 | public String getRankScoreKey() { | |
202 | 0 | return mKeyToUseForRanking; |
203 | } | |
204 | ||
205 | /** | |
206 | * Given a node, returns the corresponding rank score. This implementation of <code>getRankScore</code> assumes | |
207 | * the decoration representing the rank score is of type <code>MutableDouble</code>. | |
208 | * @return the rank score for this node | |
209 | */ | |
210 | public double getRankScore(Element v) { | |
211 | 16 | return getRankScore(v, mKeyToUseForRanking); |
212 | } | |
213 | ||
214 | /** | |
215 | * Given a node and a key, returns the corresponding rank score. Assumes the decoration representing the rank score | |
216 | * is of type <code>MutableDouble</code>. | |
217 | * @param v the node in question | |
218 | * @param key the user datum key that indexes the rank score value | |
219 | * @return the rank score for this node | |
220 | */ | |
221 | protected double getRankScore(Element v, String key) { | |
222 | 1316 | return ((MutableDouble) v.getUserDatum(key)).doubleValue(); |
223 | } | |
224 | ||
225 | protected double getPreviousAuthorityScore(Element v) { | |
226 | 200 | return ((MutableDouble) mPreviousAuthorityScores.get(v)).doubleValue(); |
227 | } | |
228 | ||
229 | protected double getPreviousHubScore(Element v) { | |
230 | 200 | return ((MutableDouble) mPreviousHubScores.get(v)).doubleValue(); |
231 | } | |
232 | ||
233 | protected void setRankScore(Element v, double rankValue, String key) { | |
234 | 432 | MutableDouble value = (MutableDouble) v.getUserDatum(key); |
235 | ||
236 | 432 | if (value == null) { |
237 | 16 | v.setUserDatum(key, new MutableDouble(rankValue), UserData.SHARED); |
238 | } else { | |
239 | 416 | value.setDoubleValue(rankValue); |
240 | } | |
241 | 432 | } |
242 | ||
243 | protected void setRankScore(Element v, double rankValue) { | |
244 | 0 | setRankScore(v, rankValue, mKeyToUseForRanking); |
245 | 0 | } |
246 | ||
247 | protected double evaluateIteration() { | |
248 | 50 | updatePreviousScores(); |
249 | ||
250 | //Perform 2 update steps | |
251 | 50 | updateAuthorityRankings(); |
252 | 50 | updateHubRankings(); |
253 | ||
254 | 50 | double hubMSE = 0; |
255 | 50 | double authorityMSE = 0; |
256 | ||
257 | //Test for convergence | |
258 | 50 | int numVertices = mReachableVertices.size(); |
259 | 50 | for (Iterator vIt = mReachableVertices.iterator(); vIt.hasNext();) { |
260 | 200 | Vertex currentVertex = (Vertex) vIt.next(); |
261 | ||
262 | 200 | double currentAuthorityScore = getRankScore(currentVertex, AUTHORITY_KEY); |
263 | 200 | double currentHubScore = getRankScore(currentVertex, HUB_KEY); |
264 | ||
265 | 200 | double previousAuthorityScore = getPreviousAuthorityScore(currentVertex); |
266 | 200 | double previousHubScore = getPreviousHubScore(currentVertex); |
267 | ||
268 | 200 | hubMSE += Math.pow(currentHubScore - previousHubScore, 2); |
269 | 200 | authorityMSE += Math.pow(currentAuthorityScore - previousAuthorityScore, 2); |
270 | } | |
271 | ||
272 | 50 | hubMSE = Math.pow(hubMSE / numVertices, 0.5); |
273 | 50 | authorityMSE = Math.pow(authorityMSE / numVertices, 0.5); |
274 | ||
275 | 50 | return hubMSE + authorityMSE; |
276 | } | |
277 | ||
278 | /** | |
279 | * If <code>evaluate()</code> has not already been called, the user can override the type of importance. | |
280 | * (hub or authority) that should be associated with the rank score. | |
281 | * @param useAuthorityForRanking if <code>true</code>, authority is used; if <code>false</code>, hub is used | |
282 | */ | |
283 | public void setUseAuthorityForRanking(boolean useAuthorityForRanking) { | |
284 | 2 | if (useAuthorityForRanking) { |
285 | 1 | mKeyToUseForRanking = AUTHORITY_KEY; |
286 | } else { | |
287 | 1 | mKeyToUseForRanking = HUB_KEY; |
288 | } | |
289 | 2 | } |
290 | ||
291 | private double computeSum(Vertex v, String key) { | |
292 | ||
293 | 400 | Set edges = null; |
294 | 400 | String oppositeKey = null; |
295 | 400 | if (key.equals(HUB_KEY)) { |
296 | 200 | edges = v.getOutEdges(); |
297 | 200 | oppositeKey = AUTHORITY_KEY; |
298 | //leafNodes = mInLeafNodes; | |
299 | } else { | |
300 | 200 | edges = v.getInEdges(); |
301 | 200 | oppositeKey = HUB_KEY; |
302 | } | |
303 | ||
304 | 400 | double sum = 0; |
305 | 400 | for (Iterator edgeIt = edges.iterator(); edgeIt.hasNext();) { |
306 | 500 | Edge e = (Edge) edgeIt.next(); |
307 | //if (mUnreachableVertices.contains(incomingEdge.getOpposite(currentVertex))) | |
308 | // continue; | |
309 | ||
310 | 500 | double currentWeight = 0; |
311 | 500 | if (key.equals(AUTHORITY_KEY)) { |
312 | 250 | currentWeight = getEdgeWeight(e); |
313 | } else { | |
314 | 250 | currentWeight = getInEdgeWeight(e); |
315 | } | |
316 | 500 | sum += getRankScore(e.getOpposite(v), oppositeKey) * currentWeight; |
317 | } | |
318 | ||
319 | 400 | if (getPriorRankScore(v) > 0) { |
320 | 100 | if (key.equals(AUTHORITY_KEY)) { |
321 | 50 | for (Iterator leafIt = mLeafNodes.iterator(); leafIt.hasNext();) { |
322 | 0 | Vertex leafNode = (Vertex) leafIt.next(); |
323 | 0 | double currentWeight = getPriorRankScore(v); |
324 | 0 | sum += getRankScore(leafNode, oppositeKey) * currentWeight; |
325 | } | |
326 | } | |
327 | } | |
328 | ||
329 | 400 | return sum; |
330 | } | |
331 | ||
332 | protected void updateAuthorityRankings() { | |
333 | 50 | double authoritySum = 0; |
334 | ||
335 | //compute authority scores | |
336 | 50 | for (Iterator vertexIt = mReachableVertices.iterator(); vertexIt.hasNext();) { |
337 | 200 | Vertex currentVertex = (Vertex) vertexIt.next(); |
338 | 200 | double newAuthorityScore = computeSum(currentVertex, AUTHORITY_KEY) * (1.0 - mBeta) + mBeta * getPriorRankScore(currentVertex); |
339 | 200 | authoritySum += newAuthorityScore; |
340 | 200 | setRankScore(currentVertex, newAuthorityScore, AUTHORITY_KEY); |
341 | } | |
342 | ||
343 | 50 | if (!NumericalPrecision.equal(authoritySum, 1.0, .1)) { |
344 | 0 | System.err.println("HITS With Priors scores can not be generrated because the specified graph is not connected."); |
345 | 0 | System.err.println("Authority Sum: " + authoritySum); |
346 | } | |
347 | ||
348 | 50 | } |
349 | ||
350 | protected void updateHubRankings() { | |
351 | 50 | double hubSum = 0; |
352 | //compute hub scores | |
353 | 50 | for (Iterator vertexIt = mReachableVertices.iterator(); vertexIt.hasNext();) { |
354 | 200 | Vertex currentVertex = (Vertex) vertexIt.next(); |
355 | 200 | double newHubScore = computeSum(currentVertex, HUB_KEY) * (1.0 - mBeta) + mBeta * getPriorRankScore(currentVertex); |
356 | 200 | hubSum += newHubScore; |
357 | 200 | setRankScore(currentVertex, newHubScore, HUB_KEY); |
358 | } | |
359 | ||
360 | 50 | if (!NumericalPrecision.equal(hubSum, 1.0, .1)) { |
361 | 0 | System.err.println("HITS With Priors scores can not be generrated because the specified graph is not connected."); |
362 | 0 | System.err.println("Hub Sum: " + hubSum); |
363 | } | |
364 | 50 | } |
365 | ||
366 | ||
367 | protected void updatePreviousScores() { | |
368 | 50 | for (Iterator vIt = getVertices().iterator(); vIt.hasNext();) { |
369 | 200 | Vertex currentVertex = (Vertex) vIt.next(); |
370 | 200 | MutableDouble previousAuthorityScore = (MutableDouble) mPreviousAuthorityScores.get(currentVertex); |
371 | 200 | double currentAuthorityScore = getRankScore(currentVertex, AUTHORITY_KEY); |
372 | 200 | previousAuthorityScore.setDoubleValue(currentAuthorityScore); |
373 | ||
374 | 200 | MutableDouble previousHubScore = (MutableDouble) mPreviousHubScores.get(currentVertex); |
375 | 200 | double currentHubScore = getRankScore(currentVertex, HUB_KEY); |
376 | 200 | previousHubScore.setDoubleValue(currentHubScore); |
377 | } | |
378 | 50 | } |
379 | ||
380 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |