| 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.HashSet; | |
| 13 | import java.util.Iterator; | |
| 14 | import java.util.Set; | |
| 15 | ||
| 16 | import edu.uci.ics.jung.algorithms.connectivity.BFSDistanceLabeler; | |
| 17 | import edu.uci.ics.jung.graph.DirectedGraph; | |
| 18 | import edu.uci.ics.jung.graph.Graph; | |
| 19 | import edu.uci.ics.jung.graph.Vertex; | |
| 20 | import edu.uci.ics.jung.utils.Pair; | |
| 21 | ||
| 22 | /** | |
| 23 | * Algorithm that extends the PageRank algorithm by incorporating root nodes (priors). Whereas in PageRank | |
| 24 | * the importance of a node is implicitly computed relative to all nodes in the graph now importance | |
| 25 | * is computed relative to the specified root nodes. | |
| 26 | * <p> | |
| 27 | * Note: This algorithm uses the same key as PageRank for storing rank sccores | |
| 28 | * <p> | |
| 29 | * A simple example of usage is: | |
| 30 | * <pre> | |
| 31 | * PageRankWithPriors ranker = new PageRankWithPriors(someGraph,0.3,1,rootSet,null); | |
| 32 | * ranker.evaluate(); | |
| 33 | * ranker.printRankings(); | |
| 34 | * </pre> | |
| 35 | * <p> | |
| 36 | * Running time: O(|E|*I) where |E| is the number of edges and I is the number of iterations until convergence | |
| 37 | * | |
| 38 | * @author Scott White | |
| 39 | * @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003" | |
| 40 | */ | |
| 41 | public class PageRankWithPriors extends PageRank { | |
| 42 | ||
| 43 | /** | |
| 44 | * Constructs an instance of the ranker. | |
| 45 | * @param graph the graph whose nodes are being ranked | |
| 46 | * @param beta the prior weight to put on the root nodes | |
| 47 | * @param priors the set of root nodes | |
| 48 | * @param edgeWeightKeyName the user datum key associated with any user-defined weights. If there are none, | |
| 49 | * null should be passed in. | |
| 50 | */ | |
| 51 | public PageRankWithPriors(DirectedGraph graph, double beta, Set priors, String edgeWeightKeyName) { | |
| 52 | 2 | super(graph, beta, edgeWeightKeyName,computeReachableVertices(graph,priors)); |
| 53 | 2 | setPriors(priors); |
| 54 | 2 | initializePriorWeights(); |
| 55 | 2 | } |
| 56 | ||
| 57 | protected void initializePriorWeights() { | |
| 58 | 2 | Set allVertices = getVertices(); |
| 59 | ||
| 60 | 2 | Set priors = getPriors(); |
| 61 | 2 | double numPriors = priors.size(); |
| 62 | ||
| 63 | 2 | Set nonPriors = new HashSet(); |
| 64 | 2 | nonPriors.addAll(allVertices); |
| 65 | 2 | nonPriors.removeAll(priors); |
| 66 | ||
| 67 | 2 | for (Iterator vIt = nonPriors.iterator(); vIt.hasNext();) { |
| 68 | 11 | Vertex currentVertex = (Vertex) vIt.next(); |
| 69 | 11 | setPriorRankScore(currentVertex, 0.0); |
| 70 | } | |
| 71 | ||
| 72 | 2 | for (Iterator vIt = getPriors().iterator(); vIt.hasNext();) { |
| 73 | 3 | Vertex currentVertex = (Vertex) vIt.next(); |
| 74 | 3 | setPriorRankScore(currentVertex, 1.0 / numPriors); |
| 75 | } | |
| 76 | 2 | } |
| 77 | ||
| 78 | private static Pair computeReachableVertices(Graph g, Set priors) { | |
| 79 | ||
| 80 | 2 | BFSDistanceLabeler labeler = new BFSDistanceLabeler("DISTANCE"); |
| 81 | 2 | labeler.labelDistances(g, priors); |
| 82 | 2 | labeler.removeDecorations(g); |
| 83 | 2 | Pair p = new Pair(new HashSet(labeler.getVerticesInOrderVisited()), |
| 84 | new HashSet(labeler.getUnivistedVertices())); | |
| 85 | ||
| 86 | 2 | return p; |
| 87 | } | |
| 88 | ||
| 89 | protected void reinitialize() { | |
| 90 | 0 | super.reinitialize(); |
| 91 | 0 | initializePriorWeights(); |
| 92 | 0 | } |
| 93 | } |
|
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |