文摘

复杂网络看到了太多的所有研究领域的兴趣,发现很多潜在的应用在不同的领域包括自然、社会、生物和工程技术。确定性模型的复杂网络领域的网络模型中扮演不可或缺的角色。确定性的方式构建网络模型不仅具有重要的理论意义,还具有潜在的应用价值。在本文中,我们提出一种3处标准与小世界网络模型的现象。我们确定它的有关拓扑特征,如直径和聚类系数。我们也给出一个计算方法3处标准网络的生成树数量和获得的数量和熵生成树,分别。

1。介绍

近年来,复杂网络的研究方兴未艾。利用复杂网络图论和一些统计物理的方法可以用来捕获和描述系统的演化机制,发展模式,整体行为,是蓬勃发展的主要原因之一,在复杂网络研究1]。

小世界网络,建设符合真实系统特性不仅具有重要的理论意义,而且在确定的方法(也有潜在的应用价值2]。在本文中,我们目前的第三小世界网络。我们确定相关的普通网络的拓扑特性,如直径和聚类系数。结果表明,我们的模型有一个离散程度指数分布,高聚类,和小直径,出现在小世界效应。众所周知,生成树的数量是一个重要的数量描述网络的可靠性。由于不同的应用在许多领域,大量的努力一直致力于研究生成树。例如,在[3,4]作者给了准确的生成树数量规律的晶格。生成树的数量在一个网络可以直接计算得到相应的网络相关的决定因素。我们也给一个方法来计算3处标准网络的生成树的数量和推导公式。基于生成树的数量我们确定熵的生成树。

2。网络建设

的程度 的一个顶点 在 的边的数量吗 事件和 ,每个循环计数两条边(5]。一个图表 是 常规的如果 对所有 。在本节中,我们描述一个日益增长的网络模型,构建以迭代的方式。我们表示我们的网络 步骤 。然后以以下方式构造网络。为 , 是一个图,两个节点连接三条边。为 , 是获得 通过添加两个新节点的一步 ;然后两个边缘增加;复制它,连接四个新节点。重复这个过程,直到达到所需的图表顺序;参见图1。


图1
确定的3处标准网络的建设 ,显示迭代过程的三个步骤。

现在我们计算的大小和顺序 。表示由 网络中节点的总数 网络中边的总数。很容易得到 自 和 ,接下去 注意四个新节点的加入会导致两个新的边缘。然后 作为 ,我们有

3所示。相关的特征

由于确定性,上面描述的相关特点,我们的模型可以完全解决。在下面,我们专注于直径和聚类系数。

3.1。直径

小世界网络描述许多真实网络;之间,有一个相对较短的距离最双节点最真实的网络和他们的平均路径长度(APL)不增加线性与系统大小但生长对数与节点的数量或慢。平均路径长度是最小的连接两个节点的链接数,平均超过所有成对的节点(2]。最长的所有成对的节点之间的最短路径叫做直径,这是最重要的评价指标之一,因为它描述了网络中的最大通信延迟(6]。对于大多数网络模型,很难获得的平均路径长度的解析解。因此我们将研究直径而不是平均路径长度。我们在迭代表示直径 作为 ;然后根据图1,我们可以清楚地知道这一点 和 。在每一次迭代 ,人们总是可以看到直径是一双新创建的节点之间在这个迭代。因此网络提出的直径有以下公式:

所以,直径 生长对数与节点的数量。因为平均路径长度小于直径,APL应该增加更慢。所以我们的模型满足小世界网络的特性。

3.2。聚类系数

集群的另一个重要属性是一个复杂的网络,它提供了一个衡量网络内的局部结构(2]。聚类系数表明一个节点与其邻居节点之间的连接关系。根据定义,聚类系数 一个节点的 与学位 是总人数的比例 现有的边缘之间的所有 最近的邻居和数量 他们之间所有可能的边缘;也就是说, 。聚类系数 整个网络的所有单个的平均值 ;也就是说, ,在那里 是网络的节点的数量。所以我们的网络的聚类系数有以下简单的公式。我们知道 在步骤 。在每一次迭代 ,我们有 很明显, 当 ;因此集群也高,满足小世界网络的属性。

基于上述讨论,我们可以得出结论,我们的模型是一个确定性小世界网络,因为它是稀疏的小直径和平均路径长度,聚类系数高。

4所示。枚举生成树

生成树的任何连接网络定义为一个最小集合的边缘连接每个节点。的生成树枚举网络是数学中的一个基本问题7- - - - - -9)、物理(3,10),和其他学科11]。生成树的问题是有关网络的各个方面,如可靠性(12,13),最优同步(14),和随机漫步15]。在下面我们将检查3处标准网络生成树的数目。

为了准确计算生成树的数目,起初我们建立一个新的模型 如图2。我们之间的关系 和 在图3。生成树的数目和生成森林等两个组件 和 属于不同的组件 所表示的 和 ,分别。然后生成树的数目的原始模型 可以从生成树的数目 。然后我们有以下关系:


图2
确定的3处标准网络的建设 ,显示迭代过程的三个步骤。

图3
网络模型 和 在步骤 。

我们计算生成树的数目 在下面。很容易获得的关系 和 从(7)。从图4,一个可以看到的生成树的形状 包括两种情况。


图4
生成树的数目 。

生成森林的形状与两个组件等 和 属于不同的组件 有5例;参见图5。


图5
生成森林的两个组件的数量 。

通过考虑对称的,不难的递归关系生成树和生成森林的数量 和 在数据4和5: 与初始条件 和 。通过计算,它遵循 让 ;然后 与 。所以 。

注意到 ,(8),我们知道

请注意, 节点的数量吗 。从(10我们确定熵的生成树 (7,16)如下: 从(10)和(11(一起),7),生成树的数目 是由 与初始条件 。

因此,熵的生成树 是由

我们可以比较的生成树的熵 与其他网络(17,18]。生成树的熵在科赫网络平均度3是0.5493 [17),而我们模型的生成树的熵是0.6931。

5。结论

在本文中,我们提出了一种确定的普通小世界模型以迭代的方式,提供了一个详尽的分析,认为模型的许多特性。然后我们获得了解析解的拓扑特性,包括直径和聚类系数。我们还确定生成树的数目在3处标准小世界网络。此外,使用该算法,我们获得了熵的生成树。

利益冲突

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

确认

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