of 69

# Preserving Personalized Pagerank in Subgraphs(ICML 2011)

http://www.icml-2011.org/papers/434_icmlpaper.pdf
Published on: Mar 4, 2016
Published in: Technology
Source: www.slideshare.net

#### Transcripts - Preserving Personalized Pagerank in Subgraphs(ICML 2011)

• 1. Preserving PersonalizedPagerank in Subgraphs(Andrea Vattani, Deepayan Chakrabarti, Maxim Gurevich) 1
• 2. a a bc c
• 3. “Due to spaceconstraints, complete proofs of our claimswill appear in the fullversion of the paper.”
• 4. p = αr + (1 − α)A D t −1 ppαrAD
• 5. rr[i]
• 6. ∞ [t]pi (j) = α(1 − α)pi (j) t=0 t [t] 1 pi (j) = d+ (kl ) k1 =i,k2 ,··· ,kt+1 =j l=1
• 7. G = (V, E) S⊂V p G pG[S] ˜ p G
• 8. ˜min d(p , p G G[S] )
• 9. |S| = o(n/ log n) 1/2 − o(1) Ω(|S|)S ⊂S ∗ u S ∗S u ∗ u
• 10. wG (i, j) = 1j∈V
• 11. G = (V, wG ) S⊂VH = (S ∪ SIN K, wH )
• 12. pi (j) G = pi (j) H ∀i, j ∈ S
• 13. aa sampling a,c b SINK Remove bc c
• 14. ∞wH (x, y)+ = (1 − α)wG (x, z)wG (z, y) [(1 − α)wG (z, z)] t t=0
• 15. wH (x, SIN K)+ = wG (x, z) − wH (x, y) y=z;wG (z,y)>0
• 16. P H pi H = pi G WH 1 t WH = (I − α(P ) ) H −1 1−α O(E + |S| ) 2
• 17. wH (u, v) < τwH (u, SIN K)+ = wH (u, v), wH (u, v) = 0
• 18. ||P (j) − P (j)||1 H R 1−α ≤ 2τ |S| + 1 αP (j) HP (j) R
• 19. v= pj (i), G i∈S j∈V Sr(j) = r(j ), j, j ∈ V S pr (i), ∀i ∈ S G
• 20. SINK Page Rank
• 21. 1 1wH (SOU RCE, l) = pj G (k)wG (k.l), l ∈ S |V S| α j,k∈V S wH (SOU RCE, SIN K) = 1 − wH (SOU RCE, i) i∈S
• 22. pr (i) = pr G H (i), ∀i ∈ S   r(k), k∈S r (k) = ρ|V S|, k = SOU RCE  0, k = SIN K