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

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.Iterator;`
14 |  | `import java.util.Map;`
15 |  | `import java.util.Set;`
16 |  | ``
17 |  | `import edu.uci.ics.jung.graph.Element;`
18 |  | `import edu.uci.ics.jung.graph.Graph;`
19 |  | `import edu.uci.ics.jung.graph.Vertex;`
20 |  | `import edu.uci.ics.jung.utils.MutableDouble;`
21 |  | `import edu.uci.ics.jung.utils.UserData;`
22 |  | ``
23 |  | `/**`
24 |  | `* Calculates the "hubs-and-authorities" importance measures for each node in a graph.`
25 |  | `* These measures are defined recursively as follows:`
26 |  | `*`
27 |  | `* <ul>`
28 |  | `* <li>The *hubness* of a node is the degree to which a node links to other important authorities</li>`
29 |  | `* <li>The *authoritativeness* of a node is the degree to which a node is pointed to by important hubs</li>`
30 |  | `* <p>`
31 |  | `* Note: This algorithm uses the same key as HITSWithPriors for storing rank sccores.`
32 |  | `* <p>`
33 |  | `* A simple example of usage is:`
34 |  | `* <pre>`
35 |  | `* HITS ranker = new HITS(someGraph);`
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 "Authoritative sources in a hyperlinked environment by Jon Kleinberg, 1997"`
44 |  | `*/`
45 |  | `public class HITS extends AbstractRanker {`
46 |  | `protected static final String AUTHORITY_KEY = "jung.algorithms.importance.AUTHORITY";`
47 |  | `protected static final String HUB_KEY = "jung.algorithms.importance.HUB";`
48 |  | `private String mKeyToUseForRanking;`
49 |  | `private Map mPreviousAuthorityScores;`
50 |  | `private Map mPreviousHubScores;`
51 |  | ``
52 |  | `/**`
53 |  | `* Constructs an instance of the ranker where the type of importance that is associated with the`
54 |  | `* rank score is the node's importance as an authority.`
55 |  | `* @param graph the graph whose nodes are to be ranked`
56 |  | `* @param useAuthorityForRanking`
57 |  | `*/`
58 | 1 | `public HITS(Graph graph, boolean useAuthorityForRanking) {`
59 | 1 | `mKeyToUseForRanking = AUTHORITY_KEY;`
60 | 1 | `if (!useAuthorityForRanking) {`
61 | 1 | `mKeyToUseForRanking = HUB_KEY;`
62 |  | `}`
63 | 1 | `initialize(graph);`
64 | 1 | `}`
65 |  | ``
66 |  | `/**`
67 |  | `* Constructs an instance of the ranker where the type of importance that is associated with the`
68 |  | `* rank score is the node's importance as an authority.`
69 |  | `* @param graph the graph whose nodes are to be ranked`
70 |  | `*/`
71 | 1 | `public HITS(Graph graph) {`
72 | 1 | `mKeyToUseForRanking = AUTHORITY_KEY;`
73 | 1 | `initialize(graph);`
74 | 1 | `}`
75 |  | ``
76 |  | `protected void initialize(Graph g) {`
77 |  | ``
78 | 2 | `super.initialize(g, true, false);`
79 |  | ``
80 | 2 | `mPreviousAuthorityScores = new HashMap();`
81 | 2 | `mPreviousHubScores = new HashMap();`
82 |  | ``
83 | 2 | `for (Iterator vIt = g.getVertices().iterator(); vIt.hasNext();) {`
84 | 10 | `Vertex currentVertex = (Vertex) vIt.next();`
85 | 10 | `setRankScore(currentVertex, 1.0, AUTHORITY_KEY);`
86 | 10 | `setRankScore(currentVertex, 1.0, HUB_KEY);`
87 |  | ``
88 | 10 | `mPreviousAuthorityScores.put(currentVertex, new MutableDouble(0));`
89 | 10 | `mPreviousHubScores.put(currentVertex, new MutableDouble(0));`
90 |  | `}`
91 | 2 | `}`
92 |  | ``
93 |  | `protected void finalizeIterations() {`
94 | 2 | `super.finalizeIterations();`
95 | 2 | `for (Iterator it = getVertices().iterator(); it.hasNext();) {`
96 | 10 | `Vertex currentVertex = (Vertex) it.next();`
97 | 10 | `if (mKeyToUseForRanking.equals(AUTHORITY_KEY)) {`
98 | 5 | `currentVertex.removeUserDatum(HUB_KEY);`
99 |  | `} else {`
100 | 5 | `currentVertex.removeUserDatum(AUTHORITY_KEY);`
101 |  | `}`
102 |  | `}`
103 |  | ``
104 | 2 | `}`
105 |  | ``
106 |  | `/**`
107 |  | `* the user datum key used to store the rank scores`
108 |  | `* @return the key`
109 |  | `*/`
110 |  | `public String getRankScoreKey() {`
111 | 0 | `return mKeyToUseForRanking;`
112 |  | `}`
113 |  | ``
114 |  | `/**`
115 |  | `* Given a node, returns the corresponding rank score. This implementation of <code>getRankScore</code> assumes`
116 |  | `* the decoration representing the rank score is of type <code>MutableDouble</code>.`
117 |  | `* @return the rank score for this node`
118 |  | `*/`
119 |  | `public double getRankScore(Element v) {`
120 | 18 | `return getRankScore(v, mKeyToUseForRanking);`
121 |  | `}`
122 |  | ``
123 |  | `/**`
124 |  | `* Given a node and a key, returns the corresponding rank score. Assumes the decoration representing the rank score`
125 |  | `* is of type <code>MutableDouble</code>.`
126 |  | `* @param v the node in question`
127 |  | `* @param key the user datum key that indexes the rank score value`
128 |  | `* @return the rank score for this node`
129 |  | `*/`
130 |  | `protected double getRankScore(Element v, String key) {`
131 | 1618 | `return ((MutableDouble) v.getUserDatum(key)).doubleValue();`
132 |  | `}`
133 |  | ``
134 |  | `protected double getPreviousAuthorityScore(Element v) {`
135 | 200 | `return ((MutableDouble) mPreviousAuthorityScores.get(v)).doubleValue();`
136 |  | `}`
137 |  | ``
138 |  | `protected double getPreviousHubScore(Element v) {`
139 | 200 | `return ((MutableDouble) mPreviousHubScores.get(v)).doubleValue();`
140 |  | `}`
141 |  | ``
142 |  | `protected void setRankScore(Element v, double rankValue, String key) {`
143 | 820 | `MutableDouble value = (MutableDouble) v.getUserDatum(key);`
144 |  | ``
145 | 820 | `if (value == null) {`
146 | 20 | `v.setUserDatum(key, new MutableDouble(rankValue), UserData.SHARED);`
147 |  | `} else {`
148 | 800 | `value.setDoubleValue(rankValue);`
149 |  | `}`
150 | 820 | `}`
151 |  | ``
152 |  | `protected void setRankScore(Element v, double rankValue) {`
153 | 0 | `setRankScore(v, rankValue, mKeyToUseForRanking);`
154 | 0 | `}`
155 |  | ``
156 |  | `protected double evaluateIteration() {`
157 | 40 | `updatePreviousScores();`
158 |  | ``
159 |  | `//Perform 2 update steps`
160 | 40 | `updateAuthorityRankings();`
161 | 40 | `updateHubRankings();`
162 |  | ``
163 | 40 | `double hubMSE = 0;`
164 | 40 | `double authorityMSE = 0;`
165 |  | ``
166 |  | `//Normalize rankings and test for convergence`
167 | 40 | `int numVertices = getVertices().size();`
168 | 40 | `for (Iterator vIt = getVertices().iterator(); vIt.hasNext();) {`
169 | 200 | `Vertex currentVertex = (Vertex) vIt.next();`
170 |  | ``
171 | 200 | `double currentAuthorityScore = getRankScore(currentVertex, AUTHORITY_KEY);`
172 | 200 | `double currentHubScore = getRankScore(currentVertex, HUB_KEY);`
173 |  | ``
174 | 200 | `double previousAuthorityScore = getPreviousAuthorityScore(currentVertex);`
175 | 200 | `double previousHubScore = getPreviousHubScore(currentVertex);`
176 |  | ``
177 | 200 | `hubMSE += Math.pow(currentHubScore - previousHubScore, 2);`
178 | 200 | `authorityMSE += Math.pow(currentAuthorityScore - previousAuthorityScore, 2);`
179 |  | `}`
180 |  | ``
181 | 40 | `hubMSE = Math.pow(hubMSE / numVertices, 0.5);`
182 | 40 | `authorityMSE = Math.pow(authorityMSE / numVertices, 0.5);`
183 |  | ``
184 | 40 | `return hubMSE + authorityMSE;`
185 |  | `}`
186 |  | ``
187 |  | `/**`
188 |  | `* If <code>evaluate()</code> has not already been called, the user can override the type of importance.`
189 |  | `* (hub or authority) that should be associated with the rank score.`
190 |  | `* @param useAuthorityForRanking if <code>true</code>, authority is used; if <code>false</code>, hub is used`
191 |  | `*/`
192 |  | `public void setUseAuthorityForRanking(boolean useAuthorityForRanking) {`
193 | 0 | `if (useAuthorityForRanking) {`
194 | 0 | `mKeyToUseForRanking = AUTHORITY_KEY;`
195 |  | `} else {`
196 | 0 | `mKeyToUseForRanking = HUB_KEY;`
197 |  | `}`
198 | 0 | `}`
199 |  | ``
200 |  | `private double computeSum(Set neighbors, String key) {`
201 | 400 | `double sum = 0;`
202 | 400 | `for (Iterator neighborIt = neighbors.iterator(); neighborIt.hasNext();) {`
203 | 400 | `Vertex currentNeighbor = (Vertex) neighborIt.next();`
204 | 400 | `sum += getRankScore(currentNeighbor, key);`
205 |  | `}`
206 | 400 | `return sum;`
207 |  | `}`
208 |  | ``
209 |  | `private void normalizeRankings(double normConstant, String key) {`
210 | 80 | `for (Iterator vertexIt = getVertices().iterator(); vertexIt.hasNext();) {`
211 | 400 | `Vertex v = (Vertex) vertexIt.next();`
212 | 400 | `double rankScore = getRankScore(v,key);`
213 | 400 | `setRankScore(v,rankScore/normConstant,key);`
214 |  | `}`
215 | 80 | `}`
216 |  | ``
217 |  | `protected void updateAuthorityRankings() {`
218 | 40 | `double total = 0;`
219 |  | `//compute authority scores`
220 | 40 | `for (Iterator vertexIt = getVertices().iterator(); vertexIt.hasNext();) {`
221 | 200 | `Vertex currentVertex = (Vertex) vertexIt.next();`
222 | 200 | `double currentHubSum = computeSum(currentVertex.getPredecessors(), HUB_KEY);`
223 | 200 | `double newAuthorityScore = currentHubSum;`
224 | 200 | `total += newAuthorityScore;`
225 | 200 | `setRankScore(currentVertex, newAuthorityScore, AUTHORITY_KEY);`
226 |  | `}`
227 |  | ``
228 |  | ``
229 | 40 | `normalizeRankings(total, AUTHORITY_KEY);`
230 | 40 | `}`
231 |  | ``
232 |  | `protected void updateHubRankings() {`
233 | 40 | `double total = 0;`
234 |  | ``
235 |  | `//compute hub scores`
236 | 40 | `for (Iterator vertexIt = getVertices().iterator(); vertexIt.hasNext();) {`
237 | 200 | `Vertex currentVertex = (Vertex) vertexIt.next();`
238 | 200 | `double currentAuthoritySum = computeSum(currentVertex.getSuccessors(), AUTHORITY_KEY);`
239 | 200 | `double newHubScore = currentAuthoritySum;`
240 | 200 | `total += newHubScore;`
241 | 200 | `setRankScore(currentVertex, newHubScore, HUB_KEY);`
242 |  | `}`
243 | 40 | `normalizeRankings(total, HUB_KEY);`
244 | 40 | `}`
245 |  | ``
246 |  | `protected void updatePreviousScores() {`
247 | 40 | `for (Iterator vIt = getVertices().iterator(); vIt.hasNext();) {`
248 | 200 | `Vertex currentVertex = (Vertex) vIt.next();`
249 | 200 | `MutableDouble previousAuthorityScore = (MutableDouble) mPreviousAuthorityScores.get(currentVertex);`
250 | 200 | `double currentAuthorityScore = getRankScore(currentVertex, AUTHORITY_KEY);`
251 | 200 | `previousAuthorityScore.setDoubleValue(currentAuthorityScore);`
252 |  | ``
253 | 200 | `MutableDouble previousHubScore = (MutableDouble) mPreviousHubScores.get(currentVertex);`
254 | 200 | `double currentHubScore = getRankScore(currentVertex, HUB_KEY);`
255 | 200 | `previousHubScore.setDoubleValue(currentHubScore);`
256 |  | `}`
257 | 40 | `}`
258 |  | ``
259 |  | `}`

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.