Page Rank Algorithm

The Page Rank Algorithm, developed by Google founders Larry Page and Sergey Brin, is a mathematical algorithm that assigns a numerical weighting to each element in a hyperlinked set of documents, such as the World Wide Web, with the purpose of measuring its relative importance within the set. The premise of the algorithm is based on the idea that the value of a webpage can be determined by the number of times it is linked to other pages, as well as the importance of the pages that link to it. In essence, it emulates the academic citation system, where a paper's importance is often judged by the number of times it is cited by other papers. The algorithm works by assuming that a user starts on a random webpage and clicks on links at random, eventually reaching a dead end or deciding to jump to another random page. The Page Rank of a page is then calculated as the probability that a user ends up on that page at any given time. This is done by iteratively updating the rank values through a series of calculations based on the ranks of the pages linking to it. The process continues until the rank values converge to a steady state, producing a final ranking for the webpages. This final ranking is what Google uses to determine the order of search results for a particular query, ensuring the most relevant and authoritative pages are displayed at the top.
/*
 Petar 'PetarV' Velickovic
 Algorithm: PageRank
*/

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <complex>
#include <iomanip>
#include <numeric>

#define DPRINTC(C) printf(#C " = %c\n", (C))
#define DPRINTS(S) printf(#S " = %s\n", (S))
#define DPRINTD(D) printf(#D " = %d\n", (D))
#define DPRINTLLD(LLD) printf(#LLD " = %lld\n", (LLD))
#define DPRINTLF(LF) printf(#LF " = %.5lf\n", (LF))

using namespace std;
typedef long long lld;
typedef unsigned long long llu;

int n;
vector<vector<int> > edges;

/*
 The PageRank algorithm computes a relevance metric for nodes in a graph,
 by computing a stationary distribution of its corresponding ergodic
 Markov Chain (using the ``easily bored random web surfer'' model).
 
 Complexity: O(V + E) time (per iteration), O(V + E) memory
*/

double sum(double x, double y)
{
    return x + y;
}

double sq_diff(double x, double y)
{
    return (x - y) * (x - y);
}

vector<double> pagerank(double alpha, double epsilon)
{
    // initialise
    vector<double> old_pi(n), pi(n);
    for (int i=0;i<n;i++) pi[i] = 1.0 / n;
    
    int num_iterations = 0;
    
    do
    {
        vector<double> H(n), A(n), I(n);
        for (int i=0;i<n;i++)
        {
            old_pi[i] = pi[i];
            H[i] = A[i] = I[i] = 0.0;
        }
        
        // Compute the separate components of pi
        for (int i=0;i<n;i++)
        {
            for (int j=0;j<edges[i].size();j++)
            {
                H[edges[i][j]] += (1.0 - alpha) * pi[i] / edges[i].size();
            }
            if (edges[i].empty()) A[i] += (1.0 - alpha) / n;
            I[i] += alpha / n;
        }
        
        // Add them up, normalise and print
        double sum = 0.0;
        for (int i=0;i<n;i++)
        {
            pi[i] = H[i] + A[i] + I[i];
            sum += pi[i];
        }
        cout << "Iteration " << ++num_iterations << ": {";
        for (int i=0;i<n;i++)
        {
            pi[i] /= sum;
            cout << pi[i];
            if (i < n - 1) cout << ", ";
            else cout << "}" << endl;
        }
        
        // Stop iterating if the computation has converged enough
    } while (inner_product(pi.begin(), pi.end(), old_pi.begin(), 0.0, sum, sq_diff) > epsilon);
    
    return pi;
}

int main()
{
    n = 7;
    edges.resize(7);
    
    edges[0].push_back(2);
    
    edges[1].push_back(1);
    edges[1].push_back(2);
    
    edges[2].push_back(0);
    edges[2].push_back(2);
    edges[2].push_back(3);
    
    edges[3].push_back(3);
    edges[3].push_back(4);
    
    edges[4].push_back(6);
    
    edges[5].push_back(5);
    edges[5].push_back(6);
    
    edges[6].push_back(3);
    edges[6].push_back(4);
    edges[6].push_back(6);
    
    pagerank(0.1, 1e-6);
    
    return 0;
}

LANGUAGE:

DARK MODE: