2 * Copyright (c) 2003, the JUNG Project and the Regents of the University
6 * This software is open-source under the BSD license; see either
8 * http://jung.sourceforge.net/license.txt for a description.
10 package edu.uci.ics.jung.algorithms.importance;
12 import java.util.Collection;
13 import java.util.HashMap;
17 import edu.uci.ics.jung.graph.DirectedGraph;
21 * Algorithm variant of <code>PageRankWithPriors</code> that computes the importance of a node based upon taking fixed-length random
22 * walks out from the root set and then computing the stationary probability of being at each node. Specifically, it computes
23 * the relative probability that the markov chain will spend at any particular node, given that it start in the root
24 * set and ends after k steps.
26 * A simple example of usage is:
28 * KStepMarkov ranker = new KStepMarkov(someGraph,rootSet,6,null);
30 * ranker.printRankings();
35 * @author Tom Nelson - adapter to jung2
36 * @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"
38 public class KStepMarkov<V,E> extends RelativeAuthorityRanker<V,E> {
39 public final static String RANK_SCORE = "jung.algorithms.importance.KStepMarkovExperimental.RankScore";
40 private final static String CURRENT_RANK = "jung.algorithms.importance.KStepMarkovExperimental.CurrentRank";
41 private int mNumSteps;
42 HashMap<V,Number> mPreviousRankingsMap;
45 * Construct the algorihm instance and initializes the algorithm.
46 * @param graph the graph to be analyzed
47 * @param priors the set of root nodes
48 * @param k positive integer parameter which controls the relative tradeoff between a distribution "biased" towards
49 * R and the steady-state distribution which is independent of where the Markov-process started. Generally values
50 * between 4-8 are reasonable
51 * @param edgeWeights the weight for each edge
53 public KStepMarkov(DirectedGraph<V,E> graph, Set<V> priors, int k, Map<E,Number> edgeWeights) {
54 super.initialize(graph,true,false);
58 if (edgeWeights == null) {
59 assignDefaultEdgeTransitionWeights();
61 setEdgeWeights(edgeWeights);
63 normalizeEdgeTransitionWeights();
67 * The user datum key used to store the rank scores.
71 public String getRankScoreKey() {
75 protected void incrementRankScore(V v, double rankValue) {
76 double value = getVertexRankScore(v, RANK_SCORE);
78 setVertexRankScore(v, value, RANK_SCORE);
81 protected double getCurrentRankScore(V v) {
82 return getVertexRankScore(v, CURRENT_RANK);
85 protected void setCurrentRankScore(V v, double rankValue) {
86 setVertexRankScore(v, rankValue, CURRENT_RANK);
89 protected void initializeRankings() {
90 mPreviousRankingsMap = new HashMap<V,Number>();
91 for (V v : getVertices()) {
92 Set<V> priors = getPriors();
93 double numPriors = priors.size();
95 if (getPriors().contains(v)) {
96 setVertexRankScore(v, 1.0/ numPriors);
97 setCurrentRankScore(v, 1.0/ numPriors);
98 mPreviousRankingsMap.put(v,1.0/numPriors);
100 setVertexRankScore(v, 0);
101 setCurrentRankScore(v, 0);
102 mPreviousRankingsMap.put(v, 0);
109 for (int i=0;i<mNumSteps;i++) {
111 for (V v : getVertices()) {
112 double currentRankScore = getCurrentRankScore(v);
113 incrementRankScore(v,currentRankScore);
114 mPreviousRankingsMap.put(v, currentRankScore);
120 protected void updateRankings() {
122 for (V v : getVertices()) {
124 Collection<E> incomingEdges = getGraph().getInEdges(v);
126 double currentPageRankSum = 0;
127 for (E e : incomingEdges) {
128 double currentWeight = getEdgeWeight(e);
129 currentPageRankSum +=
130 mPreviousRankingsMap.get(getGraph().getOpposite(v,e)).doubleValue()*currentWeight;
132 setCurrentRankScore(v,currentPageRankSum);