Order a domain here

Domains from $3.99

Resources

» Web Hosting
» Support
» $3.99 Domain Names
» FAQs
» Technical Encyclopedia

PageRank

PageRank is a family of algorithms for assigning numerical weightings to hyperlinked documents (or web pages) indexed by a search engine. Its properties are much discussed by search engine optimization (SEO) experts. The PageRank system is one of the methods that the most successful search engine, Google, uses to determine a page's relevance or importance. It was developed by Google's founders Larry Page and Sergey Brin while at Stanford University in 1998. As Google puts it (http://www.google.com/technology/):

PageRank relies on the uniquely democratic nature of the web by using its vast link structure as an indicator of an individual page's value. Google interprets a link from page A to page B as a vote, by page A, for page B. But, Google looks at more than the sheer volume of votes, or links a page receives; it also analyzes the page that casts the vote. Votes cast by pages that are themselves "important" weigh more heavily and help to make other pages "important."

In other words, a page rank results from a "ballot" amongst all the other pages on the World Wide Web about how important a page is. A hyperlink to a page counts as a vote of support. The PageRank of a page is defined recursively and depends on the number and PageRank metric of all pages that link to it ("incoming links"). A page that is linked by many pages with high rank receives a high rank itself. If there are no links to a web page there is no support of this specific page. The Google Toolbar PageRank goes from 0 to 10. It seems to be a logarithmic scale. The exact details of this scale are unknown.

The name PageRank™ is a trademark of Google. Whether or not the pun on the name Larry Page and the word "page" was intentional or accidental remains an open question. The PageRank process has been patented (US Patent number 6,285,999 (http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u=/netahtml/search-bool.html&r=1&f=G&l=50&co1=AND&d=ptxt&s1=6,285,999.WKU.&OS=PN/6,285,999&RS=PN/6,285,999)). [more info on the patent]

An alternative to the Page rank algorithm proposed by Jon Kleinberg is the HITS algorithm.

Table of contents

1 Page rank algorithm

1.1 Simplified
1.2 Complex

2 See also

3 External links

Page rank algorithm

Simplified

Suppose a small universe of four web pages: A, B, C and D. If all those pages link to A, then the PR (PageRank) of page A would be the sum of the PR of pages B, C and D.

P R (A) = P R (B) + P R (C) + P R (D)

But then suppose page B also has a link to page C, and page D has links to all three pages. One cannot vote twice, and for that reason it is considered that page B has given half a vote to each. In the same logic, only one third of D's vote is counted for A's PageRank.

$PR(A)= \frac{PR(B)}{2}+ \frac{PR(C)}{1}+ \frac{PR(D)}{3}$

In other words, divide the PR by the total Links that comes from the page.

$PR(A)= \frac{PR(B)}{L(B)}+ \frac{PR(C)}{L(C)}+ \frac{PR(D)}{L(D)}$

Finally, all of this is reduced by a certain percentage by multiplying it by a factor q. For reasons explained below, no page can have a PageRank of 0. As such, Google performs a mathematical operation and gives everyone a minimum of $1 - q$ . It means that if you reduced 15% everyone you give them back 0.15.

$PR(A)=\left( \frac{PR(B)}{L(B)}+ \frac{PR(C)}{L(C)}+ \frac{PR(D)}{L(D)}+\,\cdots \right) q + 1 - q$

So one page's PageRank is calculated by the PageRank of other pages. Google is always recalculating the PageRanks. If you give all pages a PageRank of any number (except 0) and constantly recalculate everything all PageRanks will change and tend to stabilize at some point. It is at this point where the PageRank is used by the search engine.

Complex

The formula uses a model of a random surfer who gets bored after several clicks and switches to a random page. The PageRank value of a page reflects the frequency of hits on that page by the random surfer. It can be understood as a Markov process in which the states are pages, and the transitions are all equally probable and are the links between pages. If a page has no links to another pages, it becomes a sink and therefore makes this whole thing unusable, because the sink pages will trap the random visitors forever. However, the solution is quite simple. If the random surfer arrives to a sink page, it picks another URL at random and continues surfing again.

To be fair with pages that are not sinks, these random transitions are added to all nodes in the Web, with a residual probability of usually q=0.15, estimated from the frequency that an average surfer uses his or her browser's bookmark feature.

So, the equation is as follows:

${\rm PageRank}(p_i) = \frac{q}{N} + (1 -q) \sum_{p_j \in L(p_i)} {\rm PageRank} (p_j)$

where $p 1, p 2,..., p N$ are the pages under consideration, $L (p i)$ is the set of pages that link to $p i$ , and N is the total number of pages.

The PageRank values are the entries of the dominant eigenvector of the modified adjacency matrix. This makes PageRank a particularly elegant metric: the eigenvector is

$\mathbf{R} = \begin{bmatrix} {\rm PageRank}(p_1) \\ {\rm PageRank}(p_2) \\ \vdots \\ {\rm PageRank}(p_N) \end{bmatrix}$

where R is the solution of the equation

$\mathbf{R} = \begin{bmatrix} {q / N} \\ {q / N} \\ \vdots \\ {q / N} \end{bmatrix} + (1-q) \begin{bmatrix} \ell(p_1,p_1) & \ell(p_1,p_2) & \cdots & \ell(p_1,p_N) \\ \ell(p_2,p_1) & \ddots & & \\ \vdots & & \ell(p_i,p_j) & \\ \ell(p_N,p_1) & & & \ell(p_N,p_N) \end{bmatrix} \mathbf{R}$

where the adjacency function $\ell(p_i,p_j)$ is 0 if page $p i$ does not link to $p j$ , and normalised such that, for each i

$\sum_{j = 1}^N \ell(p_i,p_j) = 1.$

The values of the PageRank eigenvector are fast to approximate (only a few iterations are needed) and in practice it gives good results.

As a result of Markov theory, it can be shown that the PageRank of a page is the probability of being at that page after lots of clicks. This happens to equal $t - 1$ where $t$ is the expectation of the number of clicks (or random jumps) required to get from the page back to itself.

The main disadvantage is that it favors older pages, because a new page, even a very good one, will not have many links unless it is part of an existing site (a site being a densely connected set of pages).

That's why PageRank should be combined with textual analysis or other ranking methods. PageRank seems to favor Wikipedia pages, often putting them high or at the top of searches for several encyclopedic topics. A common theory is that this is because Wikipedia is very interconnected, with each article having many internal links from other articles, which in turn have links from many other sites on the Web pointing to them. Compared to Wikipedia, and similar high quality content-rich sites, the rest of the World Wide Web is relatively loosely connected.

However, Google is known to actively penalize link farms and other schemes to artificially inflate PageRank. How Google tells the difference between highly inter-linked web sites and link farms is not public knowledge.

List of websites with high PageRanks The maximum PageRank attainable is 10. The minimum is 0.

The following websites have, at one point in time, been assigned below PageRanks as noted:

10/10

Google.com - Search engine that uses PageRank php.net - Official website of the PHP programming language Microsoft.com - Official Microsoft product information/support site Apple.com - Official website of Apple Computer, Inc., which also houses the iTunes Music Store lcs.mit.edu - MIT Laboratory for Computer Science www.w3.org - The World Wide Web Consortium (W3C) www.nature.com - Nature Publishing Group (NPG) www.aaas.org - American Association for the Advancement of Science 9/10

MySQL.com - Official website of the MySQL (My Structured Query Language) language CNN.com - Cable News Network BBC.co.uk - British Broadcasting Corporation Wolfram.com - Houses Mathworld and Scienceworld, two extremely comprehensive math and science resources Wikipedia.org - Free encyclopedia phpBB - Free, open-source PHP-based Internet message board system mozilla.org - Open-source Internet tools sourceforge.net - Directory of open-source development projects archive.org - Home of the Internet Archive project si.edu - Smithsonian Institution homepage stanford.edu - Stanford University

External links

Google talks about PageRank "the heart of our software" (http://www.google.com/technology/)
"PageRank, Google's Original Sin" (http://www.google-watch.org/outdated/pagerank.html)
Online PostScript version (http://www-db.stanford.edu/~backrub/pageranksub.ps) of "The PageRank Citation Ranking: Bringing Order to the Web", by L. Page, S. Brin, R. Motwani, T. Winograd, 1998.
PageRank simplify (http://easytool.org/data/d5.htm)
The Handy Dandy Google Page Rank Figurin' Guide (http://www.searchnerd.com/pagerank/)
Pagerank brief explanation plus pdf documents (http://www.googlerank.com/ranking/pagerank.html)
Google PageRank calculator (http://www.top25web.com/pagerank.php)
Websites with a high PageRank (http://www.ranking-check.de/pagerank_toplist_eng.php)
Google PageRank Bookmarklet (http://steeev.f2o.org/mt/2004/05/new_improved_google_pagerank_bookmarklet.html)

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "PageRank".

Globat.com - Special Web Site Hosting Offer: $4.44/mo for Unlimted Disk Space and Bandwidth, PHP, CGI/PERL, MySQL, FrontPage Ext., 24x7 Live Toll Free Support, 30-Day Money Back Guarantee, SSL/eCommerce ready & more..

Domains Are Free - Definition of PageRank

Site Sections