学位论文 > 优秀研究生学位论文题录展示

复杂网络的结构性质与随机游走

作　者: 齐轶
导　师: 章忠志；周水庚
学　校: 复旦大学
专　业: 计算机软件与理论
关键词: 复杂网络拓扑性质特征谱随机游走
分类号: O157.5
类　型: 硕士论文
年　份: 2010年
下　载: 472次
引　用: 0次
阅　读: 论文下载

内容摘要

复杂网络已成为学术界研究的热点,它在计算机,工程技术,社会,政治,经济等领域都有着潜在的,广泛的应用。现实世界中的网络非常普遍,但是人们对它们的结构属性与动力学行为却知之不多。本文分别从网络的结构性质和动力学特性两方面着手,按照复杂网络的一般研究思路,按照从指数型网络,小世界网络再到无标度网络的先后次序,紧密围绕目前公认的现实网络的主要结构指标和动力学特性,由浅入深地对复杂网络的结构性质以及网络上的随机游走问题进行了研究。在网络结构性质方面,使用离散数学,组合分析等方法解析计算了网络的主要结构性质,包括度分布、平均路径长度、簇系数、介数和度相关性等。尤其需要指出的是,本文还使用矩阵理论和图论的方法对网络的谱性质(特征值和特征向量)进行了详细的分析。提出了一种迭代算法计算得到了各代网络所对应的特征值与特征向量的递推表达式；与传统的数值计算方法相比较,本文提出的递推算法大大降低了计算的时间复杂度以及对存储空间的需求,并且适用于求解大规模网络的谱性质。在网络随机游走动力学方面,利用组合数学、网络特征谱等相关结论,求解了网络上经典随机游走问题的平均首次到达时间的精确结果,并且对网络上带有吸收点的随机游走问题进行了研究,提出了一种递推算法得到了网络上平均吸收时间的解析表达式,从而避开了经典方法中的矩阵求逆运算过程,大幅度提高了计算效率。特别地,我们首次发现：对于无标度网络而言,如果吸收点处于度大的节点上,其平均首次到达时间随着网络规模呈现亚线性方式增长,而以前所研究网络上的平均首次到达时间均以网络规模呈现超线性形式或线性形式增长,这一发现对于设计高传输效率的网络具有重要的理论指导意义。

全文目录

摘要  4-5
Abstract  5-6
第一章绪论  6-11
  1.1 网络拓扑结构的研究意义及现状  6-8
  1.2 网络随机游走的研究意义及现状  8-9
  1.3 本文的主要工作  9-11
第二章确定性均匀递归树的拓扑结构与随机游走  11-31
  2.1 引言  11
  2.2 网络模型的构造及其拓扑性质  11-17
  2.3 网络的Laplacian谱性质  17-21
  2.4 网络上随机游走的分析  21-29
  2.5 结论  29-31
第三章一类小世界网络的拓扑结构与随机游走  31-48
  3.1 引言  31
  3.2 网络模型的构造及其拓扑性质  31-34
  3.3 网络的Laplacian谱性质  34-44
  3.4 网络所有节点对之间MFPT指标的精确求解  44-47
  3.5 结论  47-48
第四章一个伪分形无标度网络的随机游走  48-57
  4.1 引言  48
  4.2 网络模型的构造  48-50
  4.3 问题描述  50-52
  4.4 平均首次到达时间的求解  52-55
  4.5 结论  55-57
第五章结论与展望  57-59
  5.1 结论  57-58
  5.2 展望  58-59
参考文献  59-66
硕士期间发表论文目录  66-67
硕士期间科研项目以及获奖情况  67-68
致谢  68-70

复杂网络的结构性质与随机游走

内容摘要

全文目录

相似论文