/* * Created on Jul 12, 2007 * * Copyright (c) 2007, the JUNG Project and the Regents of the University * of California * All rights reserved. * * This software is open-source under the BSD license; see either * "license.txt" or * http://jung.sourceforge.net/license.txt for a description. */ package edu.uci.ics.jung.algorithms.scoring; import org.apache.commons.collections15.Transformer; 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