论文部分内容阅读
以发现小世界网络和Internet、WWW以及蛋白质相互作用网络的无标度性质为起点,复杂网络研究发展迅速,已经成为复杂性研究的主要对象和重要方法。近十年来,学术界从理论上提出了一系列新的概念和分析方法,来研究复杂网络的结构、功能和演化,为深入认识实际复杂系统的性质提供了基础。本论文分为上中下三篇,从复杂网络的空间结构、社团结构和渗流理论三个方面,通过理论分析与数值模拟等方法,研究了复杂网络的若干重要问题,为深入理解复杂网络的结构与功能提供了启示。本研究分为三个部分:
㈠复杂网络的空间结构研究主要围绕着顶点之间的空间距离与网络结构和功能之间的关系展开。对于大量现实世界中的复杂网络,如朋友关系网络、Internet等等,每个顶点(个体)都有其自身的空间位置,顶点既可以和与它在空间位置邻近的顶点发生作用,也可以通过长程连接与离它很远的顶点发生作用,综合研究复杂网络的空间结构和拓扑结构对系统功能的影响具有重要意义首先关注了社会网络空间距离分布的标度性质。大量的社会网络空间性质的实证研究发现,在社会网络中,朋友之间的距离r服从P(r)∝r-1这样一个幂律分布,我们首次给出了这种空间结构形成的可能原因,指出社会网络空间距离的标度性质是信息熵极大化的结果。在假设个人保持朋友关系所付出的代价与朋友之间的距离正相关的限制条件下,我们发现社会网络中这种幂律分布恰好使得个人的朋友关系的多样性最大,而这一多样性可以通过信息熵来描述。同时在P(r)∝r-1这种空间幂律分布下,我们发现,不论人口分布是否均匀或者是分形结构的,社会关系网络具有小世界可导航性,也就是所谓的世界是“六度分离”的,导航时间复杂度为网络规模对数的2次方。进一步的研究表明,利用信息熵描述多样性,具有很强的普适性,可以让我们对于社会网络的空间结构、动物的Levy行走以及人类空间移动的距离分布有一个统一的理解。在一定的成本约束下构造长程连接是许多实际空间网络的共同特点。在网络上所有顶点长程连边的空间距离之和与网络规模成正比的情况下,本文分别研究了网络的导航能力、平均最短路径、最大交通流量以及疾病传染等特征。我们严格证明了在这种连边代价约束条件下,导航的时间复杂度与网络的规模线性相关,当P(r)∝r-2时时间复杂度最低,同时在P(r)∝ r-2的分布下,网络的平均最短路径长度最短,这与实际的美国航空网络存在连边的顶点间的距离分布基本一致,结论极具现实意义。另外,由于社会网络空间幂律分布与人类和动物的移动行为密切相关,我们还研究了疾病在这种网络上传播行为,并发现,在P(r)∝r-2时疾病传播的速度最快,传播的阈值相对较低并会出现类似相变的行为。
㈡许多实际网络中存在着社团结构,并与系统的功能模块密切相关。探查复杂网络中的社团结构,能更清晰深入地认识网络结构并简化对应的功能分析。本文在复杂网络社团结构分析中,主要从社团结构的显著性和社团探查算法两个方面展开研究。网络中是否存在着清晰的社团结构是显著性研究需要回答的核心问题。由于社团结构的显著性与社团结构的鲁棒性密切相关,我们首先基于网络社团结构抗扰动能力,建立了度量网络社团结构的显著性指标。一般而言,对于许多实际的复杂网络,都不可避免的存在错误的连接,而且大部分探查社团结构的算法也存在着随机性。网络社团结构的显著性实际上等价于网络社团结构的抗扰动能力。从这个角度出发,我们通过整和网络社团结构在不同强度扰动下的变化量,并综合考虑零模型的结果,给出与网络规模无关的社团结构显著性度量指标R。实际上,当一个网络用邻接矩阵来表示时,这个矩阵就包含了网络的全部性质。我们进一步利用矩阵特征向量的摄动理论,通过分析网络的Laplaucian矩阵的最大的几个特征值对应的特征向量拓展成的空间的稳定性,从理论上我们给出了在不需要预先知道具体社团结构的情况下,刻画社团结构的显著性指标H,特别值得指出的是,H指标可以被网络的顶点数量与平均度很好地标准化,可从而以用于不同规模网络社团结构显著性的相互比较。通过17个经典网络的比较,我们发现大部分社会网络具有明显的社团结构,除神经网络外,大部分生化反应网络、蛋白质相互作用网络社团结构的显著性相对较低。在社团探查算法方面,我们严格分析了被大家广泛接收的最大化Q函数问题,证明它等价于一个凹二次规划问题,并在此基础上设计了最大化Q函数的改进算法。基于网络的局部结构,我们通过比较顶点在社团中和其他任一个社团的连边数量之间的关系,给出了社团结构的新的比较性定义。并设计了基于此定义的高速演化算法,在不需要任何的外部变量的情况下,比如社团的数目等,可以对大规模网络进行有效的社团探查。同时我们还提出了基于信号传播的社团结构探查算法。在信号传播过程中,网络中的顶点首先是影响其所在的社团,然后通过其所在的社团去影响整个网络,这样,同一个社团中的顶点对于整个网络的影响是相似的。经过信号的累积与发放过程,每个顶点对整个网络影响可以用一个向量来表示,这样网络上社团的划分问题便转化成在高维空间中对向量的分类问题。利用成熟的F统计量与K-means clustering方法,就能把网络中的顶点成功地划分为社团。
㈢复杂网络上的渗流理论研究与网络鲁棒性、疾病和谣言的传播密切相关,有着极其重要的理论和应用价值,长期以来备受学术界关注。现实世界中许多网络之间都存在着相互依赖关系,研究多个网络顶点相互依赖的渗流理论也成为复杂网络研究的重要方面。本文深入研究了在单个或多个网络顶点间同时存在连接关系和依赖关系的情况下网络上的渗流行为。在很多实际的耦合网络系统中,如各种交通网络、输送天然气与石油的管道网络之间不仅存在着依赖关系而且还存在连接关系。已有关于耦合网络上渗流行为的研究,只分别关注过网络之间的顶点只存在依赖关系或者只存在连接的情况下网络上的渗流行为。本文中我们通过理论分析和数值模拟,深入研究了顶点间具有混合交互关系的耦合网络系统,发现其渗流过程具有丰富的相变行为,甚至很多违反我们的直觉。例如,当我们增加网络之间的连接强度时,可以使整个系统从一级相变变化到二级相变,有时候也可以从二级相变变化到一级相变。当一个网络中的顶点大量依赖另外一个网络中的顶点时,整个系统会出现很不常见的混合相变。所谓混合相变是指在逐渐增加攻击强度时,网络的最大连通集团的规模会突然从一个较大的值跳到一个较小的值上去,如同一级相变,然后再连续变化到0,如同二级相变。另外,我们还发现当耦合网络参数发生变化时,系统会突然从二级相变变到一级相变,也就是在二级相变与一级相变的部分分界线上临界点附近是不连续的。这些现象的发现和理解丰富了我们对复杂系统相变行为的认识。