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.Iterator; | |
14 | import java.util.Set; | |
15 | ||
16 | import edu.uci.ics.jung.graph.DirectedGraph; | |
17 | import edu.uci.ics.jung.graph.Edge; | |
18 | import edu.uci.ics.jung.graph.Element; | |
19 | import edu.uci.ics.jung.graph.Vertex; | |
20 | import edu.uci.ics.jung.utils.MutableDouble; | |
21 | import edu.uci.ics.jung.utils.UserData; | |
22 | ||
23 | /** | |
24 | * Algorithm variant of <code>PageRankWithPriors</code> that computes the importance of a node based upon taking fixed-length random | |
25 | * walks out from the root set and then computing the stationary probability of being at each node. Specifically, it computes | |
26 | * the relative probability that the markov chain will spend at any particular node, given that it start in the root | |
27 | * set and ends after k steps. | |
28 | * <p> | |
29 | * A simple example of usage is: | |
30 | * <pre> | |
31 | * KStepMarkov ranker = new KStepMarkov(someGraph,rootSet,6,null); | |
32 | * ranker.evaluate(); | |
33 | * ranker.printRankings(); | |
34 | * </pre> | |
35 | * <p> | |
36 | * | |
37 | * @author Scott White | |
38 | * @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003" | |
39 | */ | |
40 | public class KStepMarkov extends RelativeAuthorityRanker { | |
41 | public final static String RANK_SCORE = "jung.algorithms.importance.KStepMarkovExperimental.RankScore"; | |
42 | private final static String CURRENT_RANK = "jung.algorithms.importance.KStepMarkovExperimental.CurrentRank"; | |
43 | private int mNumSteps; | |
44 | HashMap mPreviousRankingsMap; | |
45 | ||
46 | /** | |
47 | * Construct the algorihm instance and initializes the algorithm. | |
48 | * @param graph the graph to be analyzed | |
49 | * @param priors the set of root nodes | |
50 | * @param k positive integer parameter which controls the relative tradeoff between a distribution "biased" towards | |
51 | * R and the steady-state distribution which is independent of where the Markov-process started. Generally values | |
52 | * between 4-8 are reasonable | |
53 | * @param edgeWeightKeyName | |
54 | */ | |
55 | 1 | public KStepMarkov(DirectedGraph graph, Set priors, int k, String edgeWeightKeyName) { |
56 | 1 | super.initialize(graph,true,false); |
57 | 1 | mNumSteps = k; |
58 | 1 | setPriors(priors); |
59 | 1 | initializeRankings(); |
60 | 1 | if (edgeWeightKeyName == null) { |
61 | 0 | assignDefaultEdgeTransitionWeights(); |
62 | } else { | |
63 | 1 | setUserDefinedEdgeWeightKey(edgeWeightKeyName); |
64 | } | |
65 | 1 | normalizeEdgeTransitionWeights(); |
66 | 1 | } |
67 | ||
68 | /** | |
69 | * The user datum key used to store the rank scores. | |
70 | * @return the key | |
71 | */ | |
72 | public String getRankScoreKey() { | |
73 | 21 | return RANK_SCORE; |
74 | } | |
75 | ||
76 | protected void incrementRankScore(Element v, double rankValue) { | |
77 | 6 | MutableDouble value = (MutableDouble) v.getUserDatum(RANK_SCORE); |
78 | ||
79 | 6 | value.add(rankValue); |
80 | 6 | } |
81 | ||
82 | protected double getCurrentRankScore(Element v) { | |
83 | 6 | return ((MutableDouble) v.getUserDatum(CURRENT_RANK)).doubleValue(); |
84 | } | |
85 | ||
86 | protected void setCurrentRankScore(Element v, double rankValue) { | |
87 | 9 | MutableDouble value = (MutableDouble) v.getUserDatum(CURRENT_RANK); |
88 | ||
89 | 9 | if (value == null) { |
90 | 3 | v.setUserDatum(CURRENT_RANK,new MutableDouble(rankValue),UserData.SHARED); |
91 | } else { | |
92 | 6 | value.setDoubleValue(rankValue); |
93 | } | |
94 | 9 | } |
95 | ||
96 | protected void initializeRankings() { | |
97 | 1 | mPreviousRankingsMap = new HashMap(); |
98 | 1 | for (Iterator vIt = getVertices().iterator();vIt.hasNext();) { |
99 | 3 | Vertex currentVertex = (Vertex) vIt.next(); |
100 | 3 | Set priors = getPriors(); |
101 | 3 | double numPriors = priors.size(); |
102 | ||
103 | 3 | if (getPriors().contains(currentVertex)) { |
104 | 2 | setRankScore(currentVertex, 1.0/ numPriors); |
105 | 2 | setCurrentRankScore(currentVertex, 1.0/ numPriors); |
106 | 2 | mPreviousRankingsMap.put(currentVertex,new MutableDouble(1.0/numPriors)); |
107 | } else { | |
108 | 1 | setRankScore(currentVertex, 0); |
109 | 1 | setCurrentRankScore(currentVertex, 0); |
110 | 1 | mPreviousRankingsMap.put(currentVertex,new MutableDouble(0)); |
111 | ||
112 | } | |
113 | } | |
114 | 1 | } |
115 | protected double evaluateIteration() { | |
116 | ||
117 | 3 | for (int i=0;i<mNumSteps;i++) { |
118 | 2 | updateRankings(); |
119 | 2 | for (Iterator vIt = getVertices().iterator(); vIt.hasNext();) { |
120 | 6 | Vertex currentVertex = (Vertex) vIt.next(); |
121 | 6 | double currentRankScore = getCurrentRankScore(currentVertex); |
122 | 6 | MutableDouble previousRankScore = (MutableDouble) mPreviousRankingsMap.get(currentVertex); |
123 | 6 | incrementRankScore(currentVertex,currentRankScore); |
124 | 6 | previousRankScore.setDoubleValue(currentRankScore); |
125 | } | |
126 | } | |
127 | ||
128 | 1 | normalizeRankings(); |
129 | ||
130 | 1 | return 0; |
131 | } | |
132 | ||
133 | protected void onFinalize(Element udc) { | |
134 | 3 | udc.removeUserDatum(CURRENT_RANK); |
135 | ||
136 | 3 | } |
137 | ||
138 | protected void updateRankings() { | |
139 | ||
140 | 2 | for (Iterator vIt = getVertices().iterator(); vIt.hasNext();) { |
141 | 6 | Vertex currentVertex = (Vertex) vIt.next(); |
142 | ||
143 | // Set incomingEdges = null; | |
144 | // if (getGraph().isDirected()) { | |
145 | // incomingEdges = currentVertex.getInEdges(); | |
146 | // } else { | |
147 | // incomingEdges = currentVertex.getIncidentEdges(); | |
148 | // } | |
149 | 6 | Set incomingEdges = currentVertex.getInEdges(); |
150 | ||
151 | 6 | double currentPageRankSum = 0; |
152 | 6 | for (Iterator edgeIt = incomingEdges.iterator(); edgeIt.hasNext();) { |
153 | 12 | Edge incomingEdge = (Edge) edgeIt.next(); |
154 | 12 | double currentWeight = getEdgeWeight(incomingEdge); |
155 | 12 | currentPageRankSum += ((MutableDouble) mPreviousRankingsMap.get(incomingEdge.getOpposite(currentVertex))).doubleValue()*currentWeight; |
156 | } | |
157 | ||
158 | 6 | setCurrentRankScore(currentVertex,currentPageRankSum); |
159 | } | |
160 | ||
161 | 2 | } |
162 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |