Personalized PageRank

In the original PageRank, the damping factor is the probability of the surfer continues browsing at each step. The surfer may also stop browsing and start again from a random vertex. In personalized PageRank, the surfer can only start browsing from a given set of source vertices both at the beginning and after stopping.

Specifications

tg_pageRank_pers(SET<VERTEX> source, STRING e_type,
FLOAT max_change=0.001, INT max_iter=25, FLOAT damping = 0.85, INT top_k = 100
BOOL print_accum = TRUE, STRING result_attr = "", STRING file_path = "")

Characteristic	Value
Result	Computes a personalized PageRank value (FLOAT type) for each vertex.
Input Parameters	SET<VERTEX> source: Set of seed vertices STRING e_type: Names of edge type to use FLOAT max_change: PageRank will stop iterating when the largest difference between any vertex's current score and its previous score ≤ max_change. That is, the scores have become very stable and are changing by less than max_change from one iteration to the next. INT max_iter: Maximum number of iterations. FLOAT damping: Fraction of score that is due to the score of neighbors. The balance (1 - damping) is a minimum baseline score that every vertex receives. INT top_k: Sort the scores highest first and output only this many scores BOOL print_accum: If True, output JSON to standard output STRING result_attr: If not empty, store PageRank values (FLOAT) to this attribute STRING file_path: If not empty, write output to this file.
Result Size	V = number of vertices
Time Complexity	O(E*k), E = number of edges, k = number of iterations. The number of iterations is data-dependent, but the user can set a maximum. Parallel processing reduces the time needed for computation.
Graph Types	Directed edges

Example

We ran Personalized PageRank on the graph social10 using Friend edges with the following parameter values:

# Using "_" to use default values
RUN QUERY tg_pageRank_pers([("Fiona","Person")], "Friend", _, _, _, _, _, _,
_)

In this case, the random walker can only start or restart walking from Fiona. In the figure below, we see that Fiona has the highest PageRank score in the result. Ivy and George have the next highest scores because they are direct out-neighbors of Ivy and there are looping paths that lead back to them again. Half of the vertices have a score of 0 since they can not be reached from Fiona.

Visualized results of example query on social10 graph, with Friend edges