两类具有分形结构的无标度网络及相关问题

摘要

本文主要讨论了两类具有分形结构的无标度网络，称一个复杂网络具有分形结构，是说它能以某种方式嵌入到平面中的分形集。我们定义了两种不同的嵌入方式，并得到对应的递归集或sofic集的Hausdorff维数。同时，对第一类网络，我们研究了谱图理论中的平均首达时间的渐近性质。对第二类无标度网络，我们估计了不同条件下的 Laplace算子谱隙。并且在基图都是完全图的情况下，我们得到了Laplace算子谱隙严格正的充分必要条件。
　　具体的说，这两类无标度网络都是在一定规则下通过基图以某种递归方式生成的。在整篇论文中，基图结点集即一致记为Σ:={0,1,...,N?1},并被分成1型和2型两类字母，由此可定义出纯型1和纯型2的词。第n图的任意结点都是n长的词。本文中的两种嵌入方式分别是所有边的嵌入和增长边的嵌入。
　　在第3章，我们介绍了一类层级网络，他们的基图都是单一的完全图，第 n代图的结点集都是Σn。即所有 n长的词。一旦定义好第 n代图的边集，我们可以如下方式递归定义(n+1)代图的边集:将第n代图复制N份，并重新标记结点，然后将纯型1和纯型2的结点连接起来即生成(n+1)代图。我们证明了该类网络的无标度性和小世界性。并考虑了以所有边嵌入方式生成的分形集，证明了该嵌入集是递归集并给出了 Hausdorff维数的精确估计。最后我们还考虑了把陷阱点固定在所有纯型1或者纯型2的结点上的平均首达时间的渐近性质。
　　在第4章，基于动力系统中有限型子位移的思想，我们构造了另一类网络，基图是二分图，他们结点集相同但边集可以不同。先定义好有限词上的限制矩阵，进而可定义所有的可允许词或禁止词。第 n代图的结点集是所有 n长的可允许词。一旦定义好了Gn,我们则以如下方式递归生成(n+1)代图:将第n代图复制N分，并重新标记结点去掉所有的禁止词，再按照基图的边集规则将部分纯型1和部分纯型2的结点连接起来即生成(n+1)代图。我们证明了在两种假设下该类图的无标度性。并考虑了以增长边嵌入方式生成的分形集，证明了该嵌入集是sofic集并给出了Hausdorff维数的精确估计。我们还考虑了不同情况下Laplace算子谱隙序列的渐近性质。并在基图都是完全二分图的情况下，我们给出了 Laplace算子谱隙序列严格正的充分必要条件。
　　在第5章，我们将本文关于两类无标度网络上的所有结果做了一个总结，并给出后续可以继续研究的问题。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 分形几何概述

1.2 复杂网络概述

1.3 具有分形结构的无标度网络的研究背景及现状

2 预备知识

2.1 Hausdorff测度

2.2 Hausdorff维数

2.3 自相似集

2.4 有向图自相似集和递归集

2.5 Sofic系统和sofic集

2.6 无标度性和小世界性

2.7 随机游走, Cheeger常数和Laplace算子

3 一类模块化的分层无标度网络

3.1 引言

3.2 模块化的分层无标度网络的构造

3.3 无标度性和小世界性的证明

3.4 嵌入集定义及其Hausdorff维数

3.5 陷阱问题中的平均首达时间估计

3.6 一些例子

4 一类基于有限型子位移生成的无标度网络

4.1 引言

4.2 基于有限型子位移生成的无标度网络的构造

4.3 无标度性的证明

4.4 嵌入集定义及其Hausdorff维数

4.5 Laplace算子谱隙的估计

4.6 一些例子

5 结论

致谢

参考文献

附录1 攻读学位期间发表论文目录

附录2 攻读博士学位期间参与的科研项目