\HeaderA{page.rank}{The Page Rank algorithm}{page.rank}
\methaliasA{page.rank.old}{page.rank}{page.rank.old}
\keyword{graphs}{page.rank}
\begin{Description}\relax
Calculates the Google PageRank for the specified
vertices.
\end{Description}
\begin{Usage}
\begin{verbatim}
page.rank (graph, vids = V(graph), directed = TRUE, damping = 0.85, 
    weights = NULL, options = igraph.arpack.default) 
page.rank.old (graph, vids = V(graph), directed = TRUE, niter = 1000, 
    eps = 0.001, damping = 0.85, old = FALSE) 
\end{verbatim}
\end{Usage}
\begin{Arguments}
\begin{ldescription}
\item[\code{graph}] The graph object. 
\item[\code{vids}] The vertices of interest.
\item[\code{directed}] Logical, if true directed paths will be considered for
directed graphs. It is ignored for undirected graphs.
\item[\code{damping}] The damping factor (\sQuote{d} in the original paper).
\item[\code{weights}] A numerical vector or \code{NULL}. This argument can be
used to give edge weights for calculating the weighted PageRank of
vertices. If this is \code{NULL} and the graph has a \code{weight}
edge attribute then that is used. If \code{weights} is a numerical
vector then it used, even if the graph has a \code{weights} edge
attribute. If this is \code{NA}, then no edge weights are used (even
if the graph has a \code{weight} edge attribute.
\item[\code{options}] A named list, to override some ARPACK options. See
\code{\LinkA{arpack}{arpack}} for details.
\item[\code{niter}] The maximum number of iterations to perform.
\item[\code{eps}] The algorithm will consider the calculation as complete if
the difference of PageRank values between iterations change less
than this value for every node.
\item[\code{old}] A logical scalar, whether the old style (pre igraph 0.5)
normalization to use. See details below.
\end{ldescription}
\end{Arguments}
\begin{Details}\relax
For the explanation of the PageRank algorithm, see the following
webpage: \url{http://www-db.stanford.edu/~backrub/google.html}, or the
following reference: 

Sergey Brin and Larry Page: The Anatomy of a Large-Scale Hypertextual
Web Search Engine. Proceedings of the 7th World-Wide Web Conference,
Brisbane, Australia, April 1998.  

igraph 0.5 (and later) contains two PageRank calculation
implementations. The \code{page.rank} function uses ARPACK to perform
the calculation, see also \code{\LinkA{arpack}{arpack}}.

The \code{page.rank.old} function performs a simple power method, this
is the implementation that was available under the name
\code{page.rank} in pre 0.5 igraph versions. Note that
\code{page.rank.old} has an argument called \code{old}. If this
argument is \code{FALSE} (the default), then the proper PageRank
algorithm is used, i.e. \eqn{(1-d)/n}{} is added to the weighted
PageRank of vertices to calculate the next iteration. If this
argument is \code{TRUE} then \eqn{(1-d)}{} is added, just like in the
PageRank paper; \eqn{d}{} is the damping factor, and \eqn{n}{} is the
total number of vertices.
A further difference is that the old implementation does not
renormalize the page rank vector after each iteration.
Note that the \code{old=FALSE} method is not stable,
is does not necessarily converge to a fixed point. It should be
avoided for new code, it is only included for compatibility with old
igraph versions.

Please note that the PageRank of a given vertex depends on the PageRank
of all other vertices, so even if you want to calculate the PageRank for
only some of the vertices, all of them must be calculated. Requesting
the PageRank for only some of the vertices does not result in any
performance increase at all. 

Since the calculation is an iterative process, the algorithm is
stopped after a given count of iterations or if the PageRank value
differences between iterations are less than a predefined value.
\end{Details}
\begin{Value}
For \code{page.rank} a named list with entries:
\begin{ldescription}
\item[\code{vector}] A numeric vector with the PageRank scores.
\item[\code{value}] The eigenvalue corresponding to the eigenvector with
the page rank scores. It should be always exactly one.
\item[\code{options}] Some information about the underlying ARPACK
calculation. See \code{\LinkA{arpack}{arpack}} for details.
\end{ldescription}


For \code{page.rank.old} a numeric vector of Page Rank scores.
\end{Value}
\begin{Author}\relax
Tamas Nepusz \email{ntamas@rmki.kfki.hu} and
Gabor Csardi \email{csardi@rmki.kfki.hu}
\end{Author}
\begin{References}\relax
Sergey Brin and Larry Page: The Anatomy of a Large-Scale Hypertextual
Web Search Engine. Proceedings of the 7th World-Wide Web Conference,
Brisbane, Australia, April 1998.
\end{References}
\begin{SeeAlso}\relax
Other centrality scores: \code{\LinkA{closeness}{closeness}},
\code{\LinkA{betweenness}{betweenness}}, \code{\LinkA{degree}{degree}}
\end{SeeAlso}
\begin{Examples}
\begin{ExampleCode}
g <- random.graph.game(20, 5/20, directed=TRUE)
page.rank(g)$vector

g2 <- graph.star(10)
page.rank(g2)$vector
\end{ExampleCode}
\end{Examples}

