网络随机游走.pptx

Random walks works
Zhongzhi ZHANG (章忠志)
School puter Science, Fudan University
Email: ******@fudan.
Homepage: ./~zhangzz/
2017/7/20
Future work
Introduction to random walks on graphs
Applications of random walks
Trapping on graphs: Introduction and Review
Contents
Trapping works
2/43
2017/7/20
-
Random Walks on Graphs
Kinds of random walks:
Unbiased random walks, biased random walks, self-avoid walks, quantum walks, ect
3/43
2017/7/20
Random Walks on Graphs
At any node, go to one of the neighbors of the node with equal probability.
-
4/43
2017/7/20
Random Walks on Graphs
At any node, go to one of the neighbors of the node with equal probability.
-
5/43
2017/7/20
Random Walks on Graphs
At any node, go to one of the neighbors of the node with equal probability.
-
6/43
2017/7/20
Random Walks on Graphs
At any node, go to one of the neighbors of the node with equal probability.
-
7/43
2017/7/20
Random Walks on Graphs
At any node, go to one of the neighbors of the node with equal probability.
-
8/43
2017/7/20
Important parameters of random walks
Primary
Indicators
mute time C(s,t): Steps from s to t, and then go back C(t,s) = F(s,t) + F(t,s)
Mean Return time T(s,s): mean time for returning to node s for the first time after having left it
First-Passage Time F(s,t): Expected number of steps to reach t starting at s
Cover time, survival problity, ……
New J. Phys. 7, 26 (2005)
9/43
FPT for general graphs
is the Laplacian matrix defined as
Pseudoinverse of the Laplacian matrix
2017/7/20
10/43
N: Node number