jcoverage | summary | package | file

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

LineHitsSource
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      */
581    public HITS(Graph graph, boolean useAuthorityForRanking) {
591        mKeyToUseForRanking = AUTHORITY_KEY;
601        if (!useAuthorityForRanking) {
611         mKeyToUseForRanking = HUB_KEY;
62         }
631        initialize(graph);
641    }
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      */
711    public HITS(Graph graph) {
721        mKeyToUseForRanking = AUTHORITY_KEY;
731        initialize(graph);
741    }
75  
76     protected void initialize(Graph g) {
77  
782        super.initialize(g, true, false);
79  
802        mPreviousAuthorityScores = new HashMap();
812        mPreviousHubScores = new HashMap();
82  
832        for (Iterator vIt = g.getVertices().iterator(); vIt.hasNext();) {
8410            Vertex currentVertex = (Vertex) vIt.next();
8510            setRankScore(currentVertex, 1.0, AUTHORITY_KEY);
8610            setRankScore(currentVertex, 1.0, HUB_KEY);
87  
8810            mPreviousAuthorityScores.put(currentVertex, new MutableDouble(0));
8910            mPreviousHubScores.put(currentVertex, new MutableDouble(0));
90         }
912    }
92  
93     protected void finalizeIterations() {
942        super.finalizeIterations();
952        for (Iterator it = getVertices().iterator(); it.hasNext();) {
9610            Vertex currentVertex = (Vertex) it.next();
9710            if (mKeyToUseForRanking.equals(AUTHORITY_KEY)) {
985                currentVertex.removeUserDatum(HUB_KEY);
99             } else {
1005                currentVertex.removeUserDatum(AUTHORITY_KEY);
101             }
102         }
103  
1042    }
105  
106     /**
107      * the user datum key used to store the rank scores
108      * @return the key
109      */
110     public String getRankScoreKey() {
1110        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) {
12018        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) {
1311618        return ((MutableDouble) v.getUserDatum(key)).doubleValue();
132     }
133  
134     protected double getPreviousAuthorityScore(Element v) {
135200        return ((MutableDouble) mPreviousAuthorityScores.get(v)).doubleValue();
136     }
137  
138     protected double getPreviousHubScore(Element v) {
139200        return ((MutableDouble) mPreviousHubScores.get(v)).doubleValue();
140     }
141  
142     protected void setRankScore(Element v, double rankValue, String key) {
143820        MutableDouble value = (MutableDouble) v.getUserDatum(key);
144  
145820        if (value == null) {
14620            v.setUserDatum(key, new MutableDouble(rankValue), UserData.SHARED);
147         } else {
148800            value.setDoubleValue(rankValue);
149         }
150820    }
151  
152     protected void setRankScore(Element v, double rankValue) {
1530        setRankScore(v, rankValue, mKeyToUseForRanking);
1540    }
155  
156     protected double evaluateIteration() {
15740        updatePreviousScores();
158  
159         //Perform 2 update steps
16040        updateAuthorityRankings();
16140        updateHubRankings();
162  
16340        double hubMSE = 0;
16440        double authorityMSE = 0;
165  
166         //Normalize rankings and test for convergence
16740        int numVertices = getVertices().size();
16840        for (Iterator vIt = getVertices().iterator(); vIt.hasNext();) {
169200            Vertex currentVertex = (Vertex) vIt.next();
170  
171200            double currentAuthorityScore = getRankScore(currentVertex, AUTHORITY_KEY);
172200            double currentHubScore = getRankScore(currentVertex, HUB_KEY);
173  
174200            double previousAuthorityScore = getPreviousAuthorityScore(currentVertex);
175200            double previousHubScore = getPreviousHubScore(currentVertex);
176  
177200            hubMSE += Math.pow(currentHubScore - previousHubScore, 2);
178200            authorityMSE += Math.pow(currentAuthorityScore - previousAuthorityScore, 2);
179         }
180  
18140        hubMSE = Math.pow(hubMSE / numVertices, 0.5);
18240        authorityMSE = Math.pow(authorityMSE / numVertices, 0.5);
183  
18440        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) {
1930        if (useAuthorityForRanking) {
1940            mKeyToUseForRanking = AUTHORITY_KEY;
195         } else {
1960            mKeyToUseForRanking = HUB_KEY;
197         }
1980    }
199  
200     private double computeSum(Set neighbors, String key) {
201400        double sum = 0;
202400        for (Iterator neighborIt = neighbors.iterator(); neighborIt.hasNext();) {
203400            Vertex currentNeighbor = (Vertex) neighborIt.next();
204400            sum += getRankScore(currentNeighbor, key);
205         }
206400        return sum;
207     }
208  
209     private void normalizeRankings(double normConstant, String key) {
21080        for (Iterator vertexIt = getVertices().iterator(); vertexIt.hasNext();) {
211400            Vertex v = (Vertex) vertexIt.next();
212400            double rankScore = getRankScore(v,key);
213400            setRankScore(v,rankScore/normConstant,key);
214         }
21580    }
216  
217     protected void updateAuthorityRankings() {
21840        double total = 0;
219         //compute authority scores
22040        for (Iterator vertexIt = getVertices().iterator(); vertexIt.hasNext();) {
221200            Vertex currentVertex = (Vertex) vertexIt.next();
222200            double currentHubSum = computeSum(currentVertex.getPredecessors(), HUB_KEY);
223200            double newAuthorityScore = currentHubSum;
224200            total += newAuthorityScore;
225200            setRankScore(currentVertex, newAuthorityScore, AUTHORITY_KEY);
226         }
227  
228  
22940        normalizeRankings(total, AUTHORITY_KEY);
23040    }
231  
232     protected void updateHubRankings() {
23340        double total = 0;
234  
235         //compute hub scores
23640        for (Iterator vertexIt = getVertices().iterator(); vertexIt.hasNext();) {
237200            Vertex currentVertex = (Vertex) vertexIt.next();
238200            double currentAuthoritySum = computeSum(currentVertex.getSuccessors(), AUTHORITY_KEY);
239200            double newHubScore = currentAuthoritySum;
240200            total += newHubScore;
241200            setRankScore(currentVertex, newHubScore, HUB_KEY);
242         }
24340        normalizeRankings(total, HUB_KEY);
24440    }
245  
246     protected void updatePreviousScores() {
24740        for (Iterator vIt = getVertices().iterator(); vIt.hasNext();) {
248200            Vertex currentVertex = (Vertex) vIt.next();
249200            MutableDouble previousAuthorityScore = (MutableDouble) mPreviousAuthorityScores.get(currentVertex);
250200            double currentAuthorityScore = getRankScore(currentVertex, AUTHORITY_KEY);
251200            previousAuthorityScore.setDoubleValue(currentAuthorityScore);
252  
253200            MutableDouble previousHubScore = (MutableDouble) mPreviousHubScores.get(currentVertex);
254200            double currentHubScore = getRankScore(currentVertex, HUB_KEY);
255200            previousHubScore.setDoubleValue(currentHubScore);
256         }
25740    }
258  
259 }

jcoverage | summary | package | file

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.