third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/KStepMarkov.java

   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.Collection;
  13 import java.util.HashMap;
  14 import java.util.Map;
  15 import java.util.Set;
  16
  17 import edu.uci.ics.jung.graph.DirectedGraph;
  18
  19
  20 /**
  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.
  25  * <p>
  26  * A simple example of usage is:
  27  * <pre>
  28  * KStepMarkov ranker = new KStepMarkov(someGraph,rootSet,6,null);
  29  * ranker.evaluate();
  30  * ranker.printRankings();
  31  * </pre>
  32  * <p>
  33  *
  34  * @author Scott White
  35  * @author Tom Nelson - adapter to jung2
  36  * @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"
  37  */
  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;
  43
  44     /**
  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
  52      */
  53     public KStepMarkov(DirectedGraph<V,E> graph, Set<V> priors, int k, Map<E,Number> edgeWeights) {
  54         super.initialize(graph,true,false);
  55         mNumSteps = k;
  56         setPriors(priors);
  57         initializeRankings();
  58         if (edgeWeights == null) {
  59             assignDefaultEdgeTransitionWeights();
  60         } else {
  61             setEdgeWeights(edgeWeights);
  62         }
  63         normalizeEdgeTransitionWeights();
  64     }
  65
  66     /**
  67      * The user datum key used to store the rank scores.
  68      * @return the key
  69      */
  70     @Override
  71     public String getRankScoreKey() {
  72         return RANK_SCORE;
  73     }
  74
  75     protected void incrementRankScore(V v, double rankValue) {
  76         double value = getVertexRankScore(v, RANK_SCORE);
  77         value += rankValue;
  78         setVertexRankScore(v, value, RANK_SCORE);
  79     }
  80
  81     protected double getCurrentRankScore(V v) {
  82         return getVertexRankScore(v, CURRENT_RANK);
  83     }
  84
  85     protected void setCurrentRankScore(V v, double rankValue) {
  86         setVertexRankScore(v, rankValue, CURRENT_RANK);
  87     }
  88
  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();
  94
  95             if (getPriors().contains(v)) {
  96                 setVertexRankScore(v, 1.0/ numPriors);
  97                 setCurrentRankScore(v, 1.0/ numPriors);
  98                 mPreviousRankingsMap.put(v,1.0/numPriors);
  99             } else {
 100                 setVertexRankScore(v, 0);
 101                 setCurrentRankScore(v, 0);
 102                 mPreviousRankingsMap.put(v, 0);
 103             }
 104         }
 105      }
 106     @Override
 107     public void step() {
 108
 109         for (int i=0;i<mNumSteps;i++) {
 110             updateRankings();
 111             for (V v : getVertices()) {
 112                 double currentRankScore = getCurrentRankScore(v);
 113                 incrementRankScore(v,currentRankScore);
 114                 mPreviousRankingsMap.put(v, currentRankScore);
 115             }
 116         }
 117         normalizeRankings();
 118     }
 119
 120     protected void updateRankings() {
 121
 122         for (V v : getVertices()) {
 123
 124             Collection<E> incomingEdges = getGraph().getInEdges(v);
 125
 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;
 131             }
 132             setCurrentRankScore(v,currentPageRankSum);
 133         }
 134     }
 135 }