/*
* Created on Jul 12, 2007
*
* Copyright (c) 2007, The JUNG Authors
*
* All rights reserved.
*
* This software is open-source under the BSD license; see either
* "license.txt" or
* https://github.com/jrtom/jung/blob/master/LICENSE for a description.
*/
package edu.uci.ics.jung.algorithms.scoring;
import com.google.common.base.Function;
import edu.uci.ics.jung.algorithms.scoring.util.ScoringUtils;
import edu.uci.ics.jung.graph.Hypergraph;
/**
* Assigns scores to each vertex according to the PageRank algorithm.
*
* PageRank is an eigenvector-based algorithm. The score for a given vertex may be thought of
* as the fraction of time spent 'visiting' that vertex (measured over all time)
* in a random walk over the vertices (following outgoing edges from each vertex).
* PageRank modifies this random walk by adding to the model a probability (specified as 'alpha'
* in the constructor) of jumping to any vertex. If alpha is 0, this is equivalent to the
* eigenvector centrality algorithm; if alpha is 1, all vertices will receive the same score
* (1/|V|). Thus, alpha acts as a sort of score smoothing parameter.
*
*
The original algorithm assumed that, for a given vertex, the probability of following any
* outgoing edge was the same; this is the default if edge weights are not specified.
* This implementation generalizes the original by permitting
* the user to specify edge weights; in order to maintain the original semantics, however,
* the weights on the outgoing edges for a given vertex must represent transition probabilities;
* that is, they must sum to 1.
*
*
If a vertex has no outgoing edges, then the probability of taking a random jump from that
* vertex is (by default) effectively 1. If the user wishes to instead throw an exception when this happens,
* call acceptDisconnectedGraph(false) on this instance.
*
*
Typical values for alpha (according to the original paper) are in the range [0.1, 0.2]
* but may be any value between 0 and 1 inclusive.
*
* @see "The Anatomy of a Large-Scale Hypertextual Web Search Engine by L. Page and S. Brin, 1999"
*/
public class PageRank extends PageRankWithPriors
{
/**
* Creates an instance for the specified graph, edge weights, and random jump probability.
* @param graph the input graph
* @param edge_weight the edge weights (transition probabilities)
* @param alpha the probability of taking a random jump to an arbitrary vertex
*/
public PageRank(Hypergraph graph, Function edge_weight, double alpha)
{
super(graph, edge_weight, ScoringUtils.getUniformRootPrior(graph.getVertices()), alpha);
}
/**
* Creates an instance for the specified graph and random jump probability; the probability
* of following any outgoing edge from a given vertex is the same.
* @param graph the input graph
* @param alpha the probability of taking a random jump to an arbitrary vertex
*/
public PageRank(Hypergraph graph, double alpha)
{
super(graph, ScoringUtils.getUniformRootPrior(graph.getVertices()), alpha);
}
}
Ads help maintain this website.