ceph/src/boost/libs/graph_parallel/doc/page_rank.rst

   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
  23 The ``page_rank`` algorithm computes the ranking of vertices in a
  24 graph, based on the connectivity of a directed graph [PBMW98]_. The
  25 idea of PageRank is based on a random model of a Web surfer, who
  26 starts a random web page and then either follows a link from that web
  27 page (choosing from the links randomly) or jumps to a completely
  28 different web page (not necessarily linked from the current
  29 page). The PageRank of each page is the probability of the random web
  30 surfer visiting that page.
  31
  32 .. contents::
  33
  34 Where Defined
  35 ~~~~~~~~~~~~~
  36 <``boost/graph/distributed/page_rank.hpp``>
  37
  38 also accessible from
  39
  40 <``boost/graph/page_rank.hpp``>
  41
  42 Parameters
  43 ~~~~~~~~~~
  44
  45 IN: ``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
  49 OUT: ``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
  56 IN: ``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
  64 IN: ``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
  71 Complexity
  72 ~~~~~~~~~~
  73 Each iteration of PageRank requires *O((V + E)/p)* time on *p*
  74 processors and performs *O(V)* communication. The number of
  75 iterations is dependent on the input to the algorithm.
  76
  77 Bibliography
  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
  87 Copyright (C) 2005 The Trustees of Indiana University.
  88
  89 Authors: 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