1 <?xml version=
"1.0" encoding=
"utf-8" ?>
2 <!DOCTYPE html PUBLIC
"-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
3 <html xmlns=
"http://www.w3.org/1999/xhtml" xml:
lang=
"en" lang=
"en">
5 <meta http-equiv=
"Content-Type" content=
"text/html; charset=utf-8" />
6 <meta name=
"generator" content=
"Docutils 0.6: http://docutils.sourceforge.net/" />
7 <title>Parallel BGL PageRank
</title>
8 <link rel=
"stylesheet" href=
"../../../../rst.css" type=
"text/css" />
11 <div class=
"document" id=
"logo-pagerank">
12 <h1 class=
"title"><a class=
"reference external" href=
"http://www.osl.iu.edu/research/pbgl"><img align=
"middle" alt=
"Parallel BGL" class=
"align-middle" src=
"pbgl-logo.png" /></a> PageRank
</h1>
14 <!-- Copyright (C) 2004-2008 The Trustees of Indiana University.
15 Use, modification and distribution is subject to the Boost Software
16 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
17 http://www.boost.org/LICENSE_1_0.txt) -->
18 <pre class=
"literal-block">
20 template
<typename Graph, typename RankMap, typename Done
>
22 page_rank(const Graph
& g, RankMap rank_map, Done done,
23 typename property_traits
<RankMap
>::value_type damping =
0.85);
25 template
<typename Graph, typename RankMap
>
27 page_rank(const Graph
& g, RankMap rank_map);
30 <p>The
<tt class=
"docutils literal"><span class=
"pre">page_rank
</span></tt> algorithm computes the ranking of vertices in a
31 graph, based on the connectivity of a directed graph
<a class=
"citation-reference" href=
"#pbmw98" id=
"id1">[PBMW98]
</a>. The
32 idea of PageRank is based on a random model of a Web surfer, who
33 starts a random web page and then either follows a link from that web
34 page (choosing from the links randomly) or jumps to a completely
35 different web page (not necessarily linked from the current
36 page). The PageRank of each page is the probability of the random web
37 surfer visiting that page.
</p>
38 <div class=
"contents topic" id=
"contents">
39 <p class=
"topic-title first">Contents
</p>
41 <li><a class=
"reference internal" href=
"#where-defined" id=
"id2">Where Defined
</a></li>
42 <li><a class=
"reference internal" href=
"#parameters" id=
"id3">Parameters
</a></li>
43 <li><a class=
"reference internal" href=
"#complexity" id=
"id4">Complexity
</a><ul>
44 <li><a class=
"reference internal" href=
"#bibliography" id=
"id5">Bibliography
</a></li>
49 <div class=
"section" id=
"where-defined">
50 <h1><a class=
"toc-backref" href=
"#id2">Where Defined
</a></h1>
51 <p><<tt class=
"docutils literal"><span class=
"pre">boost/graph/distributed/page_rank.hpp
</span></tt>></p>
52 <p>also accessible from
</p>
53 <p><<tt class=
"docutils literal"><span class=
"pre">boost/graph/page_rank.hpp
</span></tt>></p>
55 <div class=
"section" id=
"parameters">
56 <h1><a class=
"toc-backref" href=
"#id3">Parameters
</a></h1>
58 <dt>IN:
<tt class=
"docutils literal"><span class=
"pre">Graph
&</span> <span class=
"pre">g
</span></tt></dt>
59 <dd>The graph type must be a model of
<a class=
"reference external" href=
"DistributedVertexListGraph.html">Distributed Vertex List Graph
</a> and
60 <a class=
"reference external" href=
"DistributedEdgeListGraph.html">Distributed Edge List Graph
</a>. The graph must be directed.
</dd>
61 <dt>OUT:
<tt class=
"docutils literal"><span class=
"pre">RankMap
</span> <span class=
"pre">rank
</span></tt></dt>
62 <dd>Stores the rank of each vertex. The type
<tt class=
"docutils literal"><span class=
"pre">RankMap
</span></tt> must model the
63 <a class=
"reference external" href=
"http://www.boost.org/libs/property_map/ReadWritePropertyMap.html">Read/Write Property Map
</a> concept and must be a
<a class=
"reference external" href=
"distributed_property_map.html">distributed
64 property map
</a>. Its key type must be the vertex descriptor of the
65 graph type and its value type must be a floating-point or rational
67 <dt>IN:
<tt class=
"docutils literal"><span class=
"pre">Done
</span> <span class=
"pre">done
</span></tt></dt>
68 <dd><p class=
"first">A function object that determines when the PageRank algorithm
69 should complete. It will be passed two parameters, the rank map and
70 a reference to the graph, and should return
<tt class=
"docutils literal"><span class=
"pre">true
</span></tt> when the
71 algorithm should terminate.
</p>
72 <p class=
"last"><strong>Default
</strong>:
<tt class=
"docutils literal"><span class=
"pre">graph::n_iterations(
20)
</span></tt></p>
74 <dt>IN:
<tt class=
"docutils literal"><span class=
"pre">typename
</span> <span class=
"pre">property_traits
<RankMap
>::value_type
</span> <span class=
"pre">damping
</span></tt></dt>
75 <dd><p class=
"first">The damping factor is the probability that the Web surfer will
76 select an outgoing link from the current page instead of jumping to
78 <p class=
"last"><strong>Default
</strong>:
0.85</p>
82 <div class=
"section" id=
"complexity">
83 <h1><a class=
"toc-backref" href=
"#id4">Complexity
</a></h1>
84 <p>Each iteration of PageRank requires
<em>O((V + E)/p)
</em> time on
<em>p
</em>
85 processors and performs
<em>O(V)
</em> communication. The number of
86 iterations is dependent on the input to the algorithm.
</p>
87 <div class=
"section" id=
"bibliography">
88 <h2><a class=
"toc-backref" href=
"#id5">Bibliography
</a></h2>
89 <table class=
"docutils citation" frame=
"void" id=
"pbmw98" rules=
"none">
90 <colgroup><col class=
"label" /><col /></colgroup>
92 <tr><td class=
"label"><a class=
"fn-backref" href=
"#id1">[PBMW98]
</a></td><td>Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry
93 Winograd. The PageRank Citation Ranking: Bringing Order to the
94 Web. Technical report, Stanford Digital Library Technologies Project,
95 November
1998.
</td></tr>
98 <hr class=
"docutils" />
99 <p>Copyright (C)
2005 The Trustees of Indiana University.
</p>
100 <p>Authors: Douglas Gregor and Andrew Lumsdaine
</p>
105 <hr class=
"footer" />
106 Generated on:
2009-
05-
31 00:
21 UTC.
107 Generated by
<a class=
"reference external" href=
"http://docutils.sourceforge.net/">Docutils
</a> from
<a class=
"reference external" href=
"http://docutils.sourceforge.net/rst.html">reStructuredText
</a> source.