/*
* Copyright (c) 2003, The JUNG Authors 
*
* All rights reserved.
*
* This software is open-source under the BSD license; see either
* "license.txt" or
* https://github.com/jrtom/jung/blob/master/LICENSE for a description.
*/
package edu.uci.ics.jung.algorithms.importance;

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

import edu.uci.ics.jung.graph.DirectedGraph;


/**
 * Algorithm variant of PageRankWithPriors that computes the importance of a node based upon taking fixed-length random
 * walks out from the root set and then computing the stationary probability of being at each node. Specifically, it computes
 * the relative probability that the markov chain will spend at any particular node, given that it start in the root
 * set and ends after k steps.
 * 

* A simple example of usage is: *

 * KStepMarkov ranker = new KStepMarkov(someGraph,rootSet,6,null);
 * ranker.evaluate();
 * ranker.printRankings();
 * 
*

* * @author Scott White * @author Tom Nelson - adapter to jung2 * @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003" */ public class KStepMarkov extends RelativeAuthorityRanker { public final static String RANK_SCORE = "jung.algorithms.importance.KStepMarkovExperimental.RankScore"; private final static String CURRENT_RANK = "jung.algorithms.importance.KStepMarkovExperimental.CurrentRank"; private int mNumSteps; HashMap mPreviousRankingsMap; /** * Construct the algorihm instance and initializes the algorithm. * @param graph the graph to be analyzed * @param priors the set of root nodes * @param k positive integer parameter which controls the relative tradeoff between a distribution "biased" towards * R and the steady-state distribution which is independent of where the Markov-process started. Generally values * between 4-8 are reasonable * @param edgeWeights the weight for each edge */ public KStepMarkov(DirectedGraph graph, Set priors, int k, Map edgeWeights) { super.initialize(graph,true,false); mNumSteps = k; setPriors(priors); initializeRankings(); if (edgeWeights == null) { assignDefaultEdgeTransitionWeights(); } else { setEdgeWeights(edgeWeights); } normalizeEdgeTransitionWeights(); } /** * The user datum key used to store the rank scores. * @return the key */ @Override public String getRankScoreKey() { return RANK_SCORE; } protected void incrementRankScore(V v, double rankValue) { double value = getVertexRankScore(v, RANK_SCORE); value += rankValue; setVertexRankScore(v, value, RANK_SCORE); } protected double getCurrentRankScore(V v) { return getVertexRankScore(v, CURRENT_RANK); } protected void setCurrentRankScore(V v, double rankValue) { setVertexRankScore(v, rankValue, CURRENT_RANK); } protected void initializeRankings() { mPreviousRankingsMap = new HashMap(); for (V v : getVertices()) { Set priors = getPriors(); double numPriors = priors.size(); if (getPriors().contains(v)) { setVertexRankScore(v, 1.0/ numPriors); setCurrentRankScore(v, 1.0/ numPriors); mPreviousRankingsMap.put(v,1.0/numPriors); } else { setVertexRankScore(v, 0); setCurrentRankScore(v, 0); mPreviousRankingsMap.put(v, 0); } } } @Override public void step() { for (int i=0;i incomingEdges = getGraph().getInEdges(v); double currentPageRankSum = 0; for (E e : incomingEdges) { double currentWeight = getEdgeWeight(e); currentPageRankSum += mPreviousRankingsMap.get(getGraph().getOpposite(v,e)).doubleValue()*currentWeight; } setCurrentRankScore(v,currentPageRankSum); } } }

Ads help maintain this website.