graph/test/personalized_pagerank_test.cpp at 79f4c84e2916223e97eee4b436572eb7a0bf1f86 · boostorg/graph · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

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

int main(int, char*[]) {
    using namespace boost;
    // deliberately hard (slow-converging) graph
    using Graph = adjacency_list<vecS, vecS, directedS>;
    std::vector<std::pair<int,int>> edges = {
        {0,1},{1,0},{1,2},{2,1},{2,3},{3,2},
        {4,5},{5,4},{5,6},{6,5},{6,7},{7,6},{7,8},{8,7},{8,9},{9,8},{9,10},{10,9},
        {0,3},{3,0},{1,3},{3,1},{1,4},{4,1},
        {4,6},{6,4},{6,9},{9,6},{6,8},{8,6},{7,9},{9,7},{8,10},{10,8},
        {11,10},{10,11},{10,12},{12,10}
    };
    Graph g(edges.begin(), edges.end(), 13);

    std::vector<double> ranks(num_vertices(g));
    auto rank_map = make_iterator_property_map(ranks.begin(), get(vertex_index, g));
    std::vector<double> personalization(num_vertices(g));
    auto personalization_map = make_iterator_property_map(personalization.begin(), get(vertex_index, g));
    personalization[0] = 1;
    personalization[1] = 1;
    personalization[2] = 1;
    personalization[3] = 1;

    std::size_t max_iters(100); // Convergence is so bad in this graph that it needs such a high cap.
    using Edge = graph_traits<Graph>::edge_descriptor;
    auto weight = make_function_property_map<Edge, double>(
        [&g](Edge e){ return 1.0 / std::sqrt(double(out_degree(source(e, g), g) * out_degree(target(e, g), g))); });
    auto convergence1 = graph::rank_convergence(max_iters, 1.E-9);
    convergence1 = graph::personalized_page_rank(g, weight, personalization_map, rank_map, convergence1, 0.9);

    std::cout << "ended after "<<max_iters-convergence1.iters << " iterations\n";
    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";
    }
    BOOST_ASSERT(ranks[0]==ranks[2]); // should be exactly equal due to symmetry, even when considering floating point coarseness
    BOOST_ASSERT(ranks[0]<ranks[1]+0.1);
    BOOST_ASSERT(ranks[8]==ranks[9]);
    BOOST_ASSERT(ranks[11]==ranks[12]);
    BOOST_ASSERT(ranks[11]>0);
    BOOST_ASSERT(convergence1.iters<max_iters);

    // COMPUTING A HIGH-PASS VERSION BY PASSING NEGATIVE DAMPING (resulting values can be negative)
    // This is not completely correct yet for computing graph gradients, because it needs to eskew normalization,
    // so we need to be able to customize said normalization.
    // Damping should generaly be in the range [-1,1].
    auto renorm_weight = make_function_property_map<Edge, double>(
        [&g](Edge e){ return 1.0 / std::sqrt(double((1.0+out_degree(source(e, g), g)) * (1.0+out_degree(target(e, g), g)))); });
    auto convergence2 = graph::rank_convergence(max_iters, 1.E-9);
    convergence2 = graph::personalized_page_rank(g, renorm_weight, personalization_map, rank_map, convergence2, -0.8);
    std::cout << "ended after "<<max_iters-convergence2.iters << " iterations\n";
    std::cout << std::fixed << std::setprecision(4);
    for (std::size_t v = 0; v < num_vertices(g); ++v)
    {
        std::cout << "vertex " << v << "  flow=" << ranks[v] << "\n";
    }
    BOOST_ASSERT(ranks[0]==ranks[2]); // should be exactly equal due to symmetry, even when considering floating point coarseness
    BOOST_ASSERT(ranks[0]>ranks[1]+0.1);
    BOOST_ASSERT(ranks[8]==ranks[9]);
    BOOST_ASSERT(ranks[11]==ranks[12]);
    BOOST_ASSERT(ranks[11]<0);
    BOOST_ASSERT(convergence2.iters<max_iters);
}