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

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: 031140. [2] Zhang Zhongzhi(指导教师), Lin Yuan(林苑), et al. Trapping in scale-free networks with hierarchical organization of modularity, Physical Review E, 2009, 80: 051120. [3] Zhang Zhongzhi(指导教师), Lin Yuan(林苑), et al. Mean first-passage time for random walks on the T-graph, New Journal of Physics, 2009, 11: 103043. [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:016104. [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:061113.

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

INTRODUCTION ABOUT RANDOM WALKS 01:29:47 -

INTRODUCTION ABOUT RANDOM WALKS 01:29:47 -

INTRODUCTION ABOUT RANDOM WALKS 01:29:47 -

INTRODUCTION ABOUT RANDOM WALKS 01:29:47 -

INTRODUCTION ABOUT RANDOM WALKS 01:29:47 -

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

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

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

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.

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

网络构成 01:29:47

网络构成 01:29:47

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

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

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

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

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

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

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

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

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

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

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

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

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

01:29:48 Thank you