PageRank Convergence

Eliot Knudsen

unread,

Mar 25, 2012, 3:14:22 PM3/25/12

to machine-learning-with-large-d...@googlegroups.com

How many iterations should we expect for page rank to converge?

Specifically I'm using seek="A", alpha = 0.3 and epsilon = 10^-5.

Thanks,

Eliot

--
Eliot Knudsen
Department of Statistics
Carnegie Mellon University
206.788.5515 | eknu...@andrew.cmu.edu

Elmer Garduno

unread,

Mar 25, 2012, 3:45:50 PM3/25/12

to machine-learning-with-large-d...@googlegroups.com

For me it converges in 12 scans.

Tarun Sharma

unread,

Mar 25, 2012, 3:51:40 PM3/25/12

to machine-learning-with-large-d...@googlegroups.com

Really! It takes 100 scans (not necessarily full scans) for me on Test.adj

--
Tarun Sharma

Graduate Research Assistant

School of Computer Science

Carnegie Mellon University

Eliot Knudsen

unread,

Mar 25, 2012, 7:06:40 PM3/25/12

to machine-learning-with-large-d...@googlegroups.com

I have the same thing as Tarun and I'm worried it isn't converging properly, but I'm not sure exactly how to debug this. Let me know if you have any suggestions.

Eliot

Tarun Sharma

unread,

Mar 25, 2012, 7:08:17 PM3/25/12

to machine-learning-with-large-d...@googlegroups.com

It converges really fast. What do you mean by not converging properly ?

Eliot Knudsen

unread,

Mar 25, 2012, 7:10:18 PM3/25/12

to machine-learning-with-large-d...@googlegroups.com

If it isn't updating correctly then it will converge in more (or fewer) scans. 100 scans is not very fast.

Eliot

Elmer Garduno

unread,

Mar 25, 2012, 7:33:34 PM3/25/12

to machine-learning-with-large-d...@googlegroups.com

You could check for invariants after each scan, like the total probability of p + r = 1, then you can see if your probs are going wild.

Tarun Sharma

unread,

Mar 25, 2012, 7:45:01 PM3/25/12

to machine-learning-with-large-d...@googlegroups.com

p+r is coming out to be 1 after each scan. No. of scans are still 100. Regarding no. of scans - I break the scan of file once i find any node with r_u/d_u greater than epsilon.

Tarun Sharma

unread,

Mar 25, 2012, 8:02:47 PM3/25/12

to machine-learning-with-large-d...@googlegroups.com

the no. of iterations are 12 when you don't break the scan of the file once you find the node with r_u/d_u greater than epsilon and continue scanning from the next line.

Tianle Huang

unread,

Mar 25, 2012, 8:47:08 PM3/25/12

to machine-learning-with-large-d...@googlegroups.com

<i think you can keep scanning the file to the end. After you finish
it, you can scan the file again. You can stop the scanning when you
find that for each file, no line meets the greater than condition.

On Sun, Mar 25, 2012 at 8:02 PM, Tarun Sharma

Ni Lao

unread,

Mar 25, 2012, 9:05:01 PM3/25/12

to machine-learning-with-large-d...@googlegroups.com

It would be inefficient to break scans at every push

Ni

William Cohen (CMU)

unread,

Mar 25, 2012, 9:59:24 PM3/25/12

to machine-learning-with-large-d...@googlegroups.com

This is correct - you should scan all the way to the end before you restart.

--
William W. Cohen
wco...@cs.cmu.edu
http://www.wcohen.com
Research Professor
Machine Learning Department, CMU

Reply all

Reply to author

Forward