http://www.icml-2011.org/papers/434_icmlpaper.pdf

Published on: **Mar 4, 2016**

Published in:
Technology

Source: www.slideshare.net

- 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