102 lines
3.4 KiB
ReStructuredText
102 lines
3.4 KiB
ReStructuredText
.. Copyright (C) 2004-2008 The Trustees of Indiana University.
|
|
Use, modification and distribution is subject to the Boost Software
|
|
License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
|
|
http://www.boost.org/LICENSE_1_0.txt)
|
|
|
|
===============
|
|
|Logo| PageRank
|
|
===============
|
|
|
|
::
|
|
|
|
namespace graph {
|
|
template<typename Graph, typename RankMap, typename Done>
|
|
inline void
|
|
page_rank(const Graph& g, RankMap rank_map, Done done,
|
|
typename property_traits<RankMap>::value_type damping = 0.85);
|
|
|
|
template<typename Graph, typename RankMap>
|
|
inline void
|
|
page_rank(const Graph& g, RankMap rank_map);
|
|
}
|
|
|
|
The ``page_rank`` algorithm computes the ranking of vertices in a
|
|
graph, based on the connectivity of a directed graph [PBMW98]_. The
|
|
idea of PageRank is based on a random model of a Web surfer, who
|
|
starts a random web page and then either follows a link from that web
|
|
page (choosing from the links randomly) or jumps to a completely
|
|
different web page (not necessarily linked from the current
|
|
page). The PageRank of each page is the probability of the random web
|
|
surfer visiting that page.
|
|
|
|
.. contents::
|
|
|
|
Where Defined
|
|
~~~~~~~~~~~~~
|
|
<``boost/graph/distributed/page_rank.hpp``>
|
|
|
|
also accessible from
|
|
|
|
<``boost/graph/page_rank.hpp``>
|
|
|
|
Parameters
|
|
~~~~~~~~~~
|
|
|
|
IN: ``Graph& g``
|
|
The graph type must be a model of `Distributed Vertex List Graph`_ and
|
|
`Distributed Edge List Graph`_. The graph must be directed.
|
|
|
|
OUT: ``RankMap rank``
|
|
Stores the rank of each vertex. The type ``RankMap`` must model the
|
|
`Read/Write Property Map`_ concept and must be a `distributed
|
|
property map`_. Its key type must be the vertex descriptor of the
|
|
graph type and its value type must be a floating-point or rational
|
|
type.
|
|
|
|
IN: ``Done done``
|
|
A function object that determines when the PageRank algorithm
|
|
should complete. It will be passed two parameters, the rank map and
|
|
a reference to the graph, and should return ``true`` when the
|
|
algorithm should terminate.
|
|
|
|
**Default**: ``graph::n_iterations(20)``
|
|
|
|
IN: ``typename property_traits<RankMap>::value_type damping``
|
|
The damping factor is the probability that the Web surfer will
|
|
select an outgoing link from the current page instead of jumping to
|
|
a random page.
|
|
|
|
**Default**: 0.85
|
|
|
|
Complexity
|
|
~~~~~~~~~~
|
|
Each iteration of PageRank requires *O((V + E)/p)* time on *p*
|
|
processors and performs *O(V)* communication. The number of
|
|
iterations is dependent on the input to the algorithm.
|
|
|
|
Bibliography
|
|
------------
|
|
|
|
.. [PBMW98] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry
|
|
Winograd. The PageRank Citation Ranking: Bringing Order to the
|
|
Web. Technical report, Stanford Digital Library Technologies Project,
|
|
November 1998.
|
|
|
|
-----------------------------------------------------------------------------
|
|
|
|
Copyright (C) 2005 The Trustees of Indiana University.
|
|
|
|
Authors: Douglas Gregor and Andrew Lumsdaine
|
|
|
|
.. |Logo| image:: pbgl-logo.png
|
|
:align: middle
|
|
:alt: Parallel BGL
|
|
:target: http://www.osl.iu.edu/research/pbgl
|
|
|
|
.. _Distributed Vertex List Graph: DistributedVertexListGraph.html
|
|
.. _Distributed Edge List Graph: DistributedEdgeListGraph.html
|
|
.. _Distributed property map: distributed_property_map.html
|
|
.. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html
|
|
.. _Read/Write Property Map: http://www.boost.org/libs/property_map/ReadWritePropertyMap.html
|
|
|