© 2013由Elsevier B.V.发布。信息工程研究院负责评选和同行评议可在www.sciencedirect.comwww.sciencedirect.com上在线获取ScienceDirectIERI Procedia 4（2013）53 - 582013年电子工程与计算机科学度相关混合模式的网络模型方法魏高新，范进 *东华大学自动化系，上海（201620）摘要许多社会、生物或技术系统都被认为是具有混合模式的复杂网络，而典型的理论网络模型如Watts-Strogatz小世界模型和Barabási-Albert无标度网络都缺乏这种混合模式。在本文中，我们提出了一个机制，模拟复杂网络的度相关性的出现。数值模拟表明，这种相关性可调的网络模型可以表现出根本不同的程度的相关性混合模式与无标度度序列。此外，还研究了网络的结构特性，如平均路径长度和聚类特性。© 2013作者。由Elsevier B. V.在CC BY-NC-ND许可下开放获取。信息工程研究院负责评选和同行评议关键词：度关联;复杂网络;关联性;幂律1. 介绍复杂网络是真实复杂系统的抽象表示，其中节点代表典型的系统单元，连接是单元对之间的相互作用[1，2]。复杂网络的研究已经引起了社会学、生物学、经济学和技术等领域的广泛兴趣[1]。基于对网络系统的实证研究，发现了两个显著的特征：描述网络平均路径长度的小世界特性[3]，* 通讯作者。联系电话：+86-0216-779-2312。电子邮箱：jinfan@dhu.edu.cn。2212-6678 © 2013作者由Elsevier B. V.在CC BY-NC-ND许可下开放获取。信息工程研究所负责的选择和同行评审doi：10.1016/j.ieri.2013.11.00954魏高新，樊锦/IERI Procedia 4（2013）53网络大小，以及无标度分布[4]，这意味着网络中节点的概率，k个连接遵循幂律行为P（k）~ k得双曲余切值.是度指数。除了上述两种典型的网络性质外，研究人员还发现，在这样的复杂网络中，存在着几种不同的节点类型，节点之间的连接往往与节点的类型有关。这些节点被选择性地链接到相同种类的节点，例如，在许多社交网络中，人们倾向于优先与在某些方面与自己相似的人联系，这被称为选择性混合[5，6]。另一方面，在某些信息网络或技术网络中，动态节点表现出与不同节点连接的趋势，这被定义为离散混合[6]。相关无标度复杂网络中的动力学过程，如流行病传播，已经得到了广泛的研究[7Pearson系数r被广泛接受为衡量独立程度的指标[5]：M M MM·K·I·J·IR吉吉（一）其中k i 和 J I 分别是连接i的端点的度数，M是连接i的端点的数量。网络中的连接。正的r值表示互斥混合，这意味着具有相似度的两个节点倾向于连接在一起;而负值表示互斥网络，其中不同的节点倾向于连接在一起。如果r接近于零，这意味着网络似乎是不相关的。有趣的是，观察到基本上所有的社交网络似乎都是独立的，但其他网络，如信息网络，技术网络或生物网络，似乎是独立的[6]。然而，典型的理论网络模型，如Barabási-Albert无标度网络，并没有揭示这种程度的相关性。因此，构建具有指定度-度关联模式的复杂网络是研究和理解关联性如何影响复杂系统动力学的第一个重要步骤。在这方面，Newman[5]提出了一种基于生成函数和Monte Carlo算法的正相关网络模型。另一种在BA网络中重新布线边以改变相关参数的算法也被提出[11]。问题是，当网络规模较大时，该算法的时间复杂度为~O（M2），计算量巨大。本文提出了一种新的网络模型算法来生成度相关系数可调的复杂网络，该网络的度相关系数既可以是正的，也可以是负的。基于网络节点的无标度度序列，生成了具有不同节点度幂律指数的混合模式，并研究了相应的网络结构性质.我们发现，具有极端离散混合模式的模型容易生成孤立子图。网络的平均路径长度随着度相关性的变化而单调减小。此外，新的相关性可调网络模型的聚类系数很好地描述了大多数现实世界的网络的聚类特性。本文的组织结构如下。在第二部分中，提出了相关可调模型的生成算法。在第三节中，我们构建了具有不同无标度度分布的新型网络模型，并对它们进行了比较。第四节研究了平均路径长度和团簇系数。最后，第五部分对全文进行了总结。i1i 1i 1MM2MM2MK2我K我MJ2我J我I1I1I1I1魏高新，樊锦/IERI Procedia 4（2013）5355吉吉吉吉我2. 相关可调网络建模相关性可调网络模型如下生成。首先，根据生成函数[12]，我们构建具有任意分布D的度序列{d1，d2，...，DN}，可以是幂律或任何随机分布。为了简单起见，节点的索引被排序，使得度有一个降序，即， D1d2...d N，并且d i被赋予第i个节点作为其度。第二、从第一个节点开始，当每个节点连接到另一个节点时，概率为“最大”（即，具有最大度）节点是（0个1），到“最小”（具有最小度）节点是1-，直到该节点的度值被全部考虑。请注意，在这里，我们认为网络模型是无向的，没有自环，节点对或自环之间的多个连接是不允许的。最后，重复上述第二步过程，直到所有N个节点完成连接。我们得到了一个具有指定度分布的相关性可调网络，通过改变度分布的值来确定网络的相关性。根据等式（1），r的值取决于当节点的度在净工作量是固定的。根据排序原理[13]，两个向量的结果 有序环的乘积大于负序环的乘积，而随机环的因此，我们认为，越大，折射系数r值越大。所以当它很大时，我们将得到一个网络模型具有正的非线性混合;相反，当接近0时，r趋于负值，我们可以 得到一个离散的混合模式。应该注意的是，我们从“最大”节点（d1是度序列中的最大值）开始0的情况。我们我们将在第4节中解释这种特殊情况。3. 仿真结果我们从生成函数[12]中生成幂律分布的网络度作为其指数变化。为了比较异构网络和同构网络，我们选取了分别为3和5。在所有数值计算中，相关系数r是通过平均100组模型获得的。对于不同的网络规模N，我们有不同幂律度序列的网络模型的相关系数r，如图1所示。r随参数的增加呈单调增加的趋势。当网络度序列是非均匀分布时（3），相关系数r的最小值在0时开始在-0.3到-0.4左右（随网络大小N的不同而变化）（如图1-a所随着r在0.05处迅速上升到零当r = 0.05时，r收敛到0.6~0.7。 对于同构网络5，我们得到了与图1-b相似的曲线，当r = 0 0.1时，r从-0. 6 ~-0. 7迅速增大到0.37 ~ 0.65。当r为0.1时，r缓慢上升到接近1。从图1中我们可以看出，对于不同的网络规模N，r的上升趋势表现出良好的一致性。值得注意的是，对于度分布遵循幂律分布的网络，当r等于0时，的值远小于0.5。这主要是因为在幂律分布中，大多数节点的度都很小，只有极少数节点的度很大。当一条链路连接两个节点时，所选节点都具有很高的概率都是小度的，这意味着所连接的节点具有相似的节点属性。只有当节点56魏高新，樊锦/IERI Procedia 4（2013）5310.80.60.40.20-0.2-0.4-0.6-0.80.80.60.40.20-0.2-0.4-0.6-0.8N=600N=800N=1000N=1200N=1400N=1600N=1800N=2000−10 0.2 0.4 0.6 0.81−10 0.2 0.4 0.6 0.8 1图1-a：3图1-b：5图1.具有不同幂律度分布的相关调整网络模型的度相关系数r。(a)异构网络3 ;（b）同构网络5。根据不同的性质（0），我们可以得到具有不同混合模式的网络。对于固定的网络规模N=1000，具有不同幂律系数的网络的r在图2中可视化。当增加到一个小的值（0.5）时，曲线急剧增加。0.5时，增量趋势趋缓。特别是，对于极端异质的网络（2.1），我们甚至不能获得非对称混合。表1总结了不同无标度网络中r的范围。我们发现，r的变化范围随着减小而减小。10.80.60.40.20-0.2-0.4-0.6-0.8−10=2.1=2.2=2.3=3=50.2 0.4 0.6图2.指数为2.1，2.2，2.3，3和5的无标度网络的度相关系数r N一千N=600N=800N=1000N=1200N=1400N=1600N=1800N=2000RRR魏高新，樊锦/IERI Procedia 4（2013）5357聚类系数C平均路径长度d表1. r的最小值和最大值，=5、3、2.3、2.2和2.1。最小值（r）最大值（r）5-0.660.943-0.290.712.3-0.730.322.2-0.720.222.1-0.67-0.124. 网络拓扑性质以相关度可调模型的构造中N =2.3，N平均路径长度和聚类系数如图3所示。根据我们的建模机制，当0，大节点只与小节点连接，这将导致这样的情况：在一个规模-在自由网络中，每个大节点被许多小节点包围，但这几个枢纽彼此隔离。将整个网络分解为若干个“拟星”子图。当为1时，集线器为 这些小节点几乎是完全相连的，它们围绕着这个“核心”。在这种情况下，网络是紧凑的，因此任何两个节点之间的距离缩短。因此，当网络度从0变到1时，网络度相关性从离散性变为离散性，相应地，平均路径长度呈现出明显的减小趋势。聚类系数C的取值主要集中在0.01 ~ 0.3，这与大多数真实网络的聚类特性吻合较好。当=3和5时，可以发现类似的结果。0.4250.3200.2150.110050 0.2 0.4 0.6 0.8 1图3.本文研究了相关可调网络的网络结构特性，即聚类系数C[14]和平均路径长度d，网络，如2.3，N一千CD58魏高新，樊锦/IERI Procedia 4（2013）535. 结论在本文中，我们已经证明了一种方法，以获得一个新的网络模型与可变度的相关性。通过调整参数，可以很容易地生成混合模式为双折射或双折射的无标度网络。根据度分布的幂律指数，提出的相关调整模式的相关系数r具有不同的变化范围。度分布越不均匀，r的变化区域越小。通过对混合网络结构性质的分析，我们发现混合网络比非混合网络更紧凑。前者的平均路径长度比后者短得多。此外，聚类系数C表明，它是一个更好的现实模型，许多实际网络。并且，该建模算法简单易行，时间复杂度小.在这个方向上，有必要进一步研究这种网络模型的动力学。确认本工作得到了上海市自然科学基金11ZR 1401300和中国大学科学基金的资助。引用[1]王晓芳，李新，陈广荣。复杂网络理论与应用。清华大学出版社; 2006.[2]Newman ME.复杂网络的结构和功能。SIAM Review 2003;45：167-256. [3]第一次世界大战后，“小世界”网络的集体动力学。Nature 1998;393：440-442. [4]第四届中国国际航空航天博览会随机网络中的标度现象。Science 1999;286：509-512. [5]第五届全国人大代表。网络中的混合。物理修订信函2002;89（20）：208701.[6]纽曼MEJ。网络中的混合模式。物理学修订版E。2003; 67（2）：026126.[7]Boguna M，Pastor-Satorras R.相关复杂网络中的传染病传播。物理学修订版E 2002;66：047104。[8] Moreno Y，Vazquez A.结构化无标度网络中的疾病传播。EUR.物理学杂志2003;31：265- 271。[9]作者声明：A.度相关图的抗毁性。物理修订版E 2003;67：015101。[10] Boguna M，Pastor-Satorras R，Vespignani A.度相关无标度网络中传染病阈值的缺失。物理修订信函2003;90：028701.[11] 放大图片作者：Xulvi-Brunet R.重新洗牌无标度网络：从随机到随机。物理学修订版E。2004;70（6）：066102.[12] Newman MEJ，Strogatz SH，Watts DJ.具有任意度分布的随机图及其应用。物理学修订版E。2001;64：026118.[13] http://www.yygpzx.com/gzpd/jxzyg/sx/2/25/01/kzzl2.htm上的信息[14] Dorogovtsev SN，Mendes JEF.从生物网络到互联网的网络进化。牛津大学出版社; 2003年。
我的内容管理
展开
