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

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.Set;
16  
17 import edu.uci.ics.jung.graph.DirectedGraph;
18 import edu.uci.ics.jung.graph.Edge;
19 import edu.uci.ics.jung.graph.Vertex;
20 import edu.uci.ics.jung.utils.MutableDouble;
21 import edu.uci.ics.jung.utils.NumericalPrecision;
22 import edu.uci.ics.jung.utils.Pair;
23  
24 /**
25  * This algorithm measures the importance of a node in terms of the fraction of time spent at that node relative to
26  * all other nodes. This fraction is measured by first transforming the graph into a first-order Markov chain
27  * where the transition probability of going from node u to node v is equal to (1-alpha)*[1/outdegree(u)] + alpha*(1/|V|)
28  * where |V| is the # of vertices in the graph and alpha is a parameter typically set to be between 0.1 and 0.2 (according
29  * to the authors). If u has no out-edges in the original graph then 0 is used instead of 1/outdegree(v). Once the markov
30  * chain is created, the stationary probability of being at each node (state) is computed using an iterative update
31  * method that is guaranteed to converge if the markov chain is ergodic.
32  * <p>
33  * A simple example of usage is:
34  * <pre>
35  * PageRank ranker = new PageRank(someGraph,0.15);
36  * ranker.evaluate();
37  * ranker.printRankings();
38  * </pre>
39  * <p>
40  * Running time: O(|E|*I) where |E| is the number of edges and I is the number of iterations until convergence
41  *
42  * @author Scott White
43  * @see "The Anatomy of a Large-Scale Hypertextual Web Search Engine by L. Page and S. Brin, 1999"
44  */
45 public class PageRank extends RelativeAuthorityRanker {
46     public final static String KEY = "jung.algorithms.importance.PageRank.RankScore";
47     private double mAlpha;
48     private HashMap mPreviousRankingsMap;
49     private Set mUnreachableVertices;
50     private Set mReachableVertices;
51     private Set mLeafNodes;
52  
53     /**
54      * Basic constructor which initializes the algorithm
55      * @param graph the graph whose nodes are to be ranked
56      * @param bias the value (between 0 and 1) that indicates how much to dampen the underlying markov chain
57      * with underlying uniform transitions over all nodes. Generally, values between 0.0-0.3 are used.
58      */
590    public PageRank(DirectedGraph graph, double bias) {
600        initialize(graph, bias, null);
610        initializeRankings(graph.getVertices(), new HashSet());
620    }
63  
64     /**
65      * Specialized constructor that allows the user to specify an edge key if edges already have user-defined
66      * weights assigned to them.
67      * @param graph the graph whose nodes are to be ranked
68      * @param bias the value (between 0 and 1) that indicates how much to dampen the underlying markov chain
69      * with underlying uniform transitions over all nodes. Generally, values between 0.0-0.3 are used.
70      * @param edgeWeightKeyName if non-null, uses the user-defined weights to compute the transition probabilities;
71      * if null then default transition probabilities (1/outdegree(u)) are used
72      */
732    public PageRank(DirectedGraph graph, double bias, String edgeWeightKeyName) {
742        initialize(graph, bias, edgeWeightKeyName);
752        initializeRankings(graph.getVertices(), new HashSet());
762    }
77  
782    protected PageRank(DirectedGraph graph, double bias, String edgeWeightKeyName, Pair reachables) {
792        initialize(graph, bias, edgeWeightKeyName);
802        initializeRankings((Set) reachables.getFirst(), (Set) reachables.getSecond());
812    }
82  
83     protected void initialize(DirectedGraph graph, double bias, String edgeWeightKeyName) {
844        super.initialize(graph, true, false);
854        if ((bias < 0) || (bias > 1.0)) {
860            throw new IllegalArgumentException("Bias " + bias + " must be between 0 and 1.");
87         }
884        mAlpha = bias;
894        if (edgeWeightKeyName == null) {
902            assignDefaultEdgeTransitionWeights();
91         } else {
922            setUserDefinedEdgeWeightKey(edgeWeightKeyName);
932            normalizeEdgeTransitionWeights();
94         }
95  
964    }
97  
98     protected void initializeRankings(Set reachableVertices, Set unreachableVertices) {
99  
1004        mReachableVertices = reachableVertices;
1014        double numVertices = reachableVertices.size();
1024        mPreviousRankingsMap = new HashMap();
1034        mLeafNodes = new HashSet();
1044        for (Iterator vIt = mReachableVertices.iterator(); vIt.hasNext();) {
10516            Vertex currentVertex = (Vertex) vIt.next();
10616            setRankScore(currentVertex, 1.0 / numVertices);
10716            setPriorRankScore(currentVertex, 1.0 / numVertices);
10816            mPreviousRankingsMap.put(currentVertex, new MutableDouble(1.0 / numVertices));
10916            if (currentVertex.outDegree() == 0) {
1100                mLeafNodes.add(currentVertex);
111             }
112         }
113  
1144        mUnreachableVertices = unreachableVertices;
1154        for (Iterator vIt = mUnreachableVertices.iterator(); vIt.hasNext();) {
1166            Vertex currentVertex = (Vertex) vIt.next();
1176            setRankScore(currentVertex, 0);
1186            setPriorRankScore(currentVertex, 0);
1196            mPreviousRankingsMap.put(currentVertex, new MutableDouble(0));
120         }
1214    }
122  
123     protected void reinitialize() {
1240        initializeRankings(mReachableVertices, mUnreachableVertices);
1250    }
126  
127     protected void updateRankings() {
128149        double totalSum = 0;
129  
130149        for (Iterator vIt = mReachableVertices.iterator(); vIt.hasNext();) {
131596            Vertex currentVertex = (Vertex) vIt.next();
132  
133 // Set incomingEdges = null;
134 // if (getGraph().isDirected()) {
135 // incomingEdges = currentVertex.getInEdges();
136 // } else {
137 // incomingEdges = currentVertex.getIncidentEdges();
138 // }
139596            Set incomingEdges = currentVertex.getInEdges();
140  
141596            double currentPageRankSum = 0;
142596            for (Iterator edgeIt = incomingEdges.iterator(); edgeIt.hasNext();) {
143751                Edge incomingEdge = (Edge) edgeIt.next();
144751                if (mUnreachableVertices.contains(incomingEdge.getOpposite(currentVertex)))
1450                    continue;
146  
147751                double currentWeight = getEdgeWeight(incomingEdge);
148751                currentPageRankSum += ((Number) mPreviousRankingsMap.get(incomingEdge.getOpposite(currentVertex))).doubleValue() * currentWeight;
149             }
150  
151596            if (getPriorRankScore(currentVertex) > 0) {
152454                for (Iterator leafIt = mLeafNodes.iterator(); leafIt.hasNext();) {
1530                    Vertex leafNode = (Vertex) leafIt.next();
1540                    double currentWeight = getPriorRankScore(currentVertex);
1550                    currentPageRankSum += ((Number) mPreviousRankingsMap.get(leafNode)).doubleValue() * currentWeight;
156                 }
157             }
158  
159             //totalSum += currentPageRankSum;
160596            totalSum += currentPageRankSum * (1.0 - mAlpha) + mAlpha * getPriorRankScore(currentVertex);
161596            setRankScore(currentVertex, currentPageRankSum * (1.0 - mAlpha) + mAlpha * getPriorRankScore(currentVertex));
162         }
163  
164149        if (!NumericalPrecision.equal(totalSum, 1, .05)) {
1650            System.err.println("Page rank scores can not be generated because the specified graph is not connected.");
1660            System.out.println(totalSum);
167         }
168149    }
169  
170     protected double evaluateIteration() {
171149        updateRankings();
172  
173149        double rankingMSE = 0;
174  
175         //Normalize rankings and test for convergence
176149        for (Iterator vIt = mReachableVertices.iterator(); vIt.hasNext();) {
177596            Vertex currentVertex = (Vertex) vIt.next();
178596            MutableDouble previousRankScore = (MutableDouble) mPreviousRankingsMap.get(currentVertex);
179596            rankingMSE += Math.pow(getRankScore(currentVertex) - previousRankScore.doubleValue(), 2);
180596            previousRankScore.setDoubleValue(getRankScore(currentVertex));
181         }
182  
183149        rankingMSE = Math.pow(rankingMSE / getVertices().size(), 0.5);
184  
185149        return rankingMSE;
186     }
187  
188     /**
189      * The user datum key used to store the rank scores.
190      * @return the key
191      */
192     public String getRankScoreKey() {
1931866        return KEY;
194     }
195  
196 }

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.