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

   1 /*
   2  * Created on Jul 12, 2007
   3  *
   4  * Copyright (c) 2007, the JUNG Project and the Regents of the University
   5  * of California
   6  * All rights reserved.
   7  *
   8  * This software is open-source under the BSD license; see either
   9  * "license.txt" or
  10  * http://jung.sourceforge.net/license.txt for a description.
  11  */
  12 package edu.uci.ics.jung.algorithms.scoring;
  13
  14 import org.apache.commons.collections15.Transformer;
  15
  16 import edu.uci.ics.jung.algorithms.scoring.util.ScoringUtils;
  17 import edu.uci.ics.jung.graph.Hypergraph;
  18
  19 /**
  20  * Assigns scores to each vertex according to the PageRank algorithm.
  21  *
  22  * <p>PageRank is an eigenvector-based algorithm.  The score for a given vertex may be thought of
  23  * as the fraction of time spent 'visiting' that vertex (measured over all time)
  24  * in a random walk over the vertices (following outgoing edges from each vertex).
  25  * PageRank modifies this random walk by adding to the model a probability (specified as 'alpha'
  26  * in the constructor) of jumping to any vertex.  If alpha is 0, this is equivalent to the
  27  * eigenvector centrality algorithm; if alpha is 1, all vertices will receive the same score
  28  * (1/|V|).  Thus, alpha acts as a sort of score smoothing parameter.
  29  *
  30  * <p>The original algorithm assumed that, for a given vertex, the probability of following any
  31  * outgoing edge was the same; this is the default if edge weights are not specified.
  32  * This implementation generalizes the original by permitting
  33  * the user to specify edge weights; in order to maintain the original semantics, however,
  34  * the weights on the outgoing edges for a given vertex must represent transition probabilities;
  35  * that is, they must sum to 1.
  36  *
  37  * <p>If a vertex has no outgoing edges, then the probability of taking a random jump from that
  38  * vertex is (by default) effectively 1.  If the user wishes to instead throw an exception when this happens,
  39  * call <code>acceptDisconnectedGraph(false)</code> on this instance.
  40  *
  41  * <p>Typical values for alpha (according to the original paper) are in the range [0.1, 0.2]
  42  * but may be any value between 0 and 1 inclusive.
  43  *
  44  * @see "The Anatomy of a Large-Scale Hypertextual Web Search Engine by L. Page and S. Brin, 1999"
  45  */
  46 public class PageRank<V,E> extends PageRankWithPriors<V,E>
  47 {
  48
  49     /**
  50      * Creates an instance for the specified graph, edge weights, and random jump probability.
  51      * @param graph the input graph
  52      * @param edge_weight the edge weights (transition probabilities)
  53      * @param alpha the probability of taking a random jump to an arbitrary vertex
  54      */
  55     public PageRank(Hypergraph<V,E> graph, Transformer<E, ? extends Number> edge_weight, double alpha)
  56     {
  57         super(graph, edge_weight, ScoringUtils.getUniformRootPrior(graph.getVertices()), alpha);
  58     }
  59
  60     /**
  61      * Creates an instance for the specified graph and random jump probability; the probability
  62      * of following any outgoing edge from a given vertex is the same.
  63      * @param graph the input graph
  64      * @param alpha the probability of taking a random jump to an arbitrary vertex
  65      */
  66     public PageRank(Hypergraph<V,E> graph, double alpha)
  67     {
  68         super(graph, ScoringUtils.getUniformRootPrior(graph.getVertices()), alpha);
  69     }
  70 }