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 Details

    • WEIGHTED_NIPATHS_KEY

      public static final String WEIGHTED_NIPATHS_KEY
      See Also:
    • mAlpha

      private double mAlpha
    • mMaxDepth

      private int mMaxDepth
    • mPriors

      private Set<V> mPriors
    • pathIndices

      private Map<E,Number> pathIndices
    • roots

      private Map<Object,V> roots
    • pathsSeenMap

      private Map<V,Set<Number>> pathsSeenMap
    • vertexFactory

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

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

    • 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, 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 Details

    • 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)
    • step

      public void step()
      Description copied from class: IterativeProcess
      Evaluate the result of the current iteration.
      Specified by:
      step in interface IterativeContext
      Specified by:
      step in class IterativeProcess
    • getRankScoreKey

      public 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
    • onFinalize

      protected void onFinalize(Object udc)
      Overrides:
      onFinalize in class AbstractRanker<V,E>