PageRank

Computes the PageRank of each vertex: a measure of importance based on the link structure of a directed graph. A vertex is important if it is pointed to by other important vertices.

Complexity: O(V + E) per iteration
Defined in: <boost/graph/page_rank.hpp>

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/page_rank.hpp>
#include <boost/property_map/property_map.hpp>
#include <iostream>
#include <vector>
#include <iomanip>

int main() {
    using namespace boost;
    using Graph = adjacency_list<vecS, vecS, directedS>;

    // A small web graph: 0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 3 -> 2
    Graph g(4);
    add_edge(0, 1, g);
    add_edge(0, 2, g);
    add_edge(1, 2, g);
    add_edge(2, 0, g);
    add_edge(3, 2, g);

    std::vector<double> ranks(num_vertices(g));
    auto rank_map = make_iterator_property_map(
        ranks.begin(), get(vertex_index, g));

    // Run PageRank with default damping=0.85 and 20 iterations
    graph::page_rank(g, rank_map);

    std::cout << std::fixed << std::setprecision(4);
    for (std::size_t v = 0; v < num_vertices(g); ++v) {
        std::cout << "vertex " << v << "  rank=" << ranks[v] << "\n";
    }
}

vertex 0  rank=1.4436
vertex 1  rank=0.7600
vertex 2  rank=1.5301
vertex 3  rank=0.1500

Vertex 2 has the highest rank because it receives edges from three other vertices, including the high-ranked vertex 0.

All overloads live in namespace boost::graph (not boost).

(1) page_rank with explicit secondary rank buffer

template <typename Graph, typename RankMap, typename Done,
          typename RankMap2>
void page_rank(const Graph& g, RankMap rank_map, Done done,
               typename property_traits<RankMap>::value_type damping,
               typename graph_traits<Graph>::vertices_size_type n,
               RankMap2 rank_map2);

The algorithm double-buffers ranks between iterations; rank_map2 is the second buffer (same concept requirements as rank_map). Useful if you want to reuse a pre-allocated buffer.

(2) page_rank with custom iteration count

template <typename Graph, typename RankMap, typename Done>
void page_rank(const Graph& g, RankMap rank_map, Done done,
               typename property_traits<RankMap>::value_type damping,
               typename graph_traits<Graph>::vertices_size_type n);

Equivalent to (1) with an internally allocated iterator_property_map used for the second buffer.

(3) page_rank with default vertex count

template <typename Graph, typename RankMap, typename Done>
void page_rank(const Graph& g, RankMap rank_map, Done done,
               typename property_traits<RankMap>::value_type damping = 0.85);

Equivalent to (2) with n = num_vertices(g).

(4) page_rank (defaults)

template <typename Graph, typename RankMap>
void page_rank(const Graph& g, RankMap rank_map);

Equivalent to (3) with done = n_iterations(20) and damping = 0.85.

(5) remove_dangling_links

template <typename MutableGraph>
void remove_dangling_links(MutableGraph& g);

Repeatedly removes all vertices with out_degree == 0 until a fixed point is reached. Requires MutableGraph to model Vertex List Graph and Mutable Graph.

(6) n_iterations

struct n_iterations {
    explicit n_iterations(std::size_t n);

    template <typename RankMap, typename Graph>
    bool operator()(const RankMap&, const Graph&);
};

The built-in termination functor used by overload (4): returns true after n calls. Use n_iterations(k) to run exactly k iterations.

Parameters

Direction Parameter Description

Direction	Parameter	Description
IN	`const Graph& g`	Must model Vertex List Graph and Incidence Graph (or Bidirectional Graph for better performance on large graphs).
OUT	`RankMap rank_map`	ReadWritePropertyMap. Vertex descriptor → rank value (typically `double`).
UTIL	`RankMap2 rank_map2`	Second buffer used during iteration.
IN	`Done done`	Termination functor. Called with `(rank_map, g)` after each iteration. Return `true` to stop.
IN	`damping`	Probability of following a link (vs random jump). Default: `0.85`.
IN	`n`	Number of vertices used for the initial rank `1/n`. Default: `num_vertices(g)`.

const Graph& g

Must model Vertex List Graph and Incidence Graph (or Bidirectional Graph for better performance on large graphs).

OUT

RankMap rank_map

ReadWritePropertyMap. Vertex descriptor → rank value (typically double).

UTIL

RankMap2 rank_map2

Second buffer used during iteration.

Done done

Termination functor. Called with (rank_map, g) after each iteration. Return true to stop.

damping

Probability of following a link (vs random jump). Default: 0.85.

n

Number of vertices used for the initial rank 1/n. Default: num_vertices(g).

Termination

The default termination is graph::n_iterations(20), which runs exactly 20 iterations. For convergence-based termination, write a custom Done functor that compares rank values between iterations.

Dangling vertices

Vertices with no outgoing edges (dangling nodes) cause rank to "leak" out of the graph. Use graph::remove_dangling_links(g) to remove them before running PageRank, or handle them in your model.

Edit this Page