Class WeightedNIPaths<V,​E>

  • All Implemented Interfaces:
    IterativeContext

    public class WeightedNIPaths<V,​E>
    extends AbstractRanker<V,​E>
    This algorithm measures the importance of nodes based upon both the number and length of disjoint paths that lead to a given node from each of the nodes in the root set. Specifically the formula for measuring the importance of a node is given by: I(t|R) = sum_i=1_|P(r,t)|_{alpha^|p_i|} where alpha is the path decay coefficient, p_i is path i and P(r,t) is a set of maximum-sized node-disjoint paths from r to t.

    This algorithm uses heuristic breadth-first search to try and find the maximum-sized set of node-disjoint paths between two nodes. As such, it is not guaranteed to give exact answers.

    A simple example of usage is:

     WeightedNIPaths ranker = new WeightedNIPaths(someGraph,2.0,6,rootSet);
     ranker.evaluate();
     ranker.printRankings();
     
    See Also:
    "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"
    • Field Detail

      • WEIGHTED_NIPATHS_KEY

        public static final java.lang.String WEIGHTED_NIPATHS_KEY
        See Also:
        Constant Field Values
      • mAlpha

        private double mAlpha
      • mMaxDepth

        private int mMaxDepth
      • mPriors

        private java.util.Set<V> mPriors
      • pathIndices

        private java.util.Map<E,​java.lang.Number> pathIndices
      • roots

        private java.util.Map<java.lang.Object,​V> roots
      • pathsSeenMap

        private java.util.Map<V,​java.util.Set<java.lang.Number>> pathsSeenMap
      • vertexFactory

        private com.google.common.base.Supplier<V> vertexFactory
      • edgeFactory

        private com.google.common.base.Supplier<E> edgeFactory
    • Constructor Detail

      • WeightedNIPaths

        public WeightedNIPaths​(DirectedGraph<V,​E> graph,
                               com.google.common.base.Supplier<V> vertexFactory,
                               com.google.common.base.Supplier<E> edgeFactory,
                               double alpha,
                               int maxDepth,
                               java.util.Set<V> priors)
        Constructs and initializes the algorithm.
        Parameters:
        graph - the graph whose nodes are being measured for their importance
        vertexFactory - used to generate instances of V
        edgeFactory - used to generate instances of E
        alpha - the path decay coefficient (≥1); 2 is recommended
        maxDepth - the maximal depth to search out from the root set
        priors - the root set (starting vertices)
    • Method Detail

      • incrementRankScore

        protected void incrementRankScore​(V v,
                                          double rankValue)
      • computeWeightedPathsFromSource

        protected void computeWeightedPathsFromSource​(V root,
                                                      int depth)
      • newVertexEncountered

        private void newVertexEncountered​(int sourcePathIndex,
                                          V dest,
                                          V root)
      • getRankScoreKey

        public java.lang.String getRankScoreKey()
        Given a node, returns the corresponding rank score. This implementation of getRankScore assumes the decoration representing the rank score is of type MutableDouble.
        Specified by:
        getRankScoreKey in class AbstractRanker<V,​E>
        Returns:
        the rank score for this node