文摘

小世界网络无处不在在真实系统中,如万维网、通信网络、电力电网,其中大部分是随机的。在本文中,我们提出一个模型,生成一个在一个简单的确定性小世界网络模型的方法和分析相关的拓扑属性,如度分布、聚类系数、和直径。同时,根据模型的特殊结构,我们分析得出的确切数字平面网络生成树。结果表明,模型具有一个离散程度指数分布、聚类系数高,短直径和高熵。

1。介绍

在过去的十年中,很多作者在不同的科学社区齐心协力朝着揭幕的通用属性和理解复杂网络系统在自然和社会1- - - - - -5]。最重要的事情之一是网络建模。它的重要性在于,它不能只捕捉正确组装的流程我们今天所看到的网络,但也有助于知道各种微观过程如何影响网络拓扑结构(6]。目前,许多论文相关的复杂网络模型是随机的(7- - - - - -9]。但随机性,而符合现实网络的主要特性,使得它难以获得视觉是如何影响网络的理解和不同的节点之间的关系如何10]。因此,它将不仅重大理论的兴趣,也具有十分重要的现实意义构建模型,导致确定性小世界网络时尚。

第一个成功的尝试产生高的网络聚类系数和小的平均路径长度(APL)模型引入了瓦和strogat (WS模型)11]。瓦的开创性工作,“开始雪崩的研究对小世界网络的特性和Watts-Strogatz (WS)模型(12]。其一的变体:WS模型提出了纽曼和瓦(13,14]。1999年,Kasturirangan WS小世界网络提出了一个替代模式(15]。实际上,小世界网络的特点是三个主要属性。首先,他们的APL不增加线性与系统大小,但生长对数与节点的数量或慢。第二,网络的平均节点度很小。第三,网络有很强的平均聚类(11相比一个Erdos-Renyi (ER)随机网络(16,17平等的大小和节点平均度。

在本文中,我们提出一个确定的平面网络模型的生成算法。我们分析其拓扑性质;结果表明,我们的模型有一个离散程度指数分布,高聚类,和小直径,小世界效应。此外,众所周知,生成树的数量是一个重要的数量描述网络的可靠性。一般来说,网络中生成树的数目可以直接计算得到相应的网络相关的决定因素。然而,对于一个大型网络,评估有关行列式是棘手的18]。因此,我们提出一个通用的线性算法来计算生成树的数量一般平面网络。使用该算法,我们分析得出的确切数字平面网络生成树。基于生成树的数目,我们确定熵的生成树。

2。网络建设

研究网络以迭代的方式构建。我们表示网络 步骤 。然后,网络的步骤 建立如下。为 , 是一个完整的图4节点。为 , 是获得 通过替换现有迭代的边缘 与 。重复这个过程,直到达到所需的图表顺序;参见图1。


图1
在线(颜色)确定的平面网络的建设 ,显示迭代过程的三个步骤。固体链接是迭代链接;冲noniterated链接的链接。

现在,我们计算的顺序和大小 。让 , , 分别表示的顶点,边缘,边缘和迭代步骤 ,而 和 是图的顶点和边的集合 。注意,在每一次迭代,迭代的边缘被两个新的迭代边和三个noniterative边缘。因此, , 。在下一次迭代每个迭代边介绍两个新顶点和五个新的边缘, 和 。作为 , 和 。因此, 平均程度 显然,对于大 ,约等于5。

3所示。相关的确定性小世界网络的特征

在下面,我们专注于度分布、聚类系数、和直径。

3.1。度分布

程度是最简单和最集中研究了单个节点的特征。一个节点的程度 边的数量在整个网络连接 。度分布 被定义为一个随机选择的节点的概率到底是什么 边缘。

让 节点的程度 在步骤 。所有节点可以分为两类。(我)内部节点;仅供那些节点连接到noniterative边缘,他们总是等于3。(2)Noninterior节点;你会发现在任何迭代,迭代的优势被两个新的迭代边和三个新的noniterative边缘,所以noninterior度节点添加4在每一个迭代。因此,学位 一个节点的 满足的关系 。然后, 。我们有 让 一个节点的一步 创建,然后 noninterior节点,因此,我们有 因此,频谱程度的网络是一系列离散值:在步骤 程度,节点的数量 ,等于 ,分别。没有学位的其他值范围。由于这个度谱的离散性,方便获取其累积度分布(18];也就是说, 使用(5),我们有 。因此, 显然,当网络的规模大,程度分布 是一个指数的幂学位 。

3.2。聚类系数

一个网络的聚类系数是另一个重要的属性,它提供了一个网络内的局部结构的措施。最直接的衡量聚类的聚类系数 对于每一个节点 。根据定义,聚类系数 一个节点的 是总人数的比例 之间实际存在的边缘 最近的邻国和数量 他们之间所有可能的边缘;也就是说, 。聚类系数 整个网络的所有单个的平均值 年代。这个网络,我们可以获得准确的聚类系数的表达式 。通过建设,对于任何给定的节点 拥有一个学位 ,有 你的邻居节点之间实际上存在的链接。所以,你会发现有一个一对一的对应系数之间的关系 的节点及其程度 : 。这个表达式表明,当地集群规模 。

显然,度的节点的数量 ,等于 ,分别。聚类系数 是由以下几点: 为无限 , 方法定值为0.8309,所以集群高。

3.3。直径

除了度分布、聚类系数、平均路径长度(APL)是另一个重要的参数来描述一个网络。APL被定义为边的平均数量在所有可能对网络节点的最短路径。人们找到了小世界现象在大多数实际网络与短APL的行为。对于大多数网络模型,很难获得APL的解析解。证明任何一对节点之间的距离,我们可以采用另一个参数被定义为最大通信网络中延迟。如果网络有一个直径小,那么这个网络无疑是一个简短的APL (19]。对于网络提出了,我们表示迭代的直径 作为 。根据图1,我们可以清楚地知道这一点 和 。在每个迭代中,人们总是可以看到直径是一双新创建的节点之间在这个迭代,因为在每个迭代的边缘我们粘贴一个完整的图形 的直径,因此网络提出有以下简单的公式, 。

注意,对数的节点总数的价值 约等于 对于大型 。因此,直径生长对数与节点的数量和平均路径长度增加更缓慢 。

基于上面的讨论,我们的模型是一个确定性小世界网络,因为它是一个稀疏集群和高短直径,这对小世界网络满足必要的财产。

4所示。网络中生成树

在本节中,我们在这个网络生成树的数量进行调查。我们的目标是获得准确的公式生成树的数目并确定其熵。

让 是一个平面图形生成的 步骤。自 是对称的,假设边缘 , , 加权的 ,在那里 表示数量的子图的生成树 和 表示生成子图的森林的数量 等两个组件 和 属于不同的组件。让 生成树的数目 。图3给所有生成树 和图4给所有与两个组件生成森林。然后,通过图2,我们有


图2
在线(颜色)网络 。实迭代链接,链接冲noniterated链接的链接。

图3
生成树的数目 是 。坚实的联系表明,一个节点连接到另一个节点;冲链接显示没有连接到另一个节点一个节点。

图4
生成森林的两个组件的数量 是8。坚实的联系表明,一个节点连接到另一个节点;冲链接显示没有连接到另一个节点一个节点。

数据显示2,3,4,我们获得的递归关系 和 如下: 让 ,(10), 与初始条件 。因此,我们得到 由(9), 用(11)和(12)和(13),我们有 从(14(一起),1),我们确定的数量的熵跨越trees-an重要数量描述网络结构 作为限制值(20.,21]:

得到熵的生成树 相比可以发现在其他网络。在pseudofractal分形网络(22),熵是0.8959,一个值小于1,平方晶格(23谢尔宾斯基三角形(译者注:)和二维(24),生成树的熵是1.16624和1.0486,分别和分形无标度格(25),熵是1.0397。它们有相同的平均4度。在阿波罗网络(26]6的平均程度,熵是1.3540,我们的模型的熵与它们之间平均5度。

5。结论

在结论中,我们研究了一个简单的模型,这是构建在一个确定的方式。然后,我们提出了一个详尽的分析,认为模型的许多特性,得到了解析解的拓扑特性,包括度分布、聚类系数、和直径。最后,根据特殊结构,我们给出一个通用算法计算该模型的生成树的数目。使用该算法,我们得到熵的生成树。

利益冲突

作者宣称没有利益冲突有关的出版。

确认

这项研究由美国国家科学基金会支持的中国(61164005和61164005号),中国国家基础研究项目(没有。2010 cb334708),计划在大学长江学者和创新研究团队(没有。IRT1068)。