[
https://issues.apache.org/jira/browse/MADLIB-1084?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16363209#comment-16363209
]
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?
{code}
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.
{code}
Thoughts?
> 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
(v7.6.3#76005)
