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. |
copyright © 2003, jcoverage ltd. all rights reserved. |