<4D F736F F F696E74202D20B5DAC1F9BDECC8ABB9FACDF8C2E7BFC6D1A7C2DBCCB32DD5C2D6D2D6BE>

Size: px

Start display at page:

Download "<4D F736F F F696E74202D20B5DAC1F9BDECC8ABB9FACDF8C2E7BFC6D1A7C2DBCCB32DD5C2D6D2D6BE>"

明巫
5 years ago
Views:

1 第六届全国网络科学论坛与第二届全国混沌应用研讨会 Random walks in complex networks 章忠志计算科学技术学院 Homepage: 年 7 月日

2 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/

3 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 Group Members Head: 章忠志 Phd candidates (2) : 张毅超, 李玲 Graduate students (2) : 伍顺琪, 李鹏程 Undergraduate students (8): 吴斌, 林苑, 殷铭, 高曙阳, 刘弘骁, 李明韫, 李欣彤, 盛益彬 3/

4 Random Walks on Graphs - 4/

5 Random Walks on Graphs - At any node, go to one of the neighbors of the node with equal probability. 5/

6 Random Walks on Graphs - At any node, go to one of the neighbors of the node with equal probability. 6/

7 Random Walks on Graphs - At any node, go to one of the neighbors of the node with equal probability. 7/

8 Random Walks on Graphs - At any node, go to one of the neighbors of the node with equal probability. 8/

9 Random Walks on Graphs - At any node, go to one of the neighbors of the node with equal probability. 9/

10 Important parameters of random walks 重要指标 New J. Phys. 7, 26 (2005) 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, 10/

11 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/

12 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/

13 Application to recommendation systems IEEE Trans. Knowl. Data Eng. 19, 355 (2007) 13/

14 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(,) st = dz Rst (,) + Rtz (, ) Rsz (, ) 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/

15 Formulas for effective resistance 15/

16 Random walks and other topologies Communtity structure Spanning trees Average distance Ruv (, ) = N ( uv, ) ( G) N ST ST ( G) N ST ( G) N 1 = N i= 2 λ i EPL (Europhysics Letters), 2010, 90: /

In a communication or a social network, a message can disappear; for

17 Ourwork:Randomwalksoncomplex networkswithanimmobiletrap 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/

18 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/

19 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/

20 Walks on pseudofractal scale-free web Physical Review E, 2009, 79: 主要贡献 :(1) 新的解析方法 (2) 新发现 20/

21 Walks on Apollonian network 为发表时所报导的传输效率最高的网络 EPL, 2009, 86: /

22 Walks on modular scale-free networks 生成函数方法 Physical Review E, 2009, 80: /

23 Walks on Koch networks Construction Physical Review E, 2009, 79: /

24 Walks on Koch networks Physical Review E, 2009, 79: /

25 Walks in extended Koch netoworks 25/

26 Walks on a fractal scale-free network EPL (Europhysics Letters), 2009, 88: /

27 Walks on scale-free networks with identical degree sequences Physical Review E, 2009, 79: /

28 Walks on scale-free networks with identical degree sequences 模型优点 : (1) 不需要交叉边 ;(2) 网络始终连通. Physical Review E, 2009, 80: /

29 Walks on exponential networks Conclusion: MFPT depends on the location of trap. Physical Review E, 2010, 81: /

30 Impact of trap position on MFPT in scale-free networks Journal of Mathematical Physics, 2009, 50: /

31 No qualitative effect of trap location on MFPT in the T-graph E. Agliari, Physical Review E, 2008, 77: Zhang ZZ, et. al., New Journal of Physics, 2009, 11: /

32 Random Walks on Vicsek fractals Physical Review E, 2010, 81: /

33 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/

一课程负责人情况姓名吴翊性别男出生年月 1948.08.28 1. 基本信息学位硕士职称教授职务所在院系理学院数学与系统科学系电话 13808485157 研究方向数据处理近三年来

一课程负责人情况姓名吴翊性别男出生年月 1948.08.28 1. 基本信息学位硕士职称教授职务所在院系理学院数学与系统科学系电话 13808485157 研究方向数据处理近三年来湖南省普通高等学校省级精品课程复核申报表学校名称 : 课程名称 : 课程负责人 : 立项时间 : 国防科技大学概率论与数理统计吴翊 2009 年课程网站地址 :jpkc2009.nudt.edu.cn/gllysltj jpkc.nudt.edu.cn/gltj 湖南省教育厅制二