Member Avatar for codedhands

Hello Good people,am not so sure if this should go here,i am student who is interested in developing a search engine that indexes pages from my country.I have been doing my research on Algorithm to use for sometime now and i have found HITS and PageRank as the best out there.I have choosing to go with PageRank since it is more stable than the HITS Algorithm(so i read).

I have found countless articles and university researches about PageRank but my problem is that i do not understand most of the mathematical symbols that form the algorithm in this papers.Currently,i cannot understand how the Google Matrix(the irreducible,stochastic matrix) was calculated with the algorithm,i do not seem to understand the Algorithm used.

I did my reading from the articles below:


http://ilpubs.stanford.edu:8090/386/1/1999-31.pdf

Please i need you to help me go through it,i need a basic explanation(examples will be nice) with less mathematical symbols.

Thanks in advance.

  • 4 Contributors
  • 4 Replies
  • 215 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by almostbob

Dani AI

Generated

A short, practical primer that fills the gaps in the thread for .

PageRank in plain English: treat the web as a directed graph where each hyperlink is a “vote.” Model a random surfer who, at each step, either follows one of the outgoing links from the current page (with probability d) or jumps to a random page (with probability 1−d). PageRank is the long‑run probability that the surfer is on each page — i.e., the stationary distribution (dominant eigenvector) of the transition matrix. (research.google)

How the Google matrix is built (step‑by‑step, no heavy symbols):

  • Build the link structure and compute each page’s outdegree L_j.
  • Create S so column j distributes its mass equally to pages j links to: S[i,j] = 1/L_j when j→i; if L_j = 0 (a dangling page), set that column to the uniform vector 1/N.
  • Choose a damping factor d (commonly 0.85) and form the Google matrix G = d·S + (1−d)·(1/N)·11^T.
    The PageRank vector r satisfies r = G·r, or coordinatewise:
    r_i = (1-d)/N + d * sum_{j->i} (r_j / L_j). ()

Compute it with the power method (very common in practice). Pseudocode:

N = number of pages
d = 0.85
r = [1/N,...,1/N]
repeat:
  r_new = (1-d)/N * 1 + d * S * r    # implement S*r using adjacency lists (sparse)
  if ||r_new - r|| < tol: break
  r = r_new

Use sparse multiplication (sum contributions from each page to its outlinks); stop when the L1 or L2 change is below your tolerance. (books.google.com)

Practical cautions and tips: don’t form dense NxN matrices — use adjacency lists and implicit multiplication; handle dangling pages up front; consider a personalization vector instead of uniform teleportation for topic‑sensitive ranking; and remember is right that Google’s complete ranking uses many signals beyond PageRank, but the PageRank math and the teleportation fix are well documented and are a solid starting point. For deeper theory and implementation details consult the original papers and the Langville & Meyer treatment. (research.google)

Recommended Answers

All 4 Replies

Member Avatar for almostbob

just for fun, Googles April 1 approach

Member Avatar for InsightsDigital

Thanks for sharing the pigeonrank system. It had be going until I saw one of the questions regarding if the smartness of pigeons and then I realized it was an April Fools prank. Thanks for the chuckle.

Member Avatar for mokmok69

No body knows Google algorithm,...don't waste your time calculating best thing you do is to build related link to your site with high page rank.

Member Avatar for almostbob

If you cant understand the math, then you won't develop a suitable algorithm to create the rank either

bad translation
page rank = sum of all inbound links as (stability factor times number of inbound (links times rank of inbound linking page) / outbound links ) as variation in page rank approaches zero

postscript : i can calculate the math, because my calculator includes sigma functions, I cant write the math

Edited by almostbob because: n/a
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.