Class RandomWalkSTBetweenness<V,​E>

  • All Implemented Interfaces:
    IterativeContext
    Direct Known Subclasses:
    RandomWalkBetweenness

    public class RandomWalkSTBetweenness<V,​E>
    extends AbstractRanker<V,​E>
    /** Computes s-t betweenness centrality for each vertex in the graph. The betweenness values in this case are based on random walks, measuring the expected number of times a node is traversed by a random walk from s to t. The result is that each vertex has a UserData element of type MutableDouble whose key is 'centrality.RandomWalkBetweennessCentrality' A simple example of usage is:
    RandomWalkSTBetweenness ranker = new RandomWalkBetweenness(someGraph,someSource,someTarget);
    ranker.evaluate();
    ranker.printRankings();

    Running time is: O(n^3).

    See Also:
    "Mark Newman: A measure of betweenness centrality based on random walks, 2002."
    • Constructor Detail

      • RandomWalkSTBetweenness

        public RandomWalkSTBetweenness​(edu.uci.ics.jung.graph.UndirectedGraph<V,​E> g,
                                       V s,
                                       V t)
        Constructor which initializes the algorithm
        Parameters:
        g - the graph whose nodes are to be analyzed
        s - the source vertex
        t - the target vertex
    • Method Detail

      • getIndexer

        protected org.apache.commons.collections4.BidiMap<V,​java.lang.Integer> getIndexer()
      • getVoltageMatrix

        protected cern.colt.matrix.DoubleMatrix2D getVoltageMatrix()
      • setUp

        protected void setUp()
      • computeBetweenness

        protected void computeBetweenness()
      • computeSTBetweenness

        public double computeSTBetweenness​(V ithVertex,
                                           V source,
                                           V target)
      • getRankScoreKey

        public java.lang.String getRankScoreKey()
        the user datum key used to store the rank scores
        Specified by:
        getRankScoreKey in class AbstractRanker<V,​E>
        Returns:
        the key