6
$\begingroup$

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.

Improve this question
$\endgroup$
12
  • 5
    $\begingroup$ Not sure why this was downvoted. It's a modelling question. $\endgroup$
    – Suresh Venkat
    Commented Aug 15, 2011 at 18:50
  • $\begingroup$ @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. $\endgroup$
    – Huck Bennett
    Commented Aug 15, 2011 at 21:27
  • $\begingroup$ 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. $\endgroup$
    – Fomite
    Commented Aug 15, 2011 at 21:42
  • $\begingroup$ 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. $\endgroup$
    – Huck Bennett
    Commented Aug 15, 2011 at 22:43
  • 1
    $\begingroup$ 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. $\endgroup$
    – Fomite
    Commented Aug 15, 2011 at 23:03

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Huck Bennett
    Commented Aug 15, 2011 at 17:03
  • $\begingroup$ 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. $\endgroup$
    – Fomite
    Commented Aug 15, 2011 at 21:02
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Fomite
    Commented Aug 15, 2011 at 20:55
  • $\begingroup$ 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. $\endgroup$
    – Fomite
    Commented Aug 15, 2011 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.