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