Transcript 复杂网络上随机游走的分析及应用研究

第六届全国网络科学论坛与第二届全国混沌应用研讨会
Random walks in
complex networks
章 忠 志
复旦大学计算科学技术学院
Email: [email protected]
Homepage: http://homepage.fudan.edu.cn/~zhangzz/
2010年7月26-31日
Contents
Brief introduction to our group
What is a random walk
Important parameter of random walks
Applications of random walks
Our work on Random walks:
trapping in complex networks
2/43
2010-06-03
Brief introduction to our group
 Research directions: structure and
dynamics in networks
 Modeling networks and Structural analysis
 Spectrum analysis and its application
 Enumeration problems: spanning trees,
perfect matching, Hamilton paths
 Dynamics: Random walks, percolation
3/43
2010-06-03
Random Walks on Graphs
-
4/43
2010-06-03
Random Walks on Graphs
-
At any node, go to one of the neighbors
of the node with equal probability.
5/43
2010-06-03
Random Walks on Graphs
-
At any node, go to one of the neighbors
of the node with equal probability.
6/43
2010-06-03
Random Walks on Graphs
-
At any node, go to one of the neighbors
of the node with equal probability.
7/43
2010-06-03
Random Walks on Graphs
-
At any node, go to one of the neighbors
of the node with equal probability.
8/43
2010-06-03
Random Walks on Graphs
-
At any node, go to one of the neighbors
of the node with equal probability.
9/43
2010-06-03
Important parameters of random walks
First-Passage Time F(s,t):
Expected number of steps to
reach t starting at s
Mean Commute time C(s,t):
重要指标
Steps from i to j, 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
Cover time, survival problity, ……
New J. Phys. 7, 26 (2005)
10/43
2010-06-03
Applications of random walks
 PageRank algorithm
 Community detection
 Recommendation systems
 Electrical circuits (resistances)
 Information Retrieval
 Natural Language Processing
 Machine Learning
 Graph partitioning
 In economics: random walk hypothesis
11/43
2010-06-03
Application to Community detection
World Wide Web
Citation networks
Social networks
Biological networks
Food Webs
Properties of community may be quite different
from the average property of network.
More links “inside” than “outside”
12/43
2010-06-03
Application to recommendation systems
IEEE Trans. Knowl. Data Eng. 19, 355 (2007)
13/43
2010-06-03
Connections with electrical networks
 Every edge – a resistor of 1 ohm.
 Voltage difference of 1 volt between u and v.
R(u,v) – inverse of electrical current from u to v.
_
v
u +
1
F ( s, t )   d z  R( s, t )  R(t , z )  R( s, z ) 
2 z
C(u,v) = F(s,t) + F(t,s) =2mR(u,v),
dz is degree of z, m is the number of edges
14/43
2010-06-03
Formulas for effective resistance
15/43
2010-06-03
Random walks and other topologies
Communtity structure
Spanning trees
Average distance
N
( u ,v )
ST
1
N ST (G)   i
N i 2
N (G)
R(u, v) 
N ST (G)
EPL (Europhysics Letters), 2010, 90:68002
16/43
2010-06-03
Our work: Random walks on complex
networks with an immobile trap
 Consider again a random
walk process in a network.
 In a communication or a
social network, a message
can disappear; for
example, due to failure.
 How long will the
message survive before
being trapped?
17/43
2010-06-03
Our work
Random walks on scale-free networks






A pseudofractal scale-free web
Apollonian networks
Modular scale-free networks
Koch networks
A fractal scale-free network
Scale-free networks with the same degree
sequences
Random walks on exponential networks
Random walks on fractals
18/43
2010-06-03
Main contributions
Methods for finding Mean first-passage time
(MFPT)




Backward equations
Generating functions
Laplacian spectra
Electrical networks
Uncover the impacts of structures on MFPT




Scale-free behavior
Tree-like structure
Modular structure
Fractal structure
19/43
2010-06-03
Walks on pseudofractal scale-free web
Physical Review E, 2009, 79: 021127.
主要贡献：(1)新的解析方法 (2)新发现
20/43
2010-06-03
Walks on Apollonian network
为发表时所报导的传输效率最高的网络
EPL, 2009, 86: 10006.
21/43
2010-06-03
Walks on modular scale-free networks
生成函数方法
Physical Review E, 2009, 80: 051120.
22/43
2010-06-03
Walks on Koch networks
Construction
Physical Review E, 2009, 79: 061113.
23/43
2010-06-03
Walks on Koch networks
Physical Review E, 2009, 79: 061113.
24/43
2010-06-03
Walks in extended Koch netoworks
25/43
2010-06-03
Walks on a fractal scale-free network
EPL (Europhysics Letters), 2009, 88: 10001.
26/43
2010-06-03
Walks on scale-free networks with
identical degree sequences
Physical Review E, 2009, 79: 031110.
27/43
2010-06-03
Walks on scale-free networks with
identical degree sequences
模型优点： (1) 不需要交叉边；(2)网络始终连通.
Physical Review E, 2009, 80: 061111
28/43
2010-06-03
Walks on exponential networks
Conclusion: MFPT depends on the location of trap.
Physical Review E, 2010, 81: 016114.
29/43
2010-06-03
Impact of trap position on MFPT in
scale-free networks
Journal of Mathematical Physics, 2009, 50: 033514.
30/43
2010-06-03
No qualitative effect of trap location
on MFPT in the T-graph
E. Agliari, Physical Review E, 2008, 77: 011128.
Zhang ZZ, et. al., New Journal of Physics, 2009, 11: 103043.
31/43
2010-06-03
Random Walks on Vicsek fractals
Physical Review E, 2010, 81:031118.
32/43
2010-06-03
Future work
1
Walks with multiple traps
2
Quantum walks on networks
3
Biased walks, e.g. walks on weighted nets
4
Self-avoid walks
33/43
2010-06-03
Thank You!