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