在复杂网络岛屿的出现

文摘

大多数经济增长模型对复杂网络考虑网络包括一个连接块或岛屿,其中包含网络中所有节点。然而,它已经表明,一些大型复杂网络有多个岛,一个岛大小分布()服从幂律函数。介绍了一种增长模式,认为岛屿随着网络的出现。该模型解决以下两个特点:(i)生成一个新岛屿的概率减少随着网络的发展,(ii)创建新的岛屿以一个恒定的概率在任何阶段的增长。在第一种情况下,模型产生岛大小分布,作为一个幂律衰减与一个固定的指数和入度分布的幂律衰减与。第二种情况是,模型描述岛大小和入度衰减为幂律分布和,分别。

1。介绍

研究复杂网络(CN)的兴趣和重要性上升,许多自然和人工系统可以抽象,使用这种类型的网络的建模和分析。这类系统的例子有很多:神经元的连接(1),植物授粉过程(2),基因遗传(3],代谢相互作用[4,5),高速公路和公路网络6)、电子邮件(7),性伴侣8),和许多其他人。

1998年以前,大多数网络使用随机网络模型,研究了该假定每个节点随机选择其他节点连接。这个随机选择过程产生一定的拓扑属性(9]。例如,入度和出度分布可以近似泊松或一个指数函数(9]。

随机模型采用真实数据成为可用之前,允许从这个模型验证的属性和特征。不过,很难模仿的真实网络的行为,因为许多因素需要执行这些模拟是未知的。在这种背景下,Paxon和弗洛伊德发表了一篇文章,描述了因特网(模拟的主要困难10]。

提供了新的见解的红肿在1998年,当他发布了一个关于引文的分布在科学出版物11]。在他的研究中,出版物被描述为一个网络,一篇文章被表示为一个节点和之间的引用论文被表示为一个网络优势。红肿的尾巴发现引文分布的幂律指数衰减。

1999年,凯利斯等人发表了重要的拓扑属性出现在互联网12]。最有趣的是互联网的出度和入度分布的结论在自治系统规模服从幂律分布12]。在同一年,亚当等人表明,WWW也遵循幂律分布在它的一些拓扑性质(13]。这些研究表明,这些网络不能使用随机模型分析,因为他们的一些连接属性不像泊松或作为一个指数函数,而是一个幂律函数。

重要的是要注意,虽然这些网络是完全不同的他们仍然有相似的属性。例如,即使在网络的节点数量翻番,其直径没有显著改变。在这种背景下,直径是需要访问的节点数量最长的所有最短路径的所有两两节点之间的网络。

这些调查已经启动的分水岭幂律的行为和其他属性的搜索系统可以建模为一个CN。几年后这个搜索导致发现证实,幂律分布和它们的属性,如集群和直径,可以发现在大多数的复杂系统(14]。

1998年,瓦特和“发布了一个关于CN他们确认真正的网络之间的一个中间状态随机性和规律性。他们给这种类型的系统,小世界网络由于其小直径,和他们也引入了一个机制来产生。然而,没有知识的内部流程能够重现这些属性,因此没有增长模式将允许研究它们。在这一点上,巴斯和艾伯特发表的一项研究[15CN],他们引入了一个经济增长模型基于节点聚合过程与优惠附件。这个模型产生网络的度分布的幂律衰减指数等于3。这样一个模型,但是,有一些限制:它只生成与固定网络度分布指数。这个结果与实际网络服从幂律出度和入度分布,既表现出指数。因此,新工作开始寻找新工艺可以列入Albert-Barabasi模型为了复制相同的拓扑属性中发现真正的CN。

其中的一些局部流程已经进行了研究。例如,Krapivsky et al。16)实现非线性优惠附件增长机制。Dorogovtsev和门德斯17)提出另一个模型中节点得到一个初始吸引力出生的时候。这是他们如何解决矛盾巴斯的原始模型指导网络可以通过下面的例子说明:在学期的第一天在教室没人知道彼此。巴巴斯模型后,学生获得一个新朋友的概率正比于他或她已经有朋友的数量。因为没有朋友,没有创建新的友谊,这不是发生在一个真实的情况。

另一个本地流程研究是一个由Dorogovtsev引入和门德斯(18)认为节点可能会老,减少自己的魅力。例如,科学论文的引文随时间减少。艾伯特和巴斯引入了模型与重组19),有一个概率一些节点删除链接一个节点然后使用优惠附件节点使用一个新的链接。这个过程可能会发现在某些网络,比如WWW当网管删除超链接,添加一个新的。Esquivel-Gomez et al。20.)描述了一种模型,禁止多个相同的节点之间的联系。Acosta-Elias et al。21]研究延迟的影响,基于这样一个事实:每个新节点选择其他节点它应该连接使用本地信息,而不是全局拓扑信息。换句话说,延迟允许一个新节点的行为选择新连接系统的基于局部视图。

还有许多其他模型、过程和特性,研究了CN。这些可能在各种评论文章(咨询14,22,23]。然而,经过16年的研究和分析不同的CN,似乎缺乏共识和知识管理这些系统的基本规律。

利用渗流的概念,分析研究岛屿或连接组件的属性随机和CN [24]。此外,岛屿已经观察到在现实网络:布罗德et al。25]研究了WWW样本与15亿年大约有2亿个网页的链接,发现与大小岛屿,表示为的页数,表现出幂律分布指数等于2.54。这个岛大小的幂律分布允许存在的巨大岛屿(巨大的连接组件)。确定任何给定节点的概率属于这些巨大岛屿的概率计算是很重要的,因为它允许消息由一个节点到另一个节点或建模策略,可以阻止流行病的传播。事实上,在文献中可以找到增长模式能产生与社区结构[CN的26- - - - - -30.];即网络包含组的节点之间的强连通但弱与其他节点组成的网络。同样,存在增长模式(20.,31日- - - - - -35],考虑每个节点添加到网络总是连接到现有的。换句话说,这些模型中的所有节点形成一个岛,它包含所有节点的网络。然而,在一些真正的网络,如美国专利引文网络(36),多个岛屿,因此节点形式遵循幂律分布(37]。

可能导致一些真正的CN岛屿的起源是,在网络的增长,一些节点可能是与生俱来的导出链接(即为零。专利没有引用其他专利),这将导致生成新岛屿。

本文提出了定向CN的增长模式,认为岛屿随着网络的出现。在提出的模型中创建新的岛屿与概率,考虑两种不同的情况:)网络的一生期间保持不变()减少随着网络的发展。通过数值模拟分析和验证显示,第一种情况下,模型生成定向CN幂律的行为入度(),岛的大小()分布和这两个可调的来。的第二个案例指数是固定的和,分别。

本文组织如下。部分2概述了本文提出的模型的特性。模型的解析解和实验细节和结果存在于部分3。最后,讨论和结论部分4和5,分别。

2。模型

我们认为新岛屿的诞生是由一个概率通过考虑两种情况:(我) ,在那里是网络中节点的数量。在这种情况下,一个新岛屿出生的概率减少网络中节点数量的增加。这个想法从实际网络映射如下:在一个科学论文引文网络中,当很少有论文(节点),更可能的是,一篇新论文不引用其他论文(生成一个新岛屿),因为它地址一个全新的科学话题。相反,当论文的数量增加,一篇新论文地址的概率一个全新主题减少;从而产生一个新岛屿的概率也降低。(2) ,。在这种情况下,创建一个新岛屿的概率保持不变在整个网络的生活。

此外,网络的发展是通过添加一个节点在每个时间步执行。在一开始,只有节点存在于网络,为每一个新节点添加到网络的以下规则执行:(我)的概率,没有连接到任何网络中节点。也就是说,生成一个新岛屿(见图1)。(2)有互补的概率,随机选择一个节点和连接,以及所有节点有一个传入的链接(见图1)。

3所示。模型的解析解

3.1。岛屿大小分布

为了获得解析解连续介质方法(38使用以下微分方程采用:

方程(1)描述了岛屿的数量的变化与节点总数网络中的节点。术语描述了一个新岛屿的诞生;也就是说,一个新节点模型的情况不与任何节点(这个模型的第一条规则)。这个词描述了模型的第二条规则,术语占一个新节点的情况随机选择一个节点属于一个岛屿节点和连接到它,因此增加。这个词描述了一个新节点的情况随机选择一个节点属于一个岛屿节点和连接到它,因此减少。

方程(1)也可以用一个线性微分方程的标准形式: 为了调查的影响和在,(2为每个其中之一)是解决。与,(2)以下形式: 为了获得,(3)解决,,等等。为,(3)以下形式: 和解决(4)给 在哪里是一个常数,是指数积分函数。作为,(5)的收益率。解决(3)以下产生以下值: 从之前的结果(见(6))可以推断出 也就是说,与该模型能够产生岛的大小分布用幂律的行为与固定指数。

为,(2)以下形式: 为了获得,(8)解决,,等等。为,(8)以下形式: 解决(9)给 在哪里是一个常数。作为,(10)可以近似 解决(8)收益率 从之前的结果(见(11)和(12)可以推断出 与γ函数近似我们获得 从(14),当该模型能够产生岛的大小分布用幂律的行为为与指数。这允许将值从来。

3.2。入度分布

为了获得入度分布的解析解与该模型生成,使用连续介质方法(38]。因此,微分方程描述的入度分布可能写如下: 方程(15)描述了数量的变化的节点链接数量网络中的节点。这个词代表着节点的数量链接的增加,描述了一个新的节点随机选择一个节点与传入的连接和连接到它,描述如何随机选择一个节点的in-neighbor有传入的连接和连接(见图2);因此增加。这个词考虑如何与节点的数目链接减少,和术语和执行类似的功能和。最后,条款和模型添加一个新节点的影响为零链接使用模型的第二和第一条规则。

方程(15)可能是写在一个线性微分方程的标准形式: 为了分析的影响和在,(16为每个其中之一)是解决。

为,(16)以下形式: 解决(17)对于一些值可以推断出 也就是说,与该模型能够产生入度分布用幂律的行为为与固定指数。获得的相同的结果以前Krapivsky和红肿32)在一个类似的模型没有考虑岛屿在网络的出现增长。

为,(16)以下形式: 解决(19)数值产生 与γ函数近似我们获得 因此,如果该模型能够产生入度分布用幂律的行为为与指数。这允许将值从来。

3.3。试验细节和结果

为了验证分析预测(见(7)和(13)、4进行了数值模拟。对于每一个模拟,指导网络的发展来节点实现了考虑以上提出的模型。图3显示,由我们的模拟和分析结果符合适当。

为了验证分析预测(18)和(20.)、4进行了数值模拟。对于每个仿真,我们认为直接网络的发展来节点。图4显示的比较产生的模拟和分析结果,表明两个适合性。

图5显示了实验出度分布。可以看出,当,该模型产生的网络泊松分布(图5(一个))。另一方面,当,作为一个指数函数衰减,而它的展品指数和泊松分布的组合(见图5 (b))。

3.4。数值研究和在这些岛屿

为了调查入度和出度分布发生在与我们的模型生成的岛屿,几个数值模拟也执行。数值模拟是模拟一个网络的发展来节点与和(与)和三个大小不一的岛屿被随机选中。

数据6(一)- - - - - -6 (d)表明,入度分布的岛屿都是遵循幂律指数。唯一的区别是它们之间的规模由于每个岛的大小。更准确地说,所有的入度分布是一致的(18),通过Krapivsky和红肿32]。上面的结果很容易解释在每个岛以来,入度分布管理只有通过复制过程,来自的幂律指数。出度分布相似的行为是观察(图7)。

4所示。讨论

重要的是,在这个模型时的情况随着节点数的增加,不考虑。这是因为当足够大,新节点加入网络的高概率不会连接到其他节点,从而产生新的岛屿。因此,由此产生的网络是由一个大数量的孤立节点。情况,一个新节点可以连接到节点出现在不同的岛屿并不认为,因为这将导致两个或两个以上的岛屿的融合。这些案例会包括在未来的工作中。

同时,该模型产生的网络与出度分布指数和泊松分布。这与一些真正的出度分布网络的出度分布遵循幂律。这是该模型的一个限制,可能是未来研究的话题。

最后,应该注意的是,获得的结果(14)类似于西蒙提出的模型39),这是解释词的分布开发的散文样本出现的频率。值得一提的是,这样显著不同的行为产生类似的数学结果。

5。结论

总之,美国专利引文网络等大型复杂网络(36有多个岛和它的岛大小分布 遵循幂律(37]。为了复制这种行为,我们引入了复杂网络的增长模式,认为建立岛屿在网络的增长。在这个模型中两种情况考虑:即,创建岛屿更频繁的在网络发展的早期阶段和新岛屿保持不变的概率随着网络的发展。在第一种情况下,生成的网络和与幂律行为比例指数和,分别。第二种情况下使用时,网络生成的展品和与幂律行为比例指数,从来。

相互竞争的利益

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

确认

这项工作是支持的部分Consejo Nacional de Ciencia y Tecnologia Secretaria de Educacion Publica-PRODEP (DSA / 103.5 / 15/6660)。

引用

1. m . Rubinov o·斯波恩,“复杂的大脑连通性:网络措施使用和解释,“Euroimage,52卷,不。3、1059 - 1069年,2010页。视图:谷歌学术搜索
2. c·坎贝尔,s .杨、k·谢伊和r·阿尔伯特”plant-pollinator网络拓扑从物种灭绝,很容易崩溃,”物理评论E,卷86,不。2、文章ID 021924、8页,2012。视图:出版商的网站|谷歌学术搜索
3. s . Tavazoie j·d·休斯·m·j·坎贝尔,r . j .赵和通用教堂,“基因网络结构系统的决心,”自然遗传学,22卷,不。3、281 - 285年,1999页。视图:出版商的网站|谷歌学术搜索
4. h·宋,b . Tombor r·阿尔伯特·z n . Oltvai A.-L。巴斯”大型组织的代谢网络,自然,卷407,不。6804年,第654 - 651页,2000年。视图:出版商的网站|谷歌学术搜索
5. g .巴斯勒z Nikoloski a . Larhlimi a l·巴斯和y y . Liu”控制在代谢网络通量,基因组研究,26卷,不。7,956 - 968年,2016页。视图:出版商的网站|谷歌学术搜索
6. 诉Kalapala诉Sanwalani, a . Clauset和c·摩尔,尺度不变性在公路网络,“物理评论E,卷73,不。2、文章ID 026130, 2006。视图:出版商的网站|谷歌学术搜索
7. h·埃贝尔,我。Mielsch, s . Bornholdt“无标度拓扑”的电子邮件网络,物理评论E,卷66,不。第三条ID 035103, 2002。视图:出版商的网站|谷歌学术搜索
8. p . s . Bearman j .喜怒无常,k .研究”连锁店的感情:青少年恋爱和性爱的结构网络,”美国社会学杂志》,卷110,不。1,44 - 91,2004页。视图:出版商的网站|谷歌学术搜索
9. p .鄂尔多斯和a . Renyi“随机图。”出版Mathematicae1959年,卷。29日。视图:谷歌学术搜索
10. 诉Paxon和弗洛伊德,“为什么我们不知道如何模拟互联网,”冬季模拟研讨会论文集,1997年12月。视图:谷歌学术搜索
11. 美国红肿,“你的论文有多受欢迎?引文分布的实证研究”,欧洲物理期刊B,4卷,不。2、131 - 134年,1998页。视图:出版商的网站|谷歌学术搜索
12. m·凯利·凯利和c·凯利,“网络拓扑的幂律关系,”会议的程序在应用程序、技术体系结构、计算机通信和协议(SIGCOMM ' 99)剑桥,质量,美国,1999年9月。视图:出版商的网站|谷歌学术搜索
13. l·a·亚当b . a .胡伯曼a .巴斯r·阿尔伯特·h·宋和g . Bianconi“万维网的幂律分布科学,卷287,不。5461,2115年,页2000。视图:出版商的网站|谷歌学术搜索
14. r·艾伯特和A.-L。巴斯”统计力学的复杂网络,“现代物理学的评论,卷74,不。1,2002。视图:出版商的网站|谷歌学术搜索|MathSciNet
15. A.-L。巴巴斯和r·阿尔伯特”出现随机网络的扩展,“美国科学促进会。科学,卷286,不。5439年,第512 - 509页,1999年。视图:出版商的网站|谷歌学术搜索|MathSciNet
16. p . l . Krapivsky s红肿,f . Leyvraz“连通性的随机网络,”物理评论快报,卷85,不。21日,第4632 - 4629页,2000年。视图:出版商的网站|谷歌学术搜索
17. s . n . Dorogovtsev和j·f·门德斯”,完全可以解决的小世界网络”,Europhysics字母,50卷,不。1、1 - 7,2000页。视图:出版商的网站|谷歌学术搜索
18. s . n . Dorogovtsev和j·f·f·门德斯,“进化”网络与衰老的网站,物理评论E,卷62,不。2,p。1842年,2000年。视图:出版商的网站|谷歌学术搜索
19. r·艾伯特和A.-L。巴斯”演化网络的拓扑:本地事件和普遍性,”物理评论快报,卷85,不。24日,第5237 - 5234页,2000年。视图:出版商的网站|谷歌学术搜索
20. j . Esquivel-Gomez r . e . Balderas-Navarro和j . Acosta-Elias大肠尤加尔德这样”的成长指导复杂网络优惠附件:影响禁止多个链接,”国际现代物理学杂志》上,26卷,不。6、文章ID 1550066, 2015。视图:出版商的网站|谷歌学术搜索
21. j . Acosta-Elias p·d·Arjona-Villicana, l . Moldes-Navarro”时间延迟的影响,复杂网络的连通性分布使用Barabasi-Albert模型,生成“航空杂志上墨西哥德运动,60卷,不。2、145 - 148年,2014页。视图:谷歌学术搜索|MathSciNet
22. s . n . Dorogovtsev a . v . Goltsev和j·f·f·门德斯,“在复杂网络临界现象”,现代物理学的评论,卷80,不。4、1275 - 1335年,2008页。视图:出版商的网站|谷歌学术搜索
23. s . Boccaletti诉Latora,莫雷诺y、m·查韦斯和D.-U。黄”:复杂网络的结构和动力学”,物理的报告,卷424,不。4 - 5,175 - 308年,2006页。视图:出版商的网站|谷歌学术搜索|MathSciNet
24. n . Schwartz r·科恩,d . ben-Avraham A.-L。巴斯和s . Havlin”渗透在无标度网络,”物理评论E,卷66,不。1,文章ID 015104, 2002。视图:出版商的网站|谷歌学术搜索|MathSciNet
25. a·布罗德r·库马尔·Maghoul et al .,“网络图结构,”计算机网络,33卷,不。1,第320 - 309页,2000。视图:出版商的网站|谷歌学术搜索
26. X.-J。徐、张x和j·f·f·门德斯,“越来越多的社区网络与当地事件,”自然史答:统计力学及其应用,卷388,不。7,1273 - 1278年,2009页。视图:出版商的网站|谷歌学术搜索
27. j . Liu h·a·阿巴斯w·钟和d . g .绿色,“Local-global交互和无标度网络的出现与社区结构,”人工生命,17卷,不。4、263 - 279年,2011页。视图:出版商的网站|谷歌学术搜索
28. l .郭和x Cai”出现的群落结构自适应社交网络,”在计算物理学通讯,8卷,不。4、835 - 844年,2010页。视图:出版商的网站|谷歌学术搜索
29. j . m . Kumpula j。Onnela j . Saramaki j·安德烈•柯特兹,k . Kaski”模型加权社会网络社区出现的“计算机物理通信,卷180,不。4、517 - 522年,2009页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
30. j . c . Gonzalez-Avella m·g·科森扎j·l .埃雷拉和k . Tucci”在共同进化的网络社区的出现和持久性EPL (Europhysics字母),卷107,不。2、文章ID 28002, 2014。视图:出版商的网站|谷歌学术搜索
31. j . Esquivel-Gomez p·d·Arjona-Villicana, j . Acosta-Elias”当地的影响过程和多个链接的禁令在指导复杂网络的拓扑特性,”国际现代物理学杂志》上,26卷,不。12篇文章ID 1550142, 2015。视图:出版商的网站|谷歌学术搜索
32. p . l . Krapivsky和红肿,“网络增长通过复制。”物理评论E,卷71,不。3,2005。视图:出版商的网站|谷歌学术搜索
33. b . Bollobas b .基督徒,j .柴叶斯和o .赖尔登,直接无标度图工业与应用数学学会、SODA03费城,宾夕法尼亚州,美国,2003年。
34. j . Esquivel-Gomez大肠Stevens-Navarro, Pineda-Rico, j . Acosta-Elias”的增长模式指示出度分布的幂律形状复杂网络,”科学报告5卷,第7670条,2015年。视图:出版商的网站|谷歌学术搜索
35. j . Esquivel-Gomez p·d·Arjona-Villicana e . Stevens-Navarro Pineda-Rico, r . e . Balderas-Navarro和j . Acosta-Elias”在复杂网络的增长模式能产生与广泛指数幂律分布有关学位,”科学报告,5卷,p。9067年,2015年。视图:出版商的网站|谷歌学术搜索
36. b·h·霍尔,a . b . Jaffe和m . Trajtenberg“NBER美国专利引文数据文件,”美国国家经济研究局工作论文8498、2001、https://scholar.google.com/citations?view_op=view_citation&hl=es&user=xNiD7IUAAAAJ&citation_for_view=xNiD7IUAAAAJ aqlVkmm33-oC。视图:谷歌学术搜索
37. 诉Batagelj, h。一杯啤酒,a . Ferligoj和a .Žiberna Eds。数据科学和分类分类研究,数据分析,和知识组织,施普林格,柏林,德国,2006年。视图:出版商的网站
38. A.-L。巴斯r·阿尔伯特·h·宋,“平均场理论为无尺度随机网络,”自然史答:统计力学及其应用,卷272,不。1,第187 - 173页,1999。视图:出版商的网站|谷歌学术搜索
39. h·a·西蒙,”偏斜分布函数的类”,生物统计学,42卷,第440 - 425页,1955年。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet

版权

版权©2017 j . Esquivel-Gomez et al。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。