1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
.. 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
|
