<p>I'm not familiar at all with details of the PageRank theory, but here's an intuitive answer: Suppose you have a huge connected graph plus a single isolated vertex that you wish to reach. Without random jumps there's no hope to stop surfing. Does the algorithm exclude such bad instances? More generally if the graph is disconnected the jumps would be necessary to reach every vertex.</p>

CC BY-SA 3.0
2011-08-15T17:03:14.010Z
If a vertex has no incoming edges (is a rank source), then it will be unreachable and have 0 rank. If a vertex has no outgoing edges (is a rank sink), then rank will not be conserved in subsequent iterations. I.e., a vertex being weakly (but not strongly) connected causes problems; it doesn't have to be isolated.
Huck Bennett
CC BY-SA 3.0
2011-08-15T21:02:11.143Z
There are a number of unreachable "rank source" nodes in the network, but why is it necessarily bad for them to have 0 rank. If what you're interested in is the relative scale of "A is more important than B", why do nodes need to have a positive rank? There's a single rank sink, but I'm less worried about it's rank being stable, as its an artificial construct that's there to let you calculate betweenness centrality.
Fomite
CC BY-SA 3.0
2011-08-15T16:26:24.373Z
2011-08-15T17:02:37.350Z
2011-08-15T17:02:37.350Z
Mahdi Cheraghchi
<p>Let $\alpha$ be the probability of clicking through a link and let $1-\alpha$ be the probability of going to a random website. I think you're asking whether PageRank will work with $\alpha=1$. The answer is yes if and only if the network is strongly connected and the induced random walk is aperiodic. I'm not sure what "entirely closed" means.</p>

<p>Setting $\alpha = 1 $ gives intuition for how PageRank works, but there are very good reasons for setting $\alpha &lt; 1$. Namely, we want PageRank (1) to converge in every graph, (2) to converge to the same thing regardless of the initial rank distribution, (3) to converge as quickly as possible. PageRank is just a fancy name for how to set up a particular Markov Chain. For any $\alpha \in [0,1] $ you'll get <em>some</em> Markov Chain, you just need to make sure that it has properties 1-3.</p>

<p>This is the best PageRank survey that I've seen (better than Wikipedia or the original paper) and explains this: <a href="http://www.ams.org/samplings/feature-column/fcarc-pagerank" rel="nofollow">http://www.ams.org/samplings/feature-column/fcarc-pagerank</a></p>

<p>Edit: As per MCH's answer we also want the 4th condition that every vertex has positive rank, which is also ensured by the random surfer model.</p>

CC BY-SA 3.0
2011-08-15T20:55:17.390Z
Thanks for the link, it was quite helpful. I've edited the initial post to include some details about the network itself, which will hopefully be helpful.
Fomite
CC BY-SA 3.0
2011-08-15T21:03:30.160Z
What I mean by entirely closed is there is nowhere for the random surfer to jump *to*. If they leave our chain of links to go to a new site, the only place they have to go is back to the original chain of links.
Fomite
CC BY-SA 3.0
2011-08-15T16:37:18.027Z
2011-08-15T17:01:40.330Z
2011-08-15T17:01:40.330Z
Huck Bennett
<p>I'm looking to adapt the PageRank algorithm as a centrality measure in a network. This network however, unlike the "random surfer" of the original paper on PageRank, or the random library browser for Eigenfactor.org, doesn't have a random browser who can leave and jump off to some other network. The theoretical reader is reading <em>only</em> this literature, and reading it completely.</p>

<p>As I understand it, the damping factor in the usual implementation of PageRank is 1 - probability of the random surfer jumping to a different site, and is usually set at 0.85. Is it reasonable then, in an entirely closed network, to set this value = 1.0, or is there something I'm not seeing?</p>

<p>Some details of the network, which would probably be helpful:</p>

<p>All the networks I will be looking at are fairly small, less than 1000 nodes, and directed. They're citation networks - with papers as nodes and edges as citations between papers, so inherently there are no isolated nodes not connected to any other nodes, as their inclusion in the network is conditional on there being a link to or from the network. There's no reason to believe the network is strongly connected - indeed, I'm pretty sure they're inherently not.</p>

CC BY-SA 3.0
2011-08-15T18:50:37.143Z
Not sure why this was downvoted. It's a modelling question.
Suresh Venkat
CC BY-SA 3.0
2011-08-15T21:27:54.337Z
@EpiGrad: That's a weird use of PageRank since your graph is a DAG. However, PageRank is commonly used for studying related things such as citations between authors or journals where the induced graph is in general not a DAG.
Huck Bennett
CC BY-SA 3.0
2011-08-15T21:42:50.610Z
It's more commonly used that way, yes - but is there a reason it cannot be used with a DAG? The analysis is also using betweenness centrality, but when you look at the relative importance of particular papers using Betweenness vs. PageRank, there's some subtle differences. The network being a DAG is what prompted the damping factor question to begin with.
Fomite
CC BY-SA 3.0
2011-08-15T22:43:52.633Z
Using PageRank on a DAG makes no sense. It won't work *at all* with $\alpha = 1$ since all the rank will flow out through the sinks (i.e. after running the chain for awhile EVERY vertex in your graph will have rank 0). With $\alpha < 1$ the chain will converge, but not to anything meaningful.
Huck Bennett
CC BY-SA 3.0
2011-08-15T23:03:52.037Z
I just ran the PageRank centrality implementation in Python using NetworkX, and got non-zero ranks for all the nodes, that provide roughly the same ranking as betweenness centrality - as expected - and produce the same results on multiple runs of the network. This seems to be in contradiction to your assertion that it won't work at all.
Fomite
CC BY-SA 3.0
2011-08-17T16:21:30.457Z
What $\alpha$ did you use? There's a simple reason for what I said. Please look at the 2 node graph in the section "Three important questions" (single node rank sink) and the 8 node graph in the section "When things go wrong" (multi-node rank sink): http://www.ams.org/samplings/feature-column/fcarc-pagerank
Huck Bennett
CC BY-SA 3.0
2011-08-17T18:59:39.287Z
Am I missing something or your modelling gives exactly the betweenness centrality ?
Sylvain Peyronnet
CC BY-SA 3.0
2011-08-17T20:50:00.167Z
Currently away from my computer, I'll post more details when I get home.
Fomite
CC BY-SA 3.0
2011-09-03T19:54:49.620Z
Additionally, the article linked above states: "This has the effect of modifying the hyperlink matrix H by replacing the column of zeroes corresponding to a dangling node with a column in which each entry is 1/n." - which suggests this "the whole network will be drained to rank 0" thing...just isn't a problem.
Fomite
CC BY-SA 3.0
2011-08-19T16:58:18.510Z
Using this network: http://i1208.photobucket.com/albums/cc372/EpiGrad/example_network.png (ignore the colors), where the network is directed and all links flow "up" the diagram, I modeled both betweenness centrality and PageRank using NetworkX. I get this figure: http://i1208.photobucket.com/albums/cc372/EpiGrad/page_between.png - which shows that they're clearly pretty heavily correlated, but not identical, and seems to be at odds with the notion that on a graph like this, PageRank will terminally fail. This was at an alpha of 1.0.
Fomite
CC BY-SA 3.0
2011-08-19T17:06:20.437Z
Also tried comparing the results at alpha = 0.85 to alpha = 1.0. While the values change slightly, the ranking never does, and the two are *extremely* highly correlated.
Fomite
CC BY-SA 3.0
2011-08-27T00:27:31.673Z
Still looking for a compelling explanation of why this seems to be working, if Huck Bennet's assertion that shouldn't is correct.
Fomite
<ds.algorithms><advice-request><formal-modeling><ni.networking-internet>
PageRank for a Non-Random Searcher
Fomite
# PageRank for a Non-Random Searcher

(Asked by: username_0 on 2011-08-15)

I'm looking to adapt the PageRank algorithm as a centrality measure in a network. This network however, unlike the "random surfer" of the original paper on PageRank, or the random library browser for Eigenfactor.org, doesn't have a random browser who can leave and jump off to some other network. The theoretical reader is reading *only* this literature, and reading it completely.

As I understand it, the damping factor in the usual implementation of PageRank is 1 - probability of the random surfer jumping to a different site, and is usually set at 0.85. Is it reasonable then, in an entirely closed network, to set this value = 1.0, or is there something I'm not seeing?

Some details of the network, which would probably be helpful:

All the networks I will be looking at are fairly small, less than 1000 nodes, and directed. They're citation networks - with papers as nodes and edges as citations between papers, so inherently there are no isolated nodes not connected to any other nodes, as their inclusion in the network is conditional on there being a link to or from the network. There's no reason to believe the network is strongly connected - indeed, I'm pretty sure they're inherently not.

**Tags:** ds.algorithms, advice-request, formal-modeling, ni.networking-internet
> **Comments:**
> **username_1**: Not sure why this was downvoted. It's a modelling question.  
> **username_2**: @EpiGrad: That's a weird use of PageRank since your graph is a DAG. However, PageRank is commonly used for studying related things such as citations between authors or journals where the induced graph is in general not a DAG.  
> **username_0**: It's more commonly used that way, yes - but is there a reason it cannot be used with a DAG? The analysis is also using betweenness centrality, but when you look at the relative importance of particular papers using Betweenness vs. PageRank, there's some subtle differences. The network being a DAG is what prompted the damping factor question to begin with.  
> **username_2**: Using PageRank on a DAG makes no sense. It won't work *at all* with $\alpha = 1$ since all the rank will flow out through the sinks (i.e. after running the chain for awhile EVERY vertex in your graph will have rank 0). With $\alpha < 1$ the chain will converge, but not to anything meaningful.  
> **username_0**: I just ran the PageRank centrality implementation in Python using NetworkX, and got non-zero ranks for all the nodes, that provide roughly the same ranking as betweenness centrality - as expected - and produce the same results on multiple runs of the network. This seems to be in contradiction to your assertion that it won't work at all.  
> **username_2**: What $\alpha$ did you use? There's a simple reason for what I said. Please look at the 2 node graph in the section "Three important questions" (single node rank sink) and the 8 node graph in the section "When things go wrong" (multi-node rank sink): http://www.ams.org/samplings/feature-column/fcarc-pagerank  
> **username_3**: Am I missing something or your modelling gives exactly the betweenness centrality ?  
> **username_0**: Currently away from my computer, I'll post more details when I get home.  
> **username_0**: Using this network: http://i1208.photobucket.com/albums/cc372/EpiGrad/example_network.png (ignore the colors), where the network is directed and all links flow "up" the diagram, I modeled both betweenness centrality and PageRank using NetworkX. I get this figure: http://i1208.photobucket.com/albums/cc372/EpiGrad/page_between.png - which shows that they're clearly pretty heavily correlated, but not identical, and seems to be at odds with the notion that on a graph like this, PageRank will terminally fail. This was at an alpha of 1.0.  
> **username_0**: Also tried comparing the results at alpha = 0.85 to alpha = 1.0. While the values change slightly, the ranking never does, and the two are *extremely* highly correlated.  
> **username_0**: Still looking for a compelling explanation of why this seems to be working, if Huck Bennet's assertion that shouldn't is correct.  
> **username_0**: Additionally, the article linked above states: "This has the effect of modifying the hyperlink matrix H by replacing the column of zeroes corresponding to a dangling node with a column in which each entry is 1/n." - which suggests this "the whole network will be drained to rank 0" thing...just isn't a problem.  

---

## 2 answers

### Answer by username_4 on 2011-08-15. Score: 2 | Accepted answer

I'm not familiar at all with details of the PageRank theory, but here's an intuitive answer: Suppose you have a huge connected graph plus a single isolated vertex that you wish to reach. Without random jumps there's no hope to stop surfing. Does the algorithm exclude such bad instances? More generally if the graph is disconnected the jumps would be necessary to reach every vertex.

> **Comments:**
> **username_2**: If a vertex has no incoming edges (is a rank source), then it will be unreachable and have 0 rank. If a vertex has no outgoing edges (is a rank sink), then rank will not be conserved in subsequent iterations. I.e., a vertex being weakly (but not strongly) connected causes problems; it doesn't have to be isolated.  
> **username_0**: There are a number of unreachable "rank source" nodes in the network, but why is it necessarily bad for them to have 0 rank. If what you're interested in is the relative scale of "A is more important than B", why do nodes need to have a positive rank? There's a single rank sink, but I'm less worried about it's rank being stable, as its an artificial construct that's there to let you calculate betweenness centrality.  

---

### Answer by username_2 on 2011-08-15. Score: 4

Let $\alpha$ be the probability of clicking through a link and let $1-\alpha$ be the probability of going to a random website. I think you're asking whether PageRank will work with $\alpha=1$. The answer is yes if and only if the network is strongly connected and the induced random walk is aperiodic. I'm not sure what "entirely closed" means.

Setting $\alpha = 1 $ gives intuition for how PageRank works, but there are very good reasons for setting $\alpha < 1$. Namely, we want PageRank (1) to converge in every graph, (2) to converge to the same thing regardless of the initial rank distribution, (3) to converge as quickly as possible. PageRank is just a fancy name for how to set up a particular Markov Chain. For any $\alpha \in [0,1] $ you'll get *some* Markov Chain, you just need to make sure that it has properties 1-3.

This is the best PageRank survey that I've seen (better than Wikipedia or the original paper) and explains this: <http://www.ams.org/samplings/feature-column/fcarc-pagerank>

Edit: As per MCH's answer we also want the 4th condition that every vertex has positive rank, which is also ensured by the random surfer model.

> **Comments:**
> **username_0**: Thanks for the link, it was quite helpful. I've edited the initial post to include some details about the network itself, which will hopefully be helpful.  
> **username_0**: What I mean by entirely closed is there is nowhere for the random surfer to jump *to*. If they leave our chain of links to go to a new site, the only place they have to go is back to the original chain of links.  

---

