导语


自然界中的网络，连接会增减，但节点的度数有时会保持不变，或随着演化趋于饱和。然而当前的网络生成模型不具备这样的特征。近期发表在 Nature Physics 的论文“度数保持网络的生长”，提出了保度生长模型，能够模拟真实场景中的网络变化，可应用于疾病管控、病毒化传播等领域。


研究领域：复杂网络，生长模型

郭瑞东 | 作者

刘培源 | 审校

邓一雪 | 编辑



论文题目：

Degree-preserving network growth

论文链接：
https://www.nature.com/articles/s41567-021-01417-7




1. 度数维持的网络生成法则




最常见的网络生成模型，是巴拉巴西提出的优先连接（preferential attachment）模型。其中新的节点，优先和已有网络中度数较高的节点建立连接。但真实世界中，节点的度数存在上限。例如社交网络中，一个人能够联系的用户数有限；或者分子结构网络中，原子的连接共价键的数是固定的。而使用优先连接模型生成的网络，则会违背这一性质。除此之外，真实世界中，网络里的连接也会消失，而不是如优先连接模型中，持续增加。


而新提出的保度生长模型（简称保度生长 degree-perserving growth），可以根据参数不同，看成一系列模型。其共同假设是网络中的平均度数之和保持不变。网络中的节点，只能具有有限的连接数，且会有对应的适合连接数。若超过或小于该连接数，这样的节点在网络中所占的比例就会下降。尽管简单，但保度生长模型具有可解析的数学特性，使其应用场景广泛。


保度生长模型假设网络中不存在节点间的多重连边和自循环圈。其基本生成机制如下图所示，每一步节点w移除已有网络G中的k条连接，之后增加2k条新的连接（新加入的连接相互独立，否则可能形成环状结构），由此保持平均度数不变。这一过程，可以看成是新加入的节点，破坏了左图中竖线的连接，增加红线的连接，最终成为已有节点u和v之间的枢纽。

               

图1. 保度生长网络生成机制


当有更高度数的节点加入网络时，可能的减少边的方式，随着新增节点的而改变。当加入的节点度数为4，可能的方式包括两种（下图中的蓝线或绿线），而当新增的节点度数是6时，可能的删除边的方式只有一种（下图中的红线）。

              

图2. 新加入节点的度数和可能的配对方式示例


在商业或社交网络中，该模型描述的过程，可以被解释为新节点是之前节点的中介，其价值在于促进了网络中不同成员的连接。与之相关的，是结构洞（structure hole）理论，该理论指出位于网络中介位置的节点，具有相对竞争优势。


在生成过程中，可能的删除边的方式（没有相连的节点），被称为配对（matching），网络生成过程中，可能的配对数可能会在某次迭代中出现显著波动。例如下图所示，在第二次增加节点时，去除红色的边，网络中可能的配对就会降为0。

               

图3. 保度生长网络生成过程中配对的改变方式





2. 使用保度生长，重构真实网络




该研究中，作者选取了真实世界中，多个领域的网络（包括经济和社会领域的交易网络，共作者网络，社交网络；生物界的线虫神经元连接网络，基因互作网络；生态学中的食物链网络，疾病传播网络以及网络中的路由连接网络），作为预期用保度生长模型重构的网络。之后提出这样一个问题，是否存在一个基于保度生长的生成序列，能够从初始的小型网络出发，生成一个相同结构的网络？如果存在这样的序列，能否轻易地找到这样的序列了？


回答该问题的方式，是从现实的网络出发，逆向的随机选择一个节点，将其连边全部消除，再按保度生长的算法，逐个将节点从网络中移除。如此迭代，直到没有新的节点，可以维持度数不变的方式被移除。通过上述算法，反向得到的便是可用于生成网络的节点加入顺序。之后记录随机移除的节点数，占原网络中节点数的比例。如果该比例较低，说明该网络能够通过保度生长进行构建，尽管真实场景中，这种网络可能不是以保度生长的方式产生的。


图4. 不同的网络中，使用保度生长删除节点后，剩余节点所占的比例（每个网络重复五十次得出的散点图），内部的是纵轴log化之后的结果，横轴是降序排列的顺序


该图中，最不适合使用保度生长构建的网络，前4名中，1、3、4都是过于稠密的网络。这样平均度数过大的网络，天然不适合度数维持一致的生成模型。而对于较为稀疏的网络，唯一的例外是疾病和基因的关联网络。除此之外，大部分的网络，都可以使用保度生长的方式逐个拆解，这说明了在这些有明显差异的现象背后，可能有着共同的生成机制。

               

图5. 包含4158个节点的共作者网络（广义相对论和量子宇宙学领域），该网络可以使用保度生长，从包含507个节点的初始网络生成。





3. 保度生长网络生成模型的应用




由于可以自由选择新加入节点的度数，和新节点加入网络时的配对（matching），保度生长模型不仅可以生成度数不变的网络，也能产生标度一致（呈现幂律法则）的网络。其普适性，使其适合对信息和疾病的传播，以及具有特定性质的同分异构型的分子构架建模。


在一系列保度生长模型中，最简单的是度数有限的情况，即新加入的节点的度数存在上限。该模式生成的网络，能够用作P2P连接下的IP连接网络，可提供稳定的网络访问。当新加入节点的度数和网络中配对的个数相同时，这样的模型称为线性增长的保度生长模型。该模型中节点的度数线性增长，因此生成的网络中，节点的度数分布式均匀的。该论文还介绍了线性保度生长生成的网络具有的数学性质，以及可以生成幂率无关的保度生长的算法。保度生长生成的无标度网络/与诸如优先连接模型不同，保度生长模型构建它们时不会遵从“富者越富”的机制，而是可看成是一种保持功能的“修补”过程。网络在度数增长期间，同时扩大其功能。其中技术细节就不再详述。


该文还讨论了保度生长模型的可能应用。以疾病防控为例，可以应用模型，找出需移除少数节点，以达到阻止病毒在人群或计算机网络中的传播这一目的，也可以反过来，用于设计病毒化营销方案。由于保度生长的网络增长过程，是在原有连接的基础上，增加新的节点。如此可以在病毒传播网络G中新加入免疫节点，这样其不会传播病毒，如此，问题转换为如何加入少量的免疫节点，使得病毒在网络中的传播减缓。

               

图6. 图中的彩色节点是真实的430人际疾病传播网络，按保度生长模型新加入的53个灰色节点，使得网络分成了几个互不连接的部分，从而阻止了病毒的传播


总结来看，该研究提出了一组基于度数饱和这一物理约束的网络生成模型，保度生长可以生成大多数物理网络（度分布可以是均匀的，标度一致或固定的）的精确结构，尽管这本身是一个 NP 难题。研究论证并展示了，保度生长模型在现实世界的建模能力和潜在应用场景。研究强调了保度生长机制的灵活性，它允许调整生成网络的各种统计属性，从而使其具有普适性。而一个有趣的开放问题则是，现实世界网络的那些属性，使得其能够通过保度生长机制生成？



网络科学集智课堂第三期报名中

从数学建模到多学科应用


从现实社会的关系网到虚拟的互联网，从线下到线上，我们的生活始终没有脱离复杂网络。真实的复杂网络从其诞生开始就不断地演化着。网络节点不断地增加，节点之间的连接不断地增长。然而，复杂网络的形成机制是什么？具有什么样的演化规律？它们的演化机制对网络的功能和动力学行为有什么影响？为了回答这些问题，科学家们对复杂网络的探索从未停止。

网络科学是一个蓬勃发展的崭新交叉学科，可以看做复杂系统的骨架，核心是研究各种大型复杂网络之间的共性和处理它们的普适方法，其研究对于发展复杂系统的基本理论及构建产生了极大的推动作用。

网络科学的第三个十年，已经过去了几年。从国内外网络科学研究的发展趋势来看，各种各样的更复杂的网络模型和结构以及高阶相互作用动力学引起了人们的极大兴趣。为了回应这种迫切需求， 我们网络科学第三期课程将围绕复杂网络的数学建模与应用进行多角度的介绍。

集智学园特邀陈关荣、樊瑛、周进、李翔、张江、闫小勇、刘宗华、石川、虞文武、赵海兴、史定华加入打造第三期课程，欢迎你的加入。



详情请点击：
从数学建模到多学科应用——网络科学·集智课堂全新升级


推荐阅读



点击“阅读原文”，报名课程