jcoverage | summary | package | file

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

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.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      */
630    public HITSWithPriors(Graph graph, double bias, Set priors) {
640        mKeyToUseForRanking = AUTHORITY_KEY;
650        mBeta = bias;
660        setPriors(priors);
670        initialize(graph, null);
680    }
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      */
772    public HITSWithPriors(Graph graph, boolean useAuthorityForRanking, double bias, Set priors, String edgeWeightKey) {
782        setUseAuthorityForRanking(useAuthorityForRanking);
792        mBeta = bias;
802        setPriors(priors);
812        initialize(graph, edgeWeightKey);
822    }
83  
84     protected void initialize(Graph g, String edgeWeightKeyName) {
85  
862        super.initialize(g, true, false);
87  
882        mPreviousAuthorityScores = new HashMap();
892        mPreviousHubScores = new HashMap();
90  
91  
92 // int numVertices = getVertices().size();
932        for (Iterator vIt = g.getVertices().iterator(); vIt.hasNext();) {
948            Vertex currentVertex = (Vertex) vIt.next();
95  
968            mPreviousAuthorityScores.put(currentVertex, new MutableDouble(0));
978            mPreviousHubScores.put(currentVertex, new MutableDouble(0));
98  
998            setRankScore(currentVertex, 0, AUTHORITY_KEY);
1008            setRankScore(currentVertex, 0, HUB_KEY);
101  
1028            setPriorRankScore(currentVertex, 0);
103         }
104  
1052        WeakComponentClusterer wcExtractor = new WeakComponentClusterer();
1062        ClusterSet clusters = wcExtractor.extract(g);
1072        mReachableVertices = new HashSet();
108  
1092        double numPriors = getPriors().size();
1102        for (Iterator it = getPriors().iterator(); it.hasNext();) {
1112            Vertex currentVertex = (Vertex) it.next();
1122            setPriorRankScore(currentVertex, 1.0 / numPriors);
1132            for (Iterator cIt = clusters.iterator(); cIt.hasNext();) {
1142                Set members = (Set) cIt.next();
1152                if (members.contains(currentVertex)) {
1162                    mReachableVertices.addAll(members);
117                 }
118             }
119         }
120  
1212        mLeafNodes = new HashSet();
1222        int numReachableVertices = mReachableVertices.size();
1232        for (Iterator vIt = mReachableVertices.iterator(); vIt.hasNext();) {
1248            Vertex currentVertex = (Vertex) vIt.next();
1258            setRankScore(currentVertex, 1.0 / numReachableVertices, AUTHORITY_KEY);
1268            setRankScore(currentVertex, 1.0 / numReachableVertices, HUB_KEY);
1278            if (currentVertex.outDegree() == 0) {
1280                mLeafNodes.add(currentVertex);
129             }
130         }
131  
1322        if (edgeWeightKeyName == null) {
1332            assignDefaultEdgeTransitionWeights();
134         } else {
1350            setUserDefinedEdgeWeightKey(edgeWeightKeyName);
1360            normalizeEdgeTransitionWeights();
137         }
1382        assignInlinkEdgeTransitionWeights();
139  
1402    }
141  
142     protected void finalizeIterations() {
1432        super.finalizeIterations();
1442        for (Iterator it = getVertices().iterator(); it.hasNext();) {
1458            Vertex currentVertex = (Vertex) it.next();
1468            if (mKeyToUseForRanking.equals(AUTHORITY_KEY)) {
1474                currentVertex.removeUserDatum(HUB_KEY);
148             } else {
1494                currentVertex.removeUserDatum(AUTHORITY_KEY);
150             }
151         }
152  
1532    }
154  
155     protected double getInEdgeWeight(Edge e) {
156250        MutableDouble value = (MutableDouble) e.getUserDatum(IN_EDGE_WEIGHT);
157250        return value.doubleValue();
158     }
159  
160     protected void setInEdgeWeight(Edge e, double weight) {
16110        MutableDouble value = (MutableDouble) e.getUserDatum(IN_EDGE_WEIGHT);
16210        if (value == null) {
16310            e.setUserDatum(IN_EDGE_WEIGHT, new MutableDouble(weight), UserData.SHARED);
164         } else {
1650            value.setDoubleValue(weight);
166         }
16710    }
168  
169     private void assignInlinkEdgeTransitionWeights() {
170  
1712        for (Iterator vIt = getVertices().iterator(); vIt.hasNext();) {
1728            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 // }
1808            Set incomingEdges = currentVertex.getInEdges();
181  
1828            double total = 0;
1838            for (Iterator edgeIt = incomingEdges.iterator(); edgeIt.hasNext();) {
18410                Edge currentEdge = (Edge) edgeIt.next();
18510                total += getEdgeWeight(currentEdge);
186             }
187  
1888            for (Iterator edgeIt = incomingEdges.iterator(); edgeIt.hasNext();) {
18910                Edge currentEdge = (Edge) edgeIt.next();
19010                double weight = getEdgeWeight(currentEdge);
19110                setInEdgeWeight(currentEdge, weight / total);
192             }
193         }
1942    }
195  
196  
197     /**
198      * the user datum key used to store the rank scores
199      * @return the key
200      */
201     public String getRankScoreKey() {
2020        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) {
21116        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) {
2221316        return ((MutableDouble) v.getUserDatum(key)).doubleValue();
223     }
224  
225     protected double getPreviousAuthorityScore(Element v) {
226200        return ((MutableDouble) mPreviousAuthorityScores.get(v)).doubleValue();
227     }
228  
229     protected double getPreviousHubScore(Element v) {
230200        return ((MutableDouble) mPreviousHubScores.get(v)).doubleValue();
231     }
232  
233     protected void setRankScore(Element v, double rankValue, String key) {
234432        MutableDouble value = (MutableDouble) v.getUserDatum(key);
235  
236432        if (value == null) {
23716            v.setUserDatum(key, new MutableDouble(rankValue), UserData.SHARED);
238         } else {
239416            value.setDoubleValue(rankValue);
240         }
241432    }
242  
243     protected void setRankScore(Element v, double rankValue) {
2440        setRankScore(v, rankValue, mKeyToUseForRanking);
2450    }
246  
247     protected double evaluateIteration() {
24850        updatePreviousScores();
249  
250         //Perform 2 update steps
25150        updateAuthorityRankings();
25250        updateHubRankings();
253  
25450        double hubMSE = 0;
25550        double authorityMSE = 0;
256  
257         //Test for convergence
25850        int numVertices = mReachableVertices.size();
25950        for (Iterator vIt = mReachableVertices.iterator(); vIt.hasNext();) {
260200            Vertex currentVertex = (Vertex) vIt.next();
261  
262200            double currentAuthorityScore = getRankScore(currentVertex, AUTHORITY_KEY);
263200            double currentHubScore = getRankScore(currentVertex, HUB_KEY);
264  
265200            double previousAuthorityScore = getPreviousAuthorityScore(currentVertex);
266200            double previousHubScore = getPreviousHubScore(currentVertex);
267  
268200            hubMSE += Math.pow(currentHubScore - previousHubScore, 2);
269200            authorityMSE += Math.pow(currentAuthorityScore - previousAuthorityScore, 2);
270         }
271  
27250        hubMSE = Math.pow(hubMSE / numVertices, 0.5);
27350        authorityMSE = Math.pow(authorityMSE / numVertices, 0.5);
274  
27550        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) {
2842        if (useAuthorityForRanking) {
2851            mKeyToUseForRanking = AUTHORITY_KEY;
286         } else {
2871            mKeyToUseForRanking = HUB_KEY;
288         }
2892    }
290  
291     private double computeSum(Vertex v, String key) {
292  
293400        Set edges = null;
294400        String oppositeKey = null;
295400        if (key.equals(HUB_KEY)) {
296200            edges = v.getOutEdges();
297200            oppositeKey = AUTHORITY_KEY;
298             //leafNodes = mInLeafNodes;
299         } else {
300200            edges = v.getInEdges();
301200            oppositeKey = HUB_KEY;
302         }
303  
304400        double sum = 0;
305400        for (Iterator edgeIt = edges.iterator(); edgeIt.hasNext();) {
306500            Edge e = (Edge) edgeIt.next();
307             //if (mUnreachableVertices.contains(incomingEdge.getOpposite(currentVertex)))
308             // continue;
309  
310500            double currentWeight = 0;
311500            if (key.equals(AUTHORITY_KEY)) {
312250                currentWeight = getEdgeWeight(e);
313             } else {
314250                currentWeight = getInEdgeWeight(e);
315             }
316500            sum += getRankScore(e.getOpposite(v), oppositeKey) * currentWeight;
317         }
318  
319400        if (getPriorRankScore(v) > 0) {
320100            if (key.equals(AUTHORITY_KEY)) {
32150                for (Iterator leafIt = mLeafNodes.iterator(); leafIt.hasNext();) {
3220                    Vertex leafNode = (Vertex) leafIt.next();
3230                    double currentWeight = getPriorRankScore(v);
3240                    sum += getRankScore(leafNode, oppositeKey) * currentWeight;
325                 }
326             }
327         }
328  
329400        return sum;
330     }
331  
332     protected void updateAuthorityRankings() {
33350        double authoritySum = 0;
334  
335         //compute authority scores
33650        for (Iterator vertexIt = mReachableVertices.iterator(); vertexIt.hasNext();) {
337200            Vertex currentVertex = (Vertex) vertexIt.next();
338200            double newAuthorityScore = computeSum(currentVertex, AUTHORITY_KEY) * (1.0 - mBeta) + mBeta * getPriorRankScore(currentVertex);
339200            authoritySum += newAuthorityScore;
340200            setRankScore(currentVertex, newAuthorityScore, AUTHORITY_KEY);
341         }
342  
34350        if (!NumericalPrecision.equal(authoritySum, 1.0, .1)) {
3440            System.err.println("HITS With Priors scores can not be generrated because the specified graph is not connected.");
3450            System.err.println("Authority Sum: " + authoritySum);
346         }
347  
34850    }
349  
350     protected void updateHubRankings() {
35150        double hubSum = 0;
352         //compute hub scores
35350        for (Iterator vertexIt = mReachableVertices.iterator(); vertexIt.hasNext();) {
354200            Vertex currentVertex = (Vertex) vertexIt.next();
355200            double newHubScore = computeSum(currentVertex, HUB_KEY) * (1.0 - mBeta) + mBeta * getPriorRankScore(currentVertex);
356200            hubSum += newHubScore;
357200            setRankScore(currentVertex, newHubScore, HUB_KEY);
358         }
359  
36050        if (!NumericalPrecision.equal(hubSum, 1.0, .1)) {
3610            System.err.println("HITS With Priors scores can not be generrated because the specified graph is not connected.");
3620            System.err.println("Hub Sum: " + hubSum);
363         }
36450    }
365  
366  
367     protected void updatePreviousScores() {
36850        for (Iterator vIt = getVertices().iterator(); vIt.hasNext();) {
369200            Vertex currentVertex = (Vertex) vIt.next();
370200            MutableDouble previousAuthorityScore = (MutableDouble) mPreviousAuthorityScores.get(currentVertex);
371200            double currentAuthorityScore = getRankScore(currentVertex, AUTHORITY_KEY);
372200            previousAuthorityScore.setDoubleValue(currentAuthorityScore);
373  
374200            MutableDouble previousHubScore = (MutableDouble) mPreviousHubScores.get(currentVertex);
375200            double currentHubScore = getRankScore(currentVertex, HUB_KEY);
376200            previousHubScore.setDoubleValue(currentHubScore);
377         }
37850    }
379  
380 }

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.