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

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.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 |  | `*/`
59 | 0 | `public PageRank(DirectedGraph graph, double bias) {`
60 | 0 | `initialize(graph, bias, null);`
61 | 0 | `initializeRankings(graph.getVertices(), new HashSet());`
62 | 0 | `}`
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 |  | `*/`
73 | 2 | `public PageRank(DirectedGraph graph, double bias, String edgeWeightKeyName) {`
74 | 2 | `initialize(graph, bias, edgeWeightKeyName);`
75 | 2 | `initializeRankings(graph.getVertices(), new HashSet());`
76 | 2 | `}`
77 |  | ``
78 | 2 | `protected PageRank(DirectedGraph graph, double bias, String edgeWeightKeyName, Pair reachables) {`
79 | 2 | `initialize(graph, bias, edgeWeightKeyName);`
80 | 2 | `initializeRankings((Set) reachables.getFirst(), (Set) reachables.getSecond());`
81 | 2 | `}`
82 |  | ``
83 |  | `protected void initialize(DirectedGraph graph, double bias, String edgeWeightKeyName) {`
84 | 4 | `super.initialize(graph, true, false);`
85 | 4 | `if ((bias < 0) || (bias > 1.0)) {`
86 | 0 | `throw new IllegalArgumentException("Bias " + bias + " must be between 0 and 1.");`
87 |  | `}`
88 | 4 | `mAlpha = bias;`
89 | 4 | `if (edgeWeightKeyName == null) {`
90 | 2 | `assignDefaultEdgeTransitionWeights();`
91 |  | `} else {`
92 | 2 | `setUserDefinedEdgeWeightKey(edgeWeightKeyName);`
93 | 2 | `normalizeEdgeTransitionWeights();`
94 |  | `}`
95 |  | ``
96 | 4 | `}`
97 |  | ``
98 |  | `protected void initializeRankings(Set reachableVertices, Set unreachableVertices) {`
99 |  | ``
100 | 4 | `mReachableVertices = reachableVertices;`
101 | 4 | `double numVertices = reachableVertices.size();`
102 | 4 | `mPreviousRankingsMap = new HashMap();`
103 | 4 | `mLeafNodes = new HashSet();`
104 | 4 | `for (Iterator vIt = mReachableVertices.iterator(); vIt.hasNext();) {`
105 | 16 | `Vertex currentVertex = (Vertex) vIt.next();`
106 | 16 | `setRankScore(currentVertex, 1.0 / numVertices);`
107 | 16 | `setPriorRankScore(currentVertex, 1.0 / numVertices);`
108 | 16 | `mPreviousRankingsMap.put(currentVertex, new MutableDouble(1.0 / numVertices));`
109 | 16 | `if (currentVertex.outDegree() == 0) {`
110 | 0 | `mLeafNodes.add(currentVertex);`
111 |  | `}`
112 |  | `}`
113 |  | ``
114 | 4 | `mUnreachableVertices = unreachableVertices;`
115 | 4 | `for (Iterator vIt = mUnreachableVertices.iterator(); vIt.hasNext();) {`
116 | 6 | `Vertex currentVertex = (Vertex) vIt.next();`
117 | 6 | `setRankScore(currentVertex, 0);`
118 | 6 | `setPriorRankScore(currentVertex, 0);`
119 | 6 | `mPreviousRankingsMap.put(currentVertex, new MutableDouble(0));`
120 |  | `}`
121 | 4 | `}`
122 |  | ``
123 |  | `protected void reinitialize() {`
124 | 0 | `initializeRankings(mReachableVertices, mUnreachableVertices);`
125 | 0 | `}`
126 |  | ``
127 |  | `protected void updateRankings() {`
128 | 149 | `double totalSum = 0;`
129 |  | ``
130 | 149 | `for (Iterator vIt = mReachableVertices.iterator(); vIt.hasNext();) {`
131 | 596 | `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 |  | `// }`
139 | 596 | `Set incomingEdges = currentVertex.getInEdges();`
140 |  | ``
141 | 596 | `double currentPageRankSum = 0;`
142 | 596 | `for (Iterator edgeIt = incomingEdges.iterator(); edgeIt.hasNext();) {`
143 | 751 | `Edge incomingEdge = (Edge) edgeIt.next();`
144 | 751 | `if (mUnreachableVertices.contains(incomingEdge.getOpposite(currentVertex)))`
145 | 0 | `continue;`
146 |  | ``
147 | 751 | `double currentWeight = getEdgeWeight(incomingEdge);`
148 | 751 | `currentPageRankSum += ((Number) mPreviousRankingsMap.get(incomingEdge.getOpposite(currentVertex))).doubleValue() * currentWeight;`
149 |  | `}`
150 |  | ``
151 | 596 | `if (getPriorRankScore(currentVertex) > 0) {`
152 | 454 | `for (Iterator leafIt = mLeafNodes.iterator(); leafIt.hasNext();) {`
153 | 0 | `Vertex leafNode = (Vertex) leafIt.next();`
154 | 0 | `double currentWeight = getPriorRankScore(currentVertex);`
155 | 0 | `currentPageRankSum += ((Number) mPreviousRankingsMap.get(leafNode)).doubleValue() * currentWeight;`
156 |  | `}`
157 |  | `}`
158 |  | ``
159 |  | `//totalSum += currentPageRankSum;`
160 | 596 | `totalSum += currentPageRankSum * (1.0 - mAlpha) + mAlpha * getPriorRankScore(currentVertex);`
161 | 596 | `setRankScore(currentVertex, currentPageRankSum * (1.0 - mAlpha) + mAlpha * getPriorRankScore(currentVertex));`
162 |  | `}`
163 |  | ``
164 | 149 | `if (!NumericalPrecision.equal(totalSum, 1, .05)) {`
165 | 0 | `System.err.println("Page rank scores can not be generated because the specified graph is not connected.");`
166 | 0 | `System.out.println(totalSum);`
167 |  | `}`
168 | 149 | `}`
169 |  | ``
170 |  | `protected double evaluateIteration() {`
171 | 149 | `updateRankings();`
172 |  | ``
173 | 149 | `double rankingMSE = 0;`
174 |  | ``
175 |  | `//Normalize rankings and test for convergence`
176 | 149 | `for (Iterator vIt = mReachableVertices.iterator(); vIt.hasNext();) {`
177 | 596 | `Vertex currentVertex = (Vertex) vIt.next();`
178 | 596 | `MutableDouble previousRankScore = (MutableDouble) mPreviousRankingsMap.get(currentVertex);`
179 | 596 | `rankingMSE += Math.pow(getRankScore(currentVertex) - previousRankScore.doubleValue(), 2);`
180 | 596 | `previousRankScore.setDoubleValue(getRankScore(currentVertex));`
181 |  | `}`
182 |  | ``
183 | 149 | `rankingMSE = Math.pow(rankingMSE / getVertices().size(), 0.5);`
184 |  | ``
185 | 149 | `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() {`
193 | 1866 | `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.