文摘

生成树在数学的许多方面被广泛研究:理论计算机科学,组合,等等。一个重要的问题是计算这些生成树的数目。这个数字仍然是一个挑战,尤其是对于大型和复杂的网络。作为一个复杂网络模型,我们研究两个家庭的广义小世界网络,即小世界指数和科赫网络,通过改变循环子图的大小和尺寸。我们介绍他们的建筑和结构属性,以迭代的方式构建。我们提出一种分解方法计算生成树的数目,我们获得准确的公式,然后通过数值模拟验证。从这个数字,我们发现他们的生成树熵,低于其他网络拥有相同的平均程度。这个熵允许量化网络的健壮性和描述他们的结构。

1。介绍

最近,复杂网络的分析受到刺激引起的巨大的网络数据资源和现实世界中的许多系统可以被描述和复杂网络的特征1]。一些科学研究,激发了研究者构建网络模型来解释现实生活中的系统中存在的共同特征。知名的复杂网络模型中,有一个小世界网络。它显示丰富的行为观察到在一个大的各种实际系统包括互联网(网站导航菜单)、电力电网、大脑神经元网络,电话图表,和社交网络。它的特点是具体的结构特点:大聚类系数和小的平均距离。分析这类复杂网络,需要理论来解释他们的固有的和紧急的属性。新的正式的这些网络模型需要准确预测他们的性能,维护可靠性的保证,并量化其鲁棒性。图论的一个强大的工具来简化这个理论研究,列举生成树一个网络的(2]。后者被定义为连接和单极子图所有顶点(节点)和一些或所有的边缘。本文的目的是要知道有多少生成树可以有网络。这些生成树枚举的往往是最重要的一个参数特征的网络可靠性3]。我们表示生成树的数量 ,也被称为网络的复杂性。一般来说,可以通过计算行列式或拉普拉斯算子矩阵的特征值对应于网络(4]。然而,这种一般方法是不可接受的对于大型的复杂网络,由于其计算时间复杂度高。因此,有趣的是开发技术和方法来促进生成树的数目的计算和找到自己的准确公式的特殊类网络。在这种背景下,我们的工作提出了一种组合方法确定生成树数量对于一些复杂网络,即分解方法(5]。它依赖的原则“分而治之”的过程除以一个问题在子问题,求解这些子问题,然后将通解的部分结果。

作为应用程序的数量生成树的网络,我们使用生成树的熵或所谓的渐近的复杂性(见,例如,德,Emmert-Streib, Chen Li和施2,6])。通过计算这个熵,我们可以估计网络将如何演变到正无穷。该参数允许我们量化复杂网络的鲁棒性和描述他们的结构7]。它与网络的能力抵抗结构的随机变化。许多研究人员已经使用这种方法来估计一些复杂网络的鲁棒性和异质性的结构,如小世界法里图(8),两棵树网络(9),平面未聚集的网络(10),棱镜和antiprism图(11),格(12]。

我们工作的新颖性是分析调查两个广义的家庭小世界网络,小世界指数网络。见,例如,Mokhlissi、Lotfi Debnath和El Marraki [13Dolgushev]和刘,气和张14],科赫公司网络。见,例如,张周,谢,陈、林和关15)、张、高、陈、周、张,关16]。第一个网络是基于完整的图形和第二网络是基于经典分形科赫曲线(17],它有许多重要的性质在实际网络。概括这两种网络中,我们添加了两个重要的参数与循环子图的大小和循环子图的尺寸(循环子图添加的数量)。我们建议两个迭代算法生成的结构,我们决定他们的拓扑性质,计算复杂性。最后,我们评估和比较他们的生成树与其他网络熵河内网络平均度一样,花网络,蜂巢晶格。结果,我们得出这样的结论:广义指数小世界网络和广义科赫网络生成树熵相同,所以同样的健壮性尽管他们的结构和性质完全不同,这熵的大小只取决于循环子图中,这意味着第一个迭代清晰度节点度的增加根据循环子图的尺寸;它不影响跨越三通熵。本研究的范围是,这两个小世界网络的泛化并不影响小世界网络的概念(大集群系数和小的平均距离)。的工作提出了另一种观点在小世界网络的分析,表现出实际系统的典型特征。

本文的组织结构如下的轮廓。节2,我们现在预赛和使用方法。建设、属性和广义指数小世界网络的复杂性和广义科赫网络提供了部分3和4。然后,这些小世界网络的生成树熵提出了部分5。最后,结论部分中包含6。

2。预赛

在本节中,我们介绍一些符号和方法用于促进计算复杂网络的复杂性。让 是一个连接的平面图其数量的顶点,被它的边数,其数量的面孔;它没有循环,没有平行边。一个图的顶点数是指其秩序和边数指的是它的大小。图和朦胧地使用网络。网络是一个小世界网络,如果距离两个随机节点之间的对数增长比例网络中节点的数量,也就是说, ,而聚类系数(衡量网络中节点的程度倾向于聚集在一起)并不小。

欧拉公式(22]:欧拉公式是一个拓扑不变量特征的拓扑属性相关数量的顶点,边和面孔。

定理1。让是一个连接的平面图顶点,边,的脸。这些数字是由著名的欧拉关系连接;然后

选择适当的方法计算生成树数量在一个给定的网络是一个关键因素。对于这个工作,我们提出了一种分解方法生成树容易计算的数量。这种方法依赖于分而治之的原则;我们将图像分解成不同的子图显示某些约束:遵循一个节点,两个节点,边缘和路径。在这项工作中,我们研究的子图的一个顶点相连(见图1)。应用此方法,我们按照这个算法:(1)我们将原始图像分解成不同的子图,连接到一个顶点。(2)我们计算的数量为每个子图的生成树。(3)我们收集的结果获得原始图像的复杂性。

让是一个平面图形由链 (见图1)。生成树的数目由以下公式给出:

如果一个网络的复杂性随给定顶点数的增加呈指数增长 ,那么存在一个常数 ,称为生成树的熵或渐近的复杂性23》,由这个关系描述:

生成树的熵的一个网络是一种定量测量的数量生成树来评估网络的健壮性和描述它的结构。最健壮的网络与较强的异构拓扑网络生成树最高熵。根据熵的定义生成树的一个网络,熵值越大,生成树的数目越多,所以有更多的可能性两个节点之间的连接与缺陷相关的链接,以确保良好的可靠性和鲁棒性。

3所示。一个广义指数小世界网络

在本节中,我们介绍一个著名的家庭小世界网络:网络小世界指数(24]。它有一个程度的指数形式分布和相同数量的节点和边的双重Sierpinski垫圈(25]。已经观察到一些现实生活中的系统的张量网络、社会网络、量子行走。我们提出一个广义指数小世界网络,区别依靠循环子图的大小和循环子图的尺寸(循环子图添加的数量)。我们也调查其建筑和结构特性和计算复杂性。

3.1。建设和广义指数小世界网络的特性

用广义指数小世界网络有两个控制参数:循环子图的大小和吗循环子图的尺寸,即。,循环子图的数量补充道。的建设遵循这个算法: ,我们有一个简单的节点。在第一代,是一个循环图的尺寸吗 。为 上一次迭代的网络中,每个节点所取代新循环子图的大小 。因此,每个新出现的循环子图包含一个节点的网络之前的迭代和清晰度节点度的第一次迭代 (在图2,清晰度节点颜色的红色)。相同的过程用于另一个迭代。在图2的前四个迭代广义指数小世界网络进行了说明。

让我们计算顺序,大小,数量的面孔,平均学历,广义的直径小世界指数网络 。让创建节点的数量 。从图2我们注意到,从1到 : 。然后,我们乘的方程通过 ,的方程通过 ,等等,直到最后一个方程将乘 。总结所有获得的方程: 我们发现以下结果: 与 。因此,的节点的数量 是

让在迭代创建链接的数量 。通过建设,从1到 ,我们有 然后,我们乘的方程通过 ,的方程通过 ,等等,直到最后一个方程将乘 。总结所有获得的方程: 我们发现 与 。因此,链接的数量 是

让在一代面临创建的数量 。我们应用定理1;我们获得的面孔 是

的平均程度 是(约3大)

直径最大的任意两个节点之间最短的距离 网络: 。让的直径在一代 。这个直径可以计算两种情况:(我)如果循环子图的大小对,我们可以计算出直径如下:在迭代 ,直径 。为 的直径增加了最多。(2)如果循环子图的大小很奇怪,我们可以计算直径如下:在迭代 ,直径 。为 的直径增加了 最多。

所以的直径 是

这个直径可以由另一个公式生长对数与顶点的网络显示的数量是一个小世界网络。

3.2。生成树的数目的广义指数小世界网络

生成树枚举是一个基本的问题在许多网络分析中遇到的问题。然而,显式地确定这个有趣的数量在网络是一个专门为复杂网络理论挑战。幸运的是,广义指数小世界网络的建设可以得到这个数字的精确公式使用分解方法。

定理2。让表示广义指数小世界网络。的复杂性由以下公式给出:

证明。从图2,我们看到,包含几个循环子图 。使用(2我们获得 ,在那里循环子图的数量吗 。为了计算生成树的数目 ,我们需要找到首先循环子图的数量 。从我们的网络从1到 ,我们看到 。然后,我们乘的方程通过 ,的方程通过 ,等等,直到最后一个方程将乘 。总结所有获得的方程: 我们发现的周期数 : 。我们在方程代替它 ;因此,我们获得 。
为 和 ,网络是小世界网络指数。生成树的数目是由以下公式给出26]:

4所示。一个广义科赫网络

在本节中,另一类称为小世界网络科赫公司网络 进行了研究分析。这个网络派生类的科赫曲线。他们是分形的一个有趣的家庭。我们使用它们来理解几何分形在真实的系统。科赫网络包含一些属性描述的大多数实际网络系统:高聚类系数和一个小的直径,表明科赫网络是一个小世界网络。我们提出了一个广义科赫家族网络 ,的差异依赖于循环子图的大小和数量的循环子图添加到每个节点根据两个参数变化和 。我们提出分析一个算法的广义科赫公司网络的建设,我们确定它的性质和计算它的复杂性。

4.1。建设和广义科赫网络的属性

科赫公司网络的启发算法,我们提出一个广义科赫家族网络有两个整数参数(循环子图的大小)(循环子图的尺寸)。其建设的算法如下:最初( ),是一个循环图的尺寸吗 。为 ,是获得通过添加新循环子图的大小为每个节点的每个现有的循环子图 。的增长过程的广义科赫网络下一代继续以同样的方式。清晰度节点度的第一次迭代 (在图3,清晰度节点由绿颜色)。图3说明了网络的成长过程的前三代 。

在本节中,精确表达式的属性广义科赫网络给出了。然后明确结果的节点数量,数量的边缘,许多面孔,平均学历,和直径。

广义科赫网络的结构属性介绍如下:节点的数量吗计算如下。从图3我们注意到,从1到 : 。然后,我们乘的方程通过 的方程通过 ,等等,直到最后一个方程将乘 。总结所有获得的方程: 我们发现 与 。所以的节点的数量 是

边的数量计算如下:从图吗3我们注意到,从1到 : (一个几何套件)。所以边的数量 是

的面孔计算如下:从图吗3我们注意到,从1到 : 。然后,方程乘以 的方程通过 ,等等,直到最后一个方程这是乘以 。总结所有获得的方程: 我们发现 与 。所以的面孔 是

我们可以获得的面孔也通过使用定理1。

的平均程度 是(约3大)

让的直径在一代 。这个直径可以由下面的公式 :

我们可以现在它被另一个公式生长对数与顶点的网络显示的数量是一个小世界网络。

4.2。广义科赫网络的生成树的数目

为了计算广义科赫网络的生成树的数目 ,我们使用相同的方法作为其他网络研究:分解方法。

定理3。让科赫表示广义网络。的复杂性由以下公式给出:

证明。从图3,我们看到,包含几个循环子图 。使用(2) 与数量的循环子图 。从图3,我们看到了从1到 : (一个几何套件)。所以循环子图的数量是 。替换这个方程的结果与 ,因此我们获得 。为 和 ,网络科赫公司网络。生成树的数目是由以下公式给出16]:

5。生成树的广义熵指数网络和广义科赫网络小世界

广义小世界网络的生成树数目呈指数级增长,所以我们可以计算生成树熵根据熵的定义部分2。让生成树的熵的广义指数网络和小世界的熵为广义科赫网络生成树。

推论4。生成树的广义熵小世界指数网络是 生成树的广义熵科赫网络是

从结果中,我们发现广义指数小世界网络和广义科赫网络具有相同的熵即使他们的复杂性是不同的。熵的大小只取决于循环子图而不是循环子图的尺寸 。这意味着广义指数小世界网络和广义科赫网络鲁棒性尽管相同结构和性能是不同的。注意,第一个迭代的清晰度节点的程度增加的价值 ,和它不影响生成树熵和,因此,并不影响这两个小世界网络的鲁棒性。

图4表明,增加循环子图的大小导致熵减少的生成树和 。这个结果证明了这些网络的低价值更强大的比有高的价值 。

从表1,我们比较小世界的生成树熵指数网络和科赫网络(0.549)与其他网络拥有相同的平均学历3。我们注意到他们的价值生成树熵最小的出名的是网络平均度3。这反映了一个事实,科赫公司网络和小世界网络更健壮和拓扑指数不如其他异构网络拥有相同的平均程度。

6。结论

在本文中,我们研究的问题有效地计算生成树的数量在两个著名的小世界网络:广义指数小世界网络和广义科赫网络。我们已经检查了他们的建筑和详细分析他们的拓扑属性决定的。我们已获得精确解的生成树使用分解方法。我们有进一步计算和比较他们的熵的生成树。结果表明,这两种广义熵小世界网络具有相同的生成树的虽然他们没有相同的复杂性。作为一个未来的工作,我们打算分析另一种类型的复杂网络和使用新的组合方法,可以方便的计算生成树的数目。

数据可用性

这项工作不需要数据得到结果;我们开发了这个科学研究用数学计算。

的利益冲突

作者宣称没有利益冲突。