# Coverage details for edu.uci.ics.jung.algorithms.importance.HITSWithPriors

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. 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.