Coverage details for edu.uci.ics.jung.algorithms.importance.KStepMarkov

LineHitsSource
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      */
551    public KStepMarkov(DirectedGraph graph, Set priors, int k, String edgeWeightKeyName) {
561        super.initialize(graph,true,false);
571        mNumSteps = k;
581        setPriors(priors);
591        initializeRankings();
601        if (edgeWeightKeyName == null) {
610            assignDefaultEdgeTransitionWeights();
62         } else {
631            setUserDefinedEdgeWeightKey(edgeWeightKeyName);
64         }
651        normalizeEdgeTransitionWeights();
661    }
67  
68     /**
69      * The user datum key used to store the rank scores.
70      * @return the key
71      */
72     public String getRankScoreKey() {
7321        return RANK_SCORE;
74     }
75  
76     protected void incrementRankScore(Element v, double rankValue) {
776        MutableDouble value = (MutableDouble) v.getUserDatum(RANK_SCORE);
78  
796        value.add(rankValue);
806    }
81  
82     protected double getCurrentRankScore(Element v) {
836        return ((MutableDouble) v.getUserDatum(CURRENT_RANK)).doubleValue();
84     }
85  
86     protected void setCurrentRankScore(Element v, double rankValue) {
879        MutableDouble value = (MutableDouble) v.getUserDatum(CURRENT_RANK);
88  
899        if (value == null) {
903            v.setUserDatum(CURRENT_RANK,new MutableDouble(rankValue),UserData.SHARED);
91         } else {
926            value.setDoubleValue(rankValue);
93         }
949    }
95  
96     protected void initializeRankings() {
971         mPreviousRankingsMap = new HashMap();
981         for (Iterator vIt = getVertices().iterator();vIt.hasNext();) {
993            Vertex currentVertex = (Vertex) vIt.next();
1003            Set priors = getPriors();
1013            double numPriors = priors.size();
102  
1033            if (getPriors().contains(currentVertex)) {
1042                setRankScore(currentVertex, 1.0/ numPriors);
1052                setCurrentRankScore(currentVertex, 1.0/ numPriors);
1062                mPreviousRankingsMap.put(currentVertex,new MutableDouble(1.0/numPriors));
107             } else {
1081                setRankScore(currentVertex, 0);
1091                setCurrentRankScore(currentVertex, 0);
1101                mPreviousRankingsMap.put(currentVertex,new MutableDouble(0));
111  
112             }
113         }
1141     }
115     protected double evaluateIteration() {
116  
1173        for (int i=0;i<mNumSteps;i++) {
1182            updateRankings();
1192            for (Iterator vIt = getVertices().iterator(); vIt.hasNext();) {
1206                Vertex currentVertex = (Vertex) vIt.next();
1216                double currentRankScore = getCurrentRankScore(currentVertex);
1226                MutableDouble previousRankScore = (MutableDouble) mPreviousRankingsMap.get(currentVertex);
1236                incrementRankScore(currentVertex,currentRankScore);
1246                previousRankScore.setDoubleValue(currentRankScore);
125             }
126         }
127  
1281        normalizeRankings();
129  
1301        return 0;
131     }
132  
133     protected void onFinalize(Element udc) {
1343        udc.removeUserDatum(CURRENT_RANK);
135  
1363    }
137  
138     protected void updateRankings() {
139  
1402        for (Iterator vIt = getVertices().iterator(); vIt.hasNext();) {
1416            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 // }
1496            Set incomingEdges = currentVertex.getInEdges();
150  
1516            double currentPageRankSum = 0;
1526            for (Iterator edgeIt = incomingEdges.iterator(); edgeIt.hasNext();) {
15312                Edge incomingEdge = (Edge) edgeIt.next();
15412                double currentWeight = getEdgeWeight(incomingEdge);
15512                currentPageRankSum += ((MutableDouble) mPreviousRankingsMap.get(incomingEdge.getOpposite(currentVertex))).doubleValue()*currentWeight;
156             }
157  
1586            setCurrentRankScore(currentVertex,currentPageRankSum);
159         }
160  
1612    }
162 }

this report was generated by version 1.0.5 of jcoverage.
visit www.jcoverage.com for updates.

copyright © 2003, jcoverage ltd. all rights reserved.
Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.