Boost
C++ Libraries
...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
Boost
C++ Libraries
...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
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
<boost/graph/distributed/page_rank.hpp>
also accessible from
<boost/graph/page_rank.hpp>
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)
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
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.
| [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