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);
}

Page_rankалгоритм вычисляет ранжирование вершин в графе, основанное на связности направленного графа[PBMW98]. Идея PageRank основана на случайной модели веб-серфера, который запускает случайную веб-страницу, а затем либо следует по ссылке с этой веб-страницы (выбирая из ссылок случайным образом), либо переходит на совершенно другую веб-страницу (не обязательно связанную с текущей страницей). PageRank каждой страницы - это вероятность случайного веб-серфера, посещающего эту страницу.

Contents

Where Defined

<boost/graph/distributed/page_rank.hpp>

Также доступны из

<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

Каждая итерация PageRank требуетO((V + E)/p)времени наpпроцессорах и выполняетO(V)связь. Количество итераций зависит от ввода в алгоритм.

Bibliography

[PBMW98]

Лоуренс Пейдж, Сергей Брин, Раджив Мотвани и Терри Виноград. PageRank Citation Ranking: Bringing Order to the Web. Technical report, Stanford Digital Library Technologies Project, November 1998.

Авторы: Дуглас Грегор и Эндрю Лумсдейн

Статья Parallel BGL PageRank раздела может быть полезна для разработчиков на c++ и boost.

Parallel BGL PageRank

Boost , ,

Boost C++ Libraries

PageRank

Where Defined

Parameters

Complexity

Bibliography