| 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. |