Using python networkX to calculate personalized page rank
I am trying to plot a directed graph and calculate the personalized page rank from that graph. Suppose I have a graph with vertices {1,2,3,4}
and edges going from 2, 3 and 4 to vertex 1, I would like:
(1) calculate the personalized page rank of each vertex relative to 1
(2) calculate the personalized page rank of each vertex relative to 2.
The question is how to pass this parameter in the personalized page ranking function. The following code doesn't seem to do what I want:
import networkx as nx G = nx.DiGraph() [G.add_node(k) for k in [1,2,3,4]] G.add_edge(2,1) G.add_edge(3,1) G.add_edge(4,1) ppr1 = nx.pagerank(G,personalization={1:1, 2:1, 3:1, 4:1}) ppr2 = nx.pagerank(G,personalization={1:2, 2:2, 3:2, 4:2})
Right now ppr1 == ppr2
, although it shouldn't be.
=============================================== === ================ UPDATE.
In response to the comment below, my understanding of personalized page rank comes from the following:
The equivalent definition refers to the terminal node of a random walk starting at s. Let (X0, X1, ..., XL) be a random walk starting from X0 = s of length L ~ Geometric (α). Here L ~ Geometric (α) we mean Pr [L = ] = (1−α)
α. This walk starts from s and does the following at each step: with probability α, ends; and with the remaining probability 1 - α, we continue the random neighbor of the current node. Here, if the current node is u, a random neighbor v ∈ N out (u) is chosen with probability wu, v if the graph is weighted or with a uniform probability 1 / dout (u) if the graph is unweighted. Then the PPR of any node t is the probability that this walk stops at t:
Found on page 6 of this thesis: https://cs.stanford.edu/people/plofgren/bidirectional_ppr_thesis.pdf
So, I suppose what I'm looking for when calculating the "personalized page rank t with respect to s" is if we start a random walk from s according to the process described above, what is the probability that this transition ends at t ...
source to share
In conceptualizing PageRank, the casual surfer navigates to the following links. At each step, there is a nonzero chance that the surfer will land on a random page (as opposed to a link). If the selection of this random page is weighted, then it is called a personalized PageRank.
In your case, you want to navigate to one specific page. Therefore, you need to say that all other pages have zero chance of selection in those steps where the surfer is jumping, and not after the edge.
ppr1 = nx.pagerank(G,personalization={1:1, 2:0, 3:0, 4:0})
ppr2 = nx.pagerank(G,personalization={1:0, 2:1, 3:0, 4:0})
source to share