Skip to content

README.md

Latest commit

 

History

History
420 lines (302 loc) · 15.1 KB

README.md

File metadata and controls

420 lines (302 loc) · 15.1 KB
Raw

PageRank Algorithm on Indian Tourism Web Graph

Overview

This project implements the PageRank algorithm using the Power Method and applies it to a hyperlink graph obtained from the Indian Tourism website.

The main objectives of this project are:

  • Model a collection of webpages as a directed graph.
  • Construct the Google transition matrix.
  • Handle webpages with no outgoing links (dangling nodes).
  • Compute the PageRank vector using the Power Method.
  • Rank webpages according to their PageRank scores.
  • Study the effect of the damping parameter $p$.
  • Visualize the PageRank distribution across webpages.

Dataset

The dataset used in this project is:

IndianTourism.mat

The dataset contains information about approximately 500 webpages and their corresponding hyperlink graph.

The MATLAB file contains the following variables:

Variable Description
U List of webpage URLs
G Connectivity matrix representing hyperlinks between webpages

The connectivity matrix $G$ is defined as

$$ g_{ij} = \begin{cases} 1, & \text{if there is a hyperlink from page } j \text{ to page } i,\\ 0, & \text{otherwise}. \end{cases} $$

Therefore, the $j$-th column of $G$ represents the outgoing links from webpage $j$.

The web graph contains:

$$ n \approx 500 $$

webpages and

$$ \text{nnz}(G) = 3926 $$

non-zero entries, corresponding to the hyperlinks in the graph.

PageRank Formulation

Let $n$ denote the total number of webpages.

The out-degree of webpage $j$ is the sum of the entries in column $j$:

$$ c_j = \sum_i g_{ij}. $$

Let $p$ be the probability that a user follows a hyperlink. Then $1-p$ represents the probability of randomly jumping to another webpage.

The Google transition matrix $A$ is defined as

$$ a_{ij} = \begin{cases} p\dfrac{g_{ij}}{c_j} + \dfrac{1-p}{n}, & c_j \neq 0,\\ \dfrac{1}{n}, & c_j = 0. \end{cases} $$

where:

  • $p$ is the damping/follow-link probability.
  • $1-p$ is the random-jump probability.
  • $n$ is the total number of webpages.
  • $c_j$ is the out-degree of webpage $j$.

Dangling Nodes

A webpage with no outgoing hyperlinks is called a dangling node or dead-end page.

For such a webpage,

$$ c_j = 0. $$

The corresponding column of $A$ is replaced by a uniform probability distribution:

$$ A_{:,j} = \frac{1}{n}\mathbf{1}. $$

This ensures that the transition matrix remains a valid stochastic matrix.

PageRank as an Eigenvalue Problem

The PageRank vector $x$ is the normalized eigenvector corresponding to the leading eigenvalue of the Google matrix.

It satisfies

$$ Ax = x. $$

Equivalently,

$$ (A - I)x = 0. $$

The PageRank vector is normalized such that

$$ \mathbf{1}^{T}x = 1. $$

Therefore,

$$ \sum_{i=1}^{n}x_i = 1. $$

Each entry $x_i$ represents the PageRank assigned to webpage $i$.

Power Method

The PageRank vector is computed using the Power Method.

The initial vector is chosen as a uniform probability distribution:

$$ x_0 = \frac{1}{n}\mathbf{1}. $$

At each iteration, the PageRank vector is updated according to

$$ x_{k+1} = A x_k. $$

The resulting vector is normalized using the $L_1$-norm:

$$ x_{k+1} = \frac{A x_k}{|A x_k|_1}. $$

The iterations continue until

$$ |x_{k+1} - x_k|_1 < \text{tol}. $$

In this implementation:

$$ \text{tol} = 10^{-10} $$

and the maximum number of iterations is

$$ 1000. $$

Implementation

Main Function

PageRank(U, G, p=0.85, max_iter=1000, tol=1e-10)

Parameters

Parameter Description Default
U List of webpage URLs —
G Webpage connectivity matrix —
p Probability of following a hyperlink 0.85
max_iter Maximum number of Power Method iterations 1000
tol Convergence tolerance 1e-10

Algorithm

The overall PageRank computation follows these steps:

  1. Load the webpage URLs $U$ and connectivity matrix $G$.
  2. Compute the out-degree of every webpage.
  3. Identify dangling webpages with zero out-degree.
  4. Construct the Google matrix $A$.
  5. Initialize the PageRank vector uniformly.
  6. Apply the Power Method.
  7. Normalize the PageRank vector.
  8. Check the convergence criterion.
  9. Sort webpages according to their PageRank scores.
  10. Display the top-ranked webpages.
  11. Repeat the experiment for different values of $p$.

Algorithmic Flow

                 Load U and G
                      |
                      v
             Compute out-degree
                      |
                      v
              Find dangling nodes
                      |
                      v
            Construct Google Matrix A
                      |
                      v
             Initialize x = 1/n
                      |
                      v
                x_new = A @ x
                      |
                      v
                  Normalize
                      |
                      v
             Check convergence
                 /          \
               No            Yes
               |              |
               v              v
          Repeat iteration   Return x

Experimental Setup

The PageRank algorithm was evaluated for the following values of the damping parameter:

$$ p \in {0.60,\ 0.75,\ 0.85,\ 0.95,\ 1.00}. $$

The value $p = 0.85$ is used as the primary setting, following the assignment specification.

For each value of $p$, the program:

  1. Constructs the Google matrix.
  2. Computes the PageRank vector.
  3. Generates a bar plot of PageRank values.
  4. Identifies the top 10 webpages.
  5. Prints the corresponding URLs and PageRank scores.

Results

1. PageRank Results for $p = 0.60$

Rank URL PageRank
1 http://www.makeinindia.com 0.017018
2 http://www.nic.in 0.014354
3 http://india.gov.in 0.011159
4 http://subscribe.businessworld.in 0.009505
5 http://analytics.wrc.nic.in/cmfanalytics 0.008160
6 http://cmf.gov.in 0.008131
7 http://drupal.org 0.006877
8 http://foodprocessingindia.gov.in 0.006595
9 http://pgportal.gov.in 0.006276
10 http://nkn.gov.in/en 0.006211

Observation: For $p = 0.60$, the random-jump probability is relatively large ($1-p = 0.40$). The PageRank distribution is therefore relatively less concentrated, with probability mass spread across a larger portion of the graph. The highest-ranked webpage is http://www.makeinindia.com with a PageRank of 0.017018.

2. PageRank Results for $p = 0.75$

Rank URL PageRank
1 http://www.makeinindia.com 0.032895
2 http://subscribe.businessworld.in 0.018384
3 http://www.nic.in 0.017158
4 http://analytics.wrc.nic.in/cmfanalytics 0.013249
5 http://india.gov.in 0.013014
6 http://foodprocessingindia.gov.in 0.010858
7 http://cmf.gov.in 0.008713
8 http://recruitment.nic.in 0.008433
9 http://nkn.gov.in/en 0.008433
10 http://drupal.org 0.007537

Observation: As $p$ increases from 0.60 to 0.75, the hyperlink structure has a greater influence on the PageRank distribution. The PageRank of makeinindia.com increases from 0.017018 to 0.032895, indicating that the webpage receives significant importance from the connectivity structure of the graph.

3. PageRank Results for $p = 0.85$ (Primary Setting)

The assignment specifies $p = 0.85$ as the primary value.

Rank URL PageRank
1 http://www.makeinindia.com 0.057644
2 http://subscribe.businessworld.in 0.035303
3 http://analytics.wrc.nic.in/cmfanalytics 0.020900
4 http://www.nic.in 0.018004
5 http://foodprocessingindia.gov.in 0.017526
6 http://india.gov.in 0.013467
7 http://nkn.gov.in/en 0.009677
8 http://recruitment.nic.in 0.009677
9 http://cmf.gov.in 0.008479
10 http://drupal.org 0.007448

Observation: The highest-ranked webpage is http://www.makeinindia.com with a PageRank score of 0.057644, followed by http://subscribe.businessworld.in at 0.035303. A relatively small group of webpages receives a significant fraction of the PageRank mass due to the structure of the hyperlink graph.

4. PageRank Results for $p = 0.95$

Rank URL PageRank
1 http://www.makeinindia.com 0.140801
2 http://subscribe.businessworld.in 0.108806
3 http://analytics.wrc.nic.in/cmfanalytics 0.046288
4 http://foodprocessingindia.gov.in 0.040204
5 http://www.nic.in 0.014710
6 http://india.gov.in 0.010870
7 http://nkn.gov.in/en 0.008647
8 http://recruitment.nic.in 0.008647
9 http://bwdisrupt.businessworld.in 0.006942
10 http://www.digitalmarket.asia 0.006485

Observation: For $p = 0.95$, the random-jump probability is only 0.05, so the hyperlink structure dominates the PageRank computation. makeinindia.com rises to 0.140801 and subscribe.businessworld.in to 0.108806 — the distribution becomes substantially more concentrated as $p$ increases.

5. PageRank Results for $p = 1.00$

Rank URL PageRank
1 http://www.makeinindia.com 0.391034
2 http://subscribe.businessworld.in 0.377298
3 http://analytics.wrc.nic.in/cmfanalytics 0.122678
4 http://foodprocessingindia.gov.in 0.108991
5 http://www.nic.in 0.000000
6 http://india.gov.in 0.000000
7 http://bwdisrupt.businessworld.in 0.000000
8 http://www.digitalmarket.asia 0.000000
9 http://www.bwcio.com 0.000000
10 http://nkn.gov.in/en 0.000000

Observation: With $p = 1$, the random-jump probability is zero, so the PageRank is determined entirely by the hyperlink structure. The distribution becomes highly concentrated:

Webpage PageRank
http://www.makeinindia.com 0.391034
http://subscribe.businessworld.in 0.377298
http://analytics.wrc.nic.in/cmfanalytics 0.122678
http://foodprocessingindia.gov.in 0.108991

Their combined PageRank is approximately

$$ 0.391034 + 0.377298 + 0.122678 + 0.108991 \approx 0.999999, $$

so almost the entire PageRank probability mass is concentrated in these four webpages, and several others receive a PageRank of zero.

Comparison of PageRank Across Different $p$

Damping Factor $p$ PageRank of makeinindia.com
0.60 0.017018
0.75 0.032895
0.85 0.057644
0.95 0.140801
1.00 0.391034

The results show a clear increase in PageRank concentration as $p$ approaches 1.

Effect of the Damping Parameter

The damping parameter controls the balance between following hyperlinks (probability $p$) and randomly jumping to another webpage (probability $1-p$).

$p$ Link Following Random Jumping Effect
0.60 60% 40% More distributed ranking
0.75 75% 25% Greater influence of graph structure
0.85 85% 15% Standard PageRank setting
0.95 95% 5% Strong concentration
1.00 100% 0% Entirely determined by hyperlinks

As $p$ increases, the probability of following the hyperlink structure increases while the teleportation probability decreases, causing webpages strongly supported by the hyperlink structure to accumulate increasingly large PageRank values.

Visualization

For every value of $p$, the program generates a bar graph showing the PageRank score of every webpage.

  • X-axis: Webpage index
  • Y-axis: PageRank value

Discussion

The experiments demonstrate that the damping parameter has a significant effect on the PageRank distribution.

For smaller values of $p$, the random-jump probability $1-p$ is larger, which prevents the PageRank from becoming overly concentrated on a small subset of webpages. As $p$ increases, the hyperlink structure becomes increasingly dominant, so webpages that receive important links accumulate larger PageRank values.

For the primary setting $p = 0.85$, the highest-ranked webpage is http://www.makeinindia.com with a PageRank of 0.057644.

The results also show that PageRank is not determined solely by the number of incoming links — the importance of the webpages providing those links also matters. The $p = 1.0$ experiment highlights this clearly: without teleportation, the probability mass concentrates in a small portion of the graph, with four webpages accounting for almost the entire distribution.

Interpretation of the Web Graph

A webpage can obtain a high PageRank when:

  1. It receives many incoming hyperlinks.
  2. The webpages linking to it have high PageRank.
  3. It belongs to a strongly connected or highly influential region of the graph.
  4. Probability mass flows toward it through the hyperlink structure.

PageRank therefore measures more than simple hyperlink counts — it recursively assigns importance based on the importance of neighboring webpages.