123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101 |
- .. 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
|