1.. Copyright (C) 2004-2008 The Trustees of Indiana University. 2 Use, modification and distribution is subject to the Boost Software 3 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 4 http://www.boost.org/LICENSE_1_0.txt) 5 6=============== 7|Logo| PageRank 8=============== 9 10:: 11 12 namespace graph { 13 template<typename Graph, typename RankMap, typename Done> 14 inline void 15 page_rank(const Graph& g, RankMap rank_map, Done done, 16 typename property_traits<RankMap>::value_type damping = 0.85); 17 18 template<typename Graph, typename RankMap> 19 inline void 20 page_rank(const Graph& g, RankMap rank_map); 21 } 22 23The ``page_rank`` algorithm computes the ranking of vertices in a 24graph, based on the connectivity of a directed graph [PBMW98]_. The 25idea of PageRank is based on a random model of a Web surfer, who 26starts a random web page and then either follows a link from that web 27page (choosing from the links randomly) or jumps to a completely 28different web page (not necessarily linked from the current 29page). The PageRank of each page is the probability of the random web 30surfer visiting that page. 31 32.. contents:: 33 34Where Defined 35~~~~~~~~~~~~~ 36<``boost/graph/distributed/page_rank.hpp``> 37 38also accessible from 39 40<``boost/graph/page_rank.hpp``> 41 42Parameters 43~~~~~~~~~~ 44 45IN: ``Graph& g`` 46 The graph type must be a model of `Distributed Vertex List Graph`_ and 47 `Distributed Edge List Graph`_. The graph must be directed. 48 49OUT: ``RankMap rank`` 50 Stores the rank of each vertex. The type ``RankMap`` must model the 51 `Read/Write Property Map`_ concept and must be a `distributed 52 property map`_. Its key type must be the vertex descriptor of the 53 graph type and its value type must be a floating-point or rational 54 type. 55 56IN: ``Done done`` 57 A function object that determines when the PageRank algorithm 58 should complete. It will be passed two parameters, the rank map and 59 a reference to the graph, and should return ``true`` when the 60 algorithm should terminate. 61 62 **Default**: ``graph::n_iterations(20)`` 63 64IN: ``typename property_traits<RankMap>::value_type damping`` 65 The damping factor is the probability that the Web surfer will 66 select an outgoing link from the current page instead of jumping to 67 a random page. 68 69 **Default**: 0.85 70 71Complexity 72~~~~~~~~~~ 73Each iteration of PageRank requires *O((V + E)/p)* time on *p* 74processors and performs *O(V)* communication. The number of 75iterations is dependent on the input to the algorithm. 76 77Bibliography 78------------ 79 80.. [PBMW98] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry 81 Winograd. The PageRank Citation Ranking: Bringing Order to the 82 Web. Technical report, Stanford Digital Library Technologies Project, 83 November 1998. 84 85----------------------------------------------------------------------------- 86 87Copyright (C) 2005 The Trustees of Indiana University. 88 89Authors: Douglas Gregor and Andrew Lumsdaine 90 91.. |Logo| image:: pbgl-logo.png 92 :align: middle 93 :alt: Parallel BGL 94 :target: http://www.osl.iu.edu/research/pbgl 95 96.. _Distributed Vertex List Graph: DistributedVertexListGraph.html 97.. _Distributed Edge List Graph: DistributedEdgeListGraph.html 98.. _Distributed property map: distributed_property_map.html 99.. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html 100.. _Read/Write Property Map: http://www.boost.org/libs/property_map/ReadWritePropertyMap.html 101 102
