Himanshu Pandey commented on MADLIB-1084:

[~fmcquillan] [~njayaram] , 

I am referring to this 
[document|http://www-cs-students.stanford.edu/~taherh/papers/comparison.pdf] as 
well for Personalized Page Rank. So can we agree to this computation of PPR?

Let n be the number of pages on the web. Let x(v) denote the n-dimensional per- 
sonalized PageRank vector corresponding to the n-dimensional personalization 
vec- tor v. x(v) can be computed by solving the following eigenvalue problem, 
where A=cPT +(1−c)veT:
x = Ax                                    –- (2)

Rewriting the above, we see that
x = cP T x + (1 − c)v                      — (3)
x − cP T x = (1 − c)v                      — (4)
(I − cP T )x = (1 − c)v                    — (5)


I − cP is strictly diagonally dominant, so that I − cP is invertible. 
Therefore, (I − cP)T =I−cPT isalsoinvertible.Thus,we get that

x = (1 − c)(I − cPT )−1v                  — (6)

LetQ=(1−c)(I−cPT)−1. By letting v=ei, where ei is the ith elementary vector we 
see that the ith column of the matrix Q is x(ei), i.e., the personalized 
PageRank vector corresponding to the personalization vector ei.

The columns of Q comprise a complete basis for personalized PageRank vectors, 
as any personalized PageRank vector can be expressed as a convex combination of 
the columns of Q. For any personalization vector v, the corresponding 
personalized PageRank vector is given by Qv. This formulation corresponds to 
the original approach to personalizing PageRank suggested by Page et al. [7] 
that allows for personalization on arbitrary sets of pages.





> Graph - Personalized PageRank
> -----------------------------
>                 Key: MADLIB-1084
>                 URL: https://issues.apache.org/jira/browse/MADLIB-1084
>             Project: Apache MADlib
>          Issue Type: New Feature
>          Components: Module: Graph
>            Reporter: Frank McQuillan
>            Assignee: Himanshu Pandey
>            Priority: Major
>             Fix For: v1.14
> Personalized PageRank which is a variant of regular PageRank.
> Please refer to  
> [http://madlib.apache.org/docs/latest/group__grp__pagerank.html] as a 
> starting point.
> Reference:
>  Neighborhood Formation and Anomaly Detection in Bipartite Graphs
>  [http://www.cs.cmu.edu/~deepay/mywww/papers/icdm05.pdf]

This message was sent by Atlassian JIRA

Reply via email to