Random Walk on Graph undirected graph G(V,E) ●walk:v1,v2,.∈V that vi+1~vi random walk:vt1 is uniformly chosen from N(vi) u n v ud v adjacency matrix A P-DA d(u) pu,)=0 u=U u卡URandom Walk on Graph • undirected graph G(V, E) • walk: • random walk: v1, v2,... ⇥ V that vi+1 ￾ vi P = D￾1A adjacency matrix A D(u, v) = ￾ d(u) u = v 0 u ￾= v P(u, v) = ￾ 1 d(u) u ￾ v 0 u ⇥￾ v vi+1 is uniformly chosen from N(vi)