报告人：林 苑 指导老师：章忠志 副教授 复旦大学

Presentation on theme: "报告人：林 苑 指导老师：章忠志 副教授 复旦大学"— Presentation transcript:

1 报告人：林 苑 指导老师：章忠志 副教授 复旦大学 2010.10.17
第六届全国复杂网络会议 CCCN2010 DETERMINING MEAN FIRST-PASSAGE TIME ON A CLASS OF TREELIKE REGULAR FRACTALS 报告人：林　苑 指导老师：章忠志 副教授 复旦大学

2 PUBLICATIONS 01:29:47 [1] Lin Yuan(林苑), Wu Bin, Zhang Zhongzhi(指导教师). Exactly determining mean first-passage time on a class of regular fractals, Physical Review E, 2010, 82: [2] Zhang Zhongzhi(指导教师), Lin Yuan(林苑), et al. Trapping in scale-free networks with hierarchical organization of modularity, Physical Review E, 2009, 80: [3] Zhang Zhongzhi(指导教师), Lin Yuan(林苑), et al. Mean first-passage time for random walks on the T-graph, New Journal of Physics, 2009, 11: [4] Zhang Zhongzhi(指导教师), Lin Yuan(林苑), et al. Average distance in a hierarchical scale-free network: an exact solution. Journal of Statistical Mechanics: Theory and Experiment, 2009, P10022. [5] Zhang Zhongzhi(指导教师), Qi Yi, Zhou Shuigeng, Lin Yuan(林苑), and Guan Jihong. Recursive solutions for Laplacian spectra and eigenvectors of a class of growing treelike networks, Physical Review E, 2009, 80: [6] Zhang Zhongzhi(指导教师), Zhou Shuigeng, Xie Wenlei, Chen Lichao, Lin Yuan(林苑), and Guan Jihong. Standard random walks and trapping on the Koch network with scale-free behavior and small-world effect, Physical Review E, 2009, 79:

3 OUTLINE Introduction about random walks
01:29:47 Introduction about random walks Important measures of random walks Applications of random walks MFPT on a class of treelike fractals

4 INTRODUCTION ABOUT RANDOM WALKS
01:29:47 -

5 INTRODUCTION ABOUT RANDOM WALKS
01:29:47 -

6 INTRODUCTION ABOUT RANDOM WALKS
01:29:47 -

7 INTRODUCTION ABOUT RANDOM WALKS
01:29:47 -

8 INTRODUCTION ABOUT RANDOM WALKS
01:29:47 -

9 IMPORTANT MEASURES OF RANDOM WALKS
01:29:47 Tij≠Tji Mean transit time Tij Mean return time Tii Cij=Tij+Tji Mean commute time Cij

10 APPLICATIONS OF RANDOM WALKS
01:29:47 PageRank algorithm Community detection Recommendation systems Electrical circuits (resistances) Information Retrieval Natural Language Processing Machine Learning Graph partitioning In economics: random walk hypothesis

11 APPLICATIONS OF RANDOM WALKS
01:29:47 Applications in real life

12 OUR WORK: TRAPPING PROBLEM
01:29:47 Imagine there are traps (or absorbers) on several certain vertices. We are interesting the time of absorption. For simplicity, we first consider the problem that only a single trap.

13 01:29:47 Determining mean first-passage time on a class of treelike regular fractals, Lin Yuan, Wu Bin, Zhang Zhongzhi, Physical Review E, 2010, 82:031140

14 网络构成 01:29:47

15 网络构成 01:29:47

16 网络构成：另一种方法 01:29:47 网络的构成具有自相似性

17 具有单个陷阱的随机游走 传统的方法：涉及到矩阵求逆 根据一类树状网络的结构特点，提出一种新方法 时间复杂度 O(n3)
01:29:47 传统的方法：涉及到矩阵求逆 时间复杂度 O(n3) 空间复杂度 O(n2) 根据一类树状网络的结构特点，提出一种新方法 得到精确解

18 计算平均游走时间 01:29:47 树状网络相邻两点的MFPT 这个结论对一般的树 拉拉状网络均成立。

19 计算平均游走时间 01:29:48 树状网络相邻两点的MFPT 网络上任意两点MFPT的演化规律

20 计算平均游走时间 树状网络相邻两点的MFPT 网络上任意两点MFPT的演化规律 平均游走时间 将每一代新增加的点进行分类，分别计算。
01:29:48 树状网络相邻两点的MFPT 网络上任意两点MFPT的演化规律 平均游走时间 将每一代新增加的点进行分类，分别计算。

21 结论(1) 01:29:48 平均随机游走时间服从幂率分布； 网络的参数m影响网络的吸收效率：随着m的增大， 网络的吸收效率增高。

22 全局平均随机游走时间 将任一点作为陷阱的平均吸收时间； 即网络上任意两点的平均首达时间(MFPT)。
01:29:48 将任一点作为陷阱的平均吸收时间； 即网络上任意两点的平均首达时间(MFPT)。 计算全局平均随机游走时间的经典方法：计算拉普拉 斯的伪逆矩阵。 时间复杂度 O(n3) 空间复杂度 O(n2)

23 全局平均随机游走时间 01:29:48 平均首达时间 网络的电阻

24 全局平均随机游走时间 01:29:48 平均首达时间 网络的电阻 拉普拉斯矩阵的特征值

25 全局平均随机游走时间 01:29:48 平均首达时间 网络的电阻 拉普拉斯矩阵的特征值 特征多项式的系数

26 结论(2) 01:29:48 全局平均随机游走时间同样服从幂率分布。 陷阱位置对网络的吸收效率没有实质影响，原因在于 网络的构造。

27 网络构成：另一种方法 01:29:48 网络的构成具有自相似性

28 小结 01:29:48 提出一类树状分形 中间点作为陷阱的随机游走 全局随机游走时间 对自相似网络具有普适性

29 01:29:48 Thank you