Preserving PersonalizedPagerank in Subgraphs(Andrea Vattani, Deepayan Chakrabarti, Maxim Gurevich) ...
a a bc c
“Due to spaceconstraints, complete proofs of our claimswill appear in the fullversion of the paper.”
p = αr + (1 − α)A D t −1 ppαrAD
rr[i]
∞ [t]pi (j) = α(1 − α)pi (j) t=0 ...
G = (V, E) S⊂V p G pG[S] ˜ p G
˜min d(p , p G G[S] )
|S| = o(n/ log n) 1/2 − o(1) Ω(|S|)S ⊂S ∗ ...
wG (i, j) = 1j∈V
G = (V, wG ) S⊂VH = (S ∪ SIN K, wH )
pi (j) G = pi (j) H ∀i, j ∈ S
aa sampling a,c b SINK Remove bc c
∞wH (x, y)+ = (1 − α)wG (x, z)wG (z, y) [(1 − α)wG (z, z)] ...
wH (x, SIN K)+ = wG (x, z) − wH (x, y) y=z;wG (z,y)>0
P H pi H = pi G WH 1 ...
wH (u, v) < τwH (u, SIN K)+ = wH (u, v), wH (u, v) = 0
||P (j) − P (j)||1 H R 1−α ≤ 2τ |S| + 1 αP (j) HP (j) R
v= pj (i), G i∈S j∈V Sr(j) = r(j ), j, j ∈ V S pr (i), ...
SINK Page Rank
1 1wH (SOU RCE, l) = pj G ...
pr (i) = pr G H (i), ∀i ∈ S   r(k), k∈S r (k) = ρ|V S|, ...
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
Preserving Personalized Pagerank in Subgraphs(ICML 2011)
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

Related Documents