v v c(v) d(v) v 2 d(v)(d(v) )/2 2 2 v v : API G(V, E) V = {v, v 2,..., v n } ( ) n = V E v V N(v) = w V : (v, w) E v d(v) = N(v) 2. 2

Size: px

Start display at page:

Download "v v c(v) d(v) v 2 d(v)(d(v) )/2 2 2 v v : API G(V, E) V = {v, v 2,..., v n } ( ) n = V E v V N(v) = w V : (v, w) E v d(v) = N(v) 2. 2"

たみえうばら
5 years ago
Views:

1 DEIM Forum 208 I ID API Simple Random Walk with re-weighting (SRW-rw) Non-Backtracking Random Walk with re-weighting (NBRW-rw) Metropolis-Hastings Random Walk (MHRW). Online Social Networks (OSNs) world wide web ID [] [2] [3] [4] ID ID ID [5] (BFS) [6] OSN API [2] Facebook Facebook [7], [8] ( ) Simple Random Walk with re-weighting (SRW-rw) [5], [9] Metropolis-Hastings Random Walk (MHRW) [5], [9], [0] Non-backtracking Random Walk with re-weighting (NBRWrw) [7]

v v c(v) d(v) v 2 d(v)(d(v) )/2 2 2 v v : API 2 3 4 5 6 2. 2. G(V, E) V = {v, v 2,..., v n } ( ) n = V E v V N(v) = w V : (v, w) E v d(v) = N(v) 2. 2 2. 2. k p(k) p(k) k γ [] 2. 2. 2 [2] [] [] d(v)(d(v) )/2 v i c(v) 0 d(v) = 0 d(v) = c(v) = 2 i () otherwise d(v)(d(v) ) c(v) [0, ] C C = c(v) (2) n v V c(v) C G C [0, ] C = C [] C Counting Triangles 3.

2 v v c(v) d(v) v 2 d(v)(d(v) )/2 2 2 v v : API G(V, E) V = {v, v 2,..., v n } ( ) n = V E v V N(v) = w V : (v, w) E v d(v) = N(v) k p(k) p(k) k γ [] [2] [] [] d(v)(d(v) )/2 v i c(v) 0 d(v) = 0 d(v) = c(v) = 2 i () otherwise d(v)(d(v) ) c(v) [0, ] C C = c(v) (2) n v V c(v) C G C [0, ] C = C [] C Counting Triangles 3. 3 Simple Random Walk with Re-weighting (SRW-rw) Nonbacktracking Random Walk with Re-weighting (NBRW-rw) Metropolis-Hastings Random Walk (MHRW) 3. f : V R u def = [u(), u(2),..., u(n)] = [/n, /n,..., /n] E u(f) def = f(v) n v V G (P{D G = d}, d =, 2,..., n ) (3)

3 v V f(v) = l {d(v)=d} d(v) = d f(v) = f(v) = 0 f G G {X t V, t = 0,...} P def = {P (v, w)} v,w V P (v, w) = P{X t+ = w X t = v}, v, w V, (4) v V w V P (v, w) = (v, w) E P (v, w) > = 0 v w G P (v, v) > 0 v V P (v, w) = 0, (v, w) / E (v w) π = [π(v), v V ] f : V R ˆµ t (f) def = t t f(x s ) (5) s= π f E π (f) def = π(i)f(i). (6) i V [2] {X t } π P{X 0 = v}, v V, ( t ) ˆµ t (f) E π (f) almost surely (a.s.) (7) E π( f ) < 3. 2 Simple Random Walk with Re-weighting SRW-rw SRW-rw SRW SRW SRW G SRW SRW {X t } P SRW = P SRW (v, w) v,w V P SRW (v, w) P SRW (v, w) = { d(v) (v, w) E 0 otherwise 2 (8) 2: SRW P SRW π SRW (v) = d(v)/(2 E ), v V SRW t {X s } t s= f : V R w : V R w(v) = u(v) π(v) = n 2 E d(v), v V. t ˆµ t (wf) = t t w(x s )f(x s ) E π (wf) = E u (f) a.s.(9) s= n E t ˆµ t (wf) ˆµ t (w) = t s= w(x s)f(x s ) t s= w(x s) E u (f) a.s. (0) w(v) = /d(v) ˆµ t(wf)/ˆµ t(w), w(v) = /d(v)(v V ) SRW-rw SRW-rw G P{D G = d} v V f(v) = l {d(v)=d} d ˆµ t (wf) ˆµ t (w) = t s= l {d(x s)=d}/d(x s ) t s= /d(x s) v V l {d(v)=d} n a.s., ˆµ t(wf)/ˆµ t(w) P{D G = d} SRW-rw 3. 3 Non-backtracking Random Walk with Reweighting Non-backtracking Random Walk with Reweighting (NBRW-rw) [7] NBRW-rw NBRW

4 4: MHRW 3: NBRW SRW-rw NBRW-rw SRW-rw [7] NBRW NBRW 3 NBRW-rw NBRW t X t V X t X t+ X t X t {X t} t>= 0 V [7] t t f(x s) E π (f)a.s. () s= π SRW SRW [7] NBRW-rw SRW-rw 3. 4 Metropolis-Hastings Random Walk SRW NBRW MHRW Metropolis-Hastings (MH) [3] µ MCMC µ v = n min(, ) (v, w) E d(v) d(w) P MH (v, w) = y v P MH (v, y) w = v (2) 0 otherwise 4 π MH (v) = n SRW MHRW MH Algorithm X t V MHRW t X 0 Algorithm Algorithm MHRW MH (at time t) N(X t ) w p U(0, ) if p < d(x t ) = then d(w) X t+ v else X t+ X t end if P MH (v, v) t X t w w MHRW SRW-rw MHRW MHRW t {X t } t s= f : V R t t t f(x t) E u(f) a.s., (3) s= Algorithm MHRW v v v

Stanford Network Analysis Project (SNAP) [4] 5: (a) 0000 (b) 0000 6: : n Amazon 334,863 5.530 0.

5 f(v) v V ( 5 ) SRW NBRW MHRW < = f(v) f(v) v Counting Triangles 5 f(v) = c(v) f(v) Counting Triangles f(v) = ϕ k w(v) [8] ϕ k k k + k 0 w(v) 4. SRW-rw NBRW-rw MHRW 4. Stanford Network Analysis Project (SNAP) [4] 5: (a) 0000 (b) : : n Amazon 334, DBLP 37, Gowalla 96, SRW NBRW MHRW 00 6a SRW NBRW MHRW ( ) b 0000 NBRW SRW MHRW (NRMSE) [5] NMRSE NMRSE Ĉ E[(Ĉ C C)2 ] 7

6 7: Counting Triangles NRMSE 8: Counting Triangles NRMSE SRW-rw Counting Triangles NRMSE Amazon DBLP 00 Gowalla 0 5 f : V R f(v) = c(v), v V c(v) SRW-rw Counting Triangles. 8 Counting Triangles NEMSE 00 SRW-rw NBRW-rw MHRW Counting Triangles [8], [6] MHRW Counting Triangles P{D g > d} (CCDF) SRW-rw NBRW-rw MHRW P{D g > d} f(v) = l {d(v)>d} v V NRMSE NRMSE x E[(ˆx(t) x)2 ] ˆx(t) t x x = lim t ˆx(t) 9 00 NRMSE MHRW SRW-rw NBRW-rw SRW-rw NBRW-rw f(v) 8,9 f(v) 7 Counting Triangles NRMSE Counting Triangles f(v) f(v)

7 MHRW SRW-rw Lee [7] SRW-rw NBRW-rw NBRW-rw SRW-rw Hardiman Katzir [6] Counting Triangles SRW-rw [8] Counting Triangles NBRW-rw SRW-rw MHRW Counting Triangles. Chiericetti [7] MHRW Rejection sampling Maximum-degree sampling 6. 9: P{D g > d} d NRMSE Counting Triangles 8,9 NBRW SRW MHRW NBRW vs. SRW [7], [8] 9 NRMSE SRW NBRW NBRW NBRW SRW 6 NBRW SRW SRW NBRW 8 NBRW SRW MHRW SRW 8 MHRW SRW DBLP 5. Gjoka [2] SRW SRW-rw MH MHRW Counting Triangles SRWrw NBRW-rw MHRW NBRW-rw SRW-rw MHRW f(v) NEDO JSPS K2406

8 [] Y.Y. Ahn, S. Han, H. Kwak, S. Moon, and H. Jeong. Analysis of topological characteristics of huge online social networking services. In Proceedings of the 6th international conference on World Wide Web, pp ACM, [2] M. Gjoka, M. Kurant, C.T. Butts, and A. Markopoulou. Walking in Facebook: A case study of unbiased sampling of OSNs. In Proceedings IEEE Infocom, pp. 9. IEEE, 200. [3] A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, and B. Bhattacharjee. Measurement and analysis of online social networks. In Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, pp ACM, [4] J. Leskovec and C. Faloutsos. Sampling from large graphs. In Proceedings of the 2th ACM SIGKDD international conference on Knowledge discovery and data mining, pp ACM, [5] M. Gjoka, M. Kurant, C. T. Butts, and A. Markopoulou. Practical recommendations on crawling online social networks. Selected Areas in Communications, IEEE Journal on, Vol. 29, No. 9, pp , 20. [6] M. Kurant, A. Markopoulou, and P.dd Thiran. Towards unbiased bfs sampling. Selected Areas in Communications, IEEE Journal on, Vol. 29, No. 9, pp , 20. [7] C. H. Lee, X. Xu, and D. Y. Eun. Beyond random walk and metropolis-hastings samplers: why you should not backtrack for unbiased graph sampling. In ACM SIGMET- RICS Performance Evaluation Review, Vol. 40, pp , 202. [8] K. Iwasaki, K. Shudo. Estimating the clustering coefficient of a social network by a non-backtracking random walk. In IEEE BigComp 208, pp IEEE, 208. [9] A. H. Rasti, M. Torkjazi, R. Rejaie, N. Duffield, W. Willinger, and D. Stutzbach. Respondent-driven sampling for characterizing unstructured overlays. In INFOCOM 2009, IEEE, pp IEEE, [0] M. Al Hasan and M. J. Zaki. Output space sampling for graph patterns. Proceedings of the VLDB Endowment, Vol. 2, No., pp , [],.., 200. [2] G. L. Jones, et al. On the markov chain central limit theorem. Probability surveys, Vol., pp , [3] W. K. Hastings. Monte carlo sampling methods using markov chains and their applications. Biometrika, Vol. 57, No., pp , 970. [4] Stanford large network dataset collection. snap.stanford.edu/data/. [5] K. Avrachenkov, B. Ribeiro, and D. Towsley. Improving random walk estimation accuracy with uniform restarts. In International Workshop on Algorithms and Models for the Web-Graph, pp Springer, 200. [6] S. J. Hardiman and L. Katzir. Estimating clustering coefficients and size of social networks via random walk. In Proceedings of the 22nd international conference on World Wide Web, pp International World Wide Web Conferences Steering Committee, 203. [7] F. Chiericetti, A. Dasgupta, R. Kumar, S. Lattanzi, and T. Sarlós. On sampling nodes in a network. In Proceedings of the 25th International Conference on World Wide Web, pp International World Wide Web Conferences Steering Committee, 206. MHRW Counting Triangles Counting Triangles SRW NBRW Counting Triangles [8], [6] Counting Triangles [2] Counting Triangles 2 v v 2 v v 2 v v 2 v SRW d(v)/(d(v) ) NBRW 0 v N(v 2) v 2 N(v ) v v 2 SRW NBRW Counting Triangles v v = {v } v 2 = {v } 2 MHRW Counting Triangles MHRW SRW NBRW v = {v } v 2 = {v } v v 2 MHRW 2 v v {MHRW Algorithm w} v 2 {v v N(v)/{v } } v 2 N(v ) v MHRW v Counting Triangles. MHRW Counting Triangles Counting Triangles

27 YouTube YouTube UGC User Generated Content CDN Content Delivery Networks LRU Least Recently Used UGC YouTube CGM Consumer Generated Media CGM CGM U

YouTube 2016 2 16 27 YouTube YouTube UGC User Generated Content CDN Content Delivery Networks LRU Least Recently Used UGC YouTube CGM Consumer Generated Media CGM CGM UGC UGC YouTube k-means YouTube YouTube