wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Website Rankings
        
(Message started by: TenaliRaman on Nov 25^th, 2003, 1:10pm)

Title: Website Rankings
Post by TenaliRaman on Nov 25^th, 2003, 1:10pm

(i thought first of putting it in CS section but then i thought this system should be known by everyone as a general information)

You have created 10 web pages with one as your home page. How will you link them so as to maximise the average PR of your site?

PR = page ranking
we will follow google page ranking scheme here.
our page ranking will be only based on backward links and no other factors.
Assume that there are no links coming from other websites.

Title: Re: Website Rankings
Post by Jamie on Dec 1^st, 2003, 4:16am

I suspect you're going to have clarify this one a bit. For example, why not just link every page from every other?

on 11/25/03 at 13:10:37, TenaliRaman wrote:

Assume that there are no links coming from other websites.

Hmmm... How is Google going to find our page in the first place? ;)

Title: Re: Website Rankings
Post by TenaliRaman on Dec 1^st, 2003, 6:55am

every inward coming link to a page increases the page's PR and every outgoing link reduces the page's PR. This is sort of the action - counteraction.

The assumption basically is to simplify calculations a bit since incoming links from other sites would drastically increase your PR.

Usually google does not find your page, you need to register with them. you might information on this from www.w3schools.com .

[edit]
As a general note to all,
the google search engine and other stuff explained here. This i think is the official paper of google,
http://www-db.stanford.edu/~backrub/google.html
[/edit]

Title: Re: Website Rankings
Post by aero_guy on Dec 1^st, 2003, 11:50am

It seems (if I am understanding you) that in any contained system the average ranking will be zero. Every link counts as one point for the page being linked to and one against the one being linked from. If both the to and from pages are on your site than you will always have a zero average page ranking.

For example, the average page ranking of the internet itself would be zero (actually it would be negative considering the amount of blind links).

Title: Re: Website Rankings
Post by TenaliRaman on Dec 2^nd, 2003, 10:31am

yes aero, it would be zero if it had not been for something called as damping factor. The official paper which i had linked to in my last post gives a formula for calculating PR of a web page and it includes this damping factor.

The formula gives the lowest possible value of (1-damping_factor) to any page.

Title: Re: Website Rankings
Post by aero_guy on Dec 2^nd, 2003, 3:42pm

From your link right under where they present the formula (along with damping factor):

Note that the PageRanks form a probability distribution over web pages, so the sum of all web pages' PageRanks will be one.

Therefore the average for ten self-contained pages will be .1 no matter how you link them.

Title: Re: Website Rankings
Post by TenaliRaman on Dec 3^rd, 2003, 1:54am

hmm,
mean = E(x) = sum over xP(x) (for discrete probabilities) and integral over xP(x) (for continuous probabilities)

not necessarily (sum of probs)/10 (or am i making a mistake?)

Title: Re: Website Rankings
Post by towr on Dec 3^rd, 2003, 3:11am

P(x) would have to be the chance of a certain webpage, where x would be the PR of that webpage.. I don't see a reason not to take every P(x) as 1/10, that is each page is weighed equally in the average.
And since PR sums to 1 we get 1/10

Title: Re: Website Rankings
Post by TenaliRaman on Dec 3^rd, 2003, 4:22am

hmm,
i could accept the argument (but if i do understand google's formula , the lowest possible value a page gets is 0.15 no??)

Title: Re: Website Rankings
Post by towr on Dec 3^rd, 2003, 6:07am

Hmm.. it does look peculiar.. One the one hand they say all page rankings of all webpages must add up to one, and one the other hand the minimum seems (1-d) (where d is typically 0.85).
The only solution for this I see is that the other terms may be negative.. But I guess I'll have to actually read the article to fidn out how it really works..

Title: Re: Website Rankings
Post by TenaliRaman on Dec 3^rd, 2003, 8:06am

Yes it is peculiar.

if you note , the formula given is a recursive formula.
If page A has link to page B and page B has link page A, then you would normally expect this formula to give a very high result (and it would if it had not been for that 'd'). I did some calculations and it seems to stabilise at one point but some of my calculations have given me average PR's well above 1(?).I might have probably made a mistake in either understanding the formula or in my calculations. I thought i understood it pretty well but i never gave the thought to the statement of the probability distribution.

Hopefully you would get it and then explain it to me ;D