Auto Byte

专注未来出行及智能汽车科技

微信扫一扫获取更多资讯

Science AI

关注人工智能与其他前沿技术、基础学科的交叉研究与融合发展

微信扫一扫获取更多资讯

学术菠菜 Jasmine排版Mascara Jasmine校审王健嘉(上海大学)解读学术渣 优学术责编

Nature通讯:驯化发生在互联网络上演化过程的非平衡动态

Taming out-of-equilibrium dynamics on interconnected networks

作者:

Javier M. Buldú, Federico Pablo-Martí, Jacobo Aguirre

地址:

https://www.nature.com/articles/s41467-019-13291-2

一、前言

这篇论文提出一种新的方法来实时描述、预测和管理发生在互联网络上演化过程的非平衡动态。

这一目标的实现是通过对现象学的全面分析处理,并将其简化为一个二维的通量图,以便实验人员在每一步预测修改不同系统之间联系的动态结果。实验结果与真实数据相一致,该方法可以被移植应用于集群网络和任何规模、拓扑结构或起源的互连网络,诸如创新结构的知识纠纷、国际经济关系和疾病在社会中的传播方式等。

二、介绍

许多真实世界的网络可以被视为拥有自身标识的系统,可与其他实体相互连接,共同组成所谓的“网络的网络”。这些复杂系统的某些特性与孤立系统截然不同。

当网络属性在与其他网络交互时,它们会发生改变,这一事实为在网络之间定义最佳连接提供了可能性。举个例子,一个网络在网络的网络中的重要性通过其累积的特征向量中心性来衡量,而这一点又很大程度上依赖于它的它的谱属性(即邻接矩阵的最大特征值)和特定的连接器节点(即连接到其他网络的连接器的节点)。

前一种分析的一个主要局限性是,它们主要关注系统的渐近平衡状态。然而,许多真实的过程是永远远离平衡的。网络不能逃避这一现实,因为大多数真正的网络系统是在通过时间不断进化的。

在网络竞争资源给定的框架下,一个主要的目标可能是将达到均衡的时间最小化——或最大化,而不是将某个结果的最终价值最大化。这一事实引出了一个自然而然的问题:为什么我们不应该寻找一个依赖时间的次优连接策略,作为补偿,它需要更短的时间来达到平衡?此外,如果网络决定在某个时间修改其连接策略以避免有害的平衡状态,该怎么办?

这篇文章描述了网络上的动态过程是如何达到平衡状态的,以及通过实时精确地管理连接它们的链路来实现这种动态行为的潜在指导。此外,文中介绍了一个基于被研究系统的光谱特性的新框架,该问题的分析处理允许预测网络之间的连接器链接如何影响整个系统的演变和实时调整这些链接的后果。作者还提出了多种应用来描述这一新视角的潜力和进一步发展的途径。

三、实验相关

1.基本方法和定义

• 基本方法

本文研究发生在两个网络A和B上失去平衡的动态过程,它们通过一定数量的连接器构成一个含有两个网络的“网络的网络”---T。

随时间演变的过程由公式(1)给出:

其中,M是一个通用的过渡矩阵,用于描述发生在两个网络上的动态过程;n(t)是一个代表系统在时间t的状态的向量,n(0)是初始状态条件。

向量n(t)代表不同的大小取决于系统的性质。可能是社会学背景下的人数,可能是生物学环境中的有机体或分子数,也可能是金融和经济网络中的货币或商品与服务的数量,亦或者是创新网络中的知识,等等。为简单起见,我们将使用通用术语population向量代表n(t),因此每个节点i在时间t拥有一个population---n_i(t),每个网络一个population--PA(t)和PB(t)等于在每个时刻留在该网络的节点的population占总population的比例。

• 系统的渐近平衡

很容易看到n(t)→u_(T, 1)当时间增长时,u_(T, 1)为与过渡矩阵M的最大特征值相关联的特征向量。此外,u_(T, 1)强烈依赖于连接器节点,即那些通过连接器连接链接,以及从孤立的网络A和B获得的最大的特征值λ A1和λ B1。为了方便性,我们假设网络A和B,满足λ A, 1>λ B, 1。当λ1随着链接和节点的数量增长时,我们称A为强网络和B为弱网络。

• 特征向量中心

与表示网络的矩阵的最大特征值相关联的特征向量。它被广泛地用于测量网络中节点的拓扑重要性,并被实验证明在知识传播系统中是至关重要的。我们将网络A和B的中央(C)和外围(P)节点i使用大和小的中心性(Ul)i来各自命名。当每个网络被孤立时计算(因此每个节点在整个过程具有一个恒定的数量)。

• 引入结论

两个互联网络通过低中心性的节点(即使用外设-外设(PP))连接可以使强网络A保留尽可能多的用户,而通过中心节点(central - central (CC)连接)的连接对弱网络最有利。然而,这两种连接策略的结果都是在平衡状态下测量的,不考虑实现它所需的时间,也不考虑网络修改其互连的能力。之后该文章将分析在网络远离平衡状态时研究网络上动态系统的重要性。

2.一个说明时间重要性的例子

——知识在创新网络传播的模型

• 对模型的描述

①节点代表个人或公司,他们与他人竞争或合作,以获取生产某种产品或控制某种技术的最有价值的知识;

②假设知识只能通过与搭档的合作过程和知识交换创造。在这些工作中,知识交换被理解为正式或非正式的研究与开发(R&D)关系,可以用个体之间的双边互动来描述;

③在许多情况下(例如生物技术行业),关联性较低的组织最有可能失败。

根据以上三点,在网络结构中与其他公司建立联系总体上似乎是一个不错的策略。

描述知识在网络上传播动态的方程为:

其中,n_i (t)表示个体i在时间t的知识积累,这些知识在一个时间段内只能从个体j转移到与其直接相连的个体i。{nn}_i表示节点i的近邻。其动态可表示为矩阵形式:

其中,G是网络的邻接矩阵,如果节点i和j相连,其元素G_ij=1,否则G_ij=0。

• 具体过程

两个网络A和B,它们在各自的节点上竞争所积累的知识。首先假设这两个网络最初是断开的,最强的网络在完全没有知识的情况下开始,并愿意通过连接器节点连接到最弱的网络,以在渐近平衡时获得最大可能的知识,但同时最小化达到这种平衡的时间。

为清楚起见,在这个例子中,文章先分析了网络通过一个唯一的连接器链接进行连接的情况,但稍后将证明,这种情况可以直接推广到更多的链接。

图1:两个互联网络上演变的动态过程

图1显示了几种优化知识从弱网络B的N_B个节点向强网络A的N_A完全转移的策略。P_A (t)代表在t时刻在网络A中的知识占总知识的比例。显而易见,P_B (t)=1- P_A (t)。

• 静态策略

①通过中心度最高的节点(CC)连接网络A和网络B;

②通过外围节点(PP)连接网络A和网络B。

• 动态策略

在有必要的情况可随时修改连接器的连接,同时尽量优化所积累的知识和到达平衡的时间。

①穷举方法,探索能使知识流量在之后n步中最大化的方法(n=5和10)所有可能的组合;

②基于选择CC的策略的启发式方法(它会导致状态快速远离平衡),直到知识流量变得非常低,因为此时到达了CC渐近平衡,然后转换成PP策略,这种策略比较慢,但是可以使强网络最后获得尽可能多的知识。

• 策略比较

图1显示穷举方法是最有效的方法,但是计算代价非常高,因为每经过一个时间t,需要计算两个网络之间所有可能的NA*NB个连接的后n个步骤。另一方面,基于CC和PP策略相结合的启发式方法得到了一个解,该解达到了网络A的最优知识,仅比穷举法稍慢,但计算速度快几个数量级。

如果实验的目标是阻碍创新的传播而不是促进传播,一个有效的启发式策略将连接通过PP连接(最小化流量)持续很长一段时间,当弱网络的剩余信息在CC连接达到均衡状态时,通过改变连接状态彻底变成CC可以完全阻止通量产生。

3.现象学的分析方法

这篇文章主要关注两个独立的网络,它们通过有限数量的连接器相互连接,其中普通的人口(或知识)随着时间的推移而发不断变化,连接器链接可以在任何时间步长变化。

文中特别注意的是得到人口分布和人口流动的理论表达式,即在每个时间步长内,人口从一个网络流向另一个网络的比例,以获得在两个网络的属性在变化过程中的未来行为,它们潜在的连接策略和初始人口分布。

4.人口分布的演变

文中通过公式4给出两个互联对称网络上一般过程随时间的演化规律:

其中n(t)的含义如前所述,M是描述动态过程的过渡矩阵;N_t = N_A + N_B是网络的网络T中的节点总数;α_i = n(0) • u_(T, i)是初始条件在网络T的矩阵M的第i个特征向量上的投影。

假设矩阵A和B满足λ_(A, 1) > λ_(B, 1),其中u_(A, i)和λ_(A, 1)是网络A的矩阵M_A的第i个特征向量和对应的特征值,B同理。使用公式5来估计初始条件n(0):

其中,

引入定义在0~∞之间,时间为t时的互联网络中的人口分布函数x(t):

联立公式(4)和(6),运用相关理论,我们可以获得矩阵T的第一和第二特征值和特征向量,作为只依赖于相互隔离的网络A和B的特征值和特征向量、连接器的连接权重ϵ和连接器的信息的量。

在网络T上的人口分布函数x(t)服从公式(7):

其中:

P是一个满足条件的矩阵:如果A中的节点l和B中的节点m通过一个连接器相连,则P中的元素P_ml = P_lm = 1,否则P_ml = P_lm = 0。

F代表在A, B相互连接之前,所有连接节点的特征向量中心的测量结果之和。因此,ϵF被命名为连接强度,ϵF/△λ被命名为正常连接强度。

值得注意的一点是,PP连接会导致F的值较低,CC连接或是大规模的PP连接能带来较大的F值。

最终可以得到结论--x(t)的表达式只依赖于四大因素:

①孤立的网络A和B的第一个特征值λ_(A, 1)和λ_(B, 1);

②通过F可以得到的连接节点的中心性,而F取决于A和B的第一个特征向量u_(A, 1)和u_(B, 1);

③连接器连接权重ϵ;

④初始条件x_0。

5.人口流动和渐近平衡

人口流量x(t):衡量在时间t时,人口从网络A传播到网络B的速度。它允许网络在此过程的每一步选择最优策略来根据具体情况,最大化或最小化这一流量。根据公式(7),得到公式(9):

其中K、L、△λ、ϵ各含义与公式(7)中相同,的值越大意味着人口分布的变化越快,易得到当系统处于平衡状态时= 0,代入公式(7),我们得到公式(10):

当两个网络通过外围节点(PP策略)连接时,ϵF ≈ 10,x_eq = 0,人口的均衡分布充满了强网络A,且几乎与u_(A, 1)一致。

CC策略即ϵF的值尽可能大,推动人口尽可能向弱网络B流动。

在两个网络之间的连接策略,即ϵF不改变的情况下,如果x_0 >x_eq,人口将会从B单向往A流动,反之则由A向B流动。

图2:人口流量的数值和解析计算之间的比较

图2显示了在t=1和t=150时,与正常连接强度ϵF/△λ和初始人口分布x_0的函数关系:a图和b图中,人口流量绝对值使用图1中用到的无标度网络对两个互连网络的非平衡态进行数值计算得到;c图和d图中,人口流量绝对值通过公式(9)分析得到。图中的白线对应于平衡态x_0 = x_eq。

可以发现,正如对现象学的分析处理所预测的那样,人口流量超过平衡线时,人口将向网络A流动,而如果在平衡线以下,人口流动将趋向于网络B。此外,在此动态过程刚开始时,远离平衡(a和c的右上角)的CC连接流量最大;然而在大多数情况下,网络使用PP连接。

6.人口流量图和框架的适用性

• 人口流量图的建立

利用上述结果可以创建一个人口流量图,作为研究一般互联网络上的非平衡过程的一般框架。具体来说,主要是利用了以下几点:

①在= 0的情况下得到平衡曲线,这一点依赖于网络的内部拓扑结构,或者说是它们的最大特征值和网络之间的连接器连接情况,与初始人口分布x_0无关;

②x_0>x_eq时,<0;x_0<x_eq时,>0。

因此,xxx图的轨道每一步都会向平衡边界移动一段垂直距离;同时,在任何时候改变连接器连接将会水平地移动轨道。

通过这种方法,可以得到一个图,它可以表示在每个时间步长选择连接器链接的条件下,从任意初始条件到任意最终平衡状态的完整轨迹。

图3:人口流量图

• 框架适用性的探究

如果把现象学看作一个游戏,那么任何一种竞争规则都包含在这个框架中,例如一个独特的网络在最短的时间内获取最多的人口,一个网络之间的竞争,其中竞争者轮流选择连接器链接,等等。

在图3中绘制了几个样本轨道来显示这个框架的通用性:

⑴大多数人口最初放在弱网络B(x_0 = 2.5)中,目标是尽可能快地让人口移动到网络B中:

①通过图1所示的穷举方法来实现,在每一步中,系统选择的连接使人口流量达到最大,经过十步,策略从CC逐渐变化到CP,最后到达PP连接(轨迹(i));

②通过启发式方法,即网络通过CC连接,直到系统接近平衡状态,改变到PP连接(轨迹(ii))。

⑵人口最初放在弱网络A(x_0 = 0)中,选择一个中间连接,推动人口向网络B流动,直到x(t)达到一个定值(此例中x(t) = 0.6),立刻改变连接器的连接方式和它们的权重,来停止人口流动,以无限期维持在这种情况下人口分布 (轨迹(3));

⑶轨迹(4)显示了两种不同策略交替的最简单情况。该方法表明,这种情况下的最终均衡等价于同时应用两种策略,但将连接器链接的权重减半。

除了图3所示的一般例子外,这篇文章还通过对一个研究经济网络演变的实际案例的分析来体现该框架的应用价值。

四、讨论

在这篇文章的这项研究中,作者证明了:在两个相互连接的网络之间,可以通过对连接器链接的适当改变,引导系统的动态,根据需要决定系统从任何初始条件到任何期望的最终状态的演变过程。

文中提出了一个完整的分析处理过程,为了简化系统的管理,引入一个二维结构-人口流量图,其中包含人口随时间的演变,所有可能的初始条件和连接策略。

文中的方法适用于任何规模或拓扑结构的有向和无向网络描述和管理整个系统的非平衡演化,只要系统的动态演化可以通过一个过渡矩阵来建模,即n(t) = M^t n(0),n(t)为某个变量在时间t是网络中每一个节点的状态向量。

作者研究了从2005年到2015年36个经合组织国家的经济网络。面对不同国家的经济行为,文中的方法可以帮助出开发依赖国家的经济和金融形势的积极的经济政策。文中还通过专门的补充注例来提供其方法在其他复杂系统的潜在应用,如在分散的栖息地内的物种的生长的控制和优化的突变——选择进化过程,疾病蔓延在社会环境的描述,和描述了1988年和1999年之间在生物科技方面相互协作网络的进化的潜在的数据集的分析。

AMiner学术头条
AMiner学术头条

AMiner平台由清华大学计算机系研发,拥有我国完全自主知识产权。系统2006年上线,吸引了全球220个国家/地区800多万独立IP访问,数据下载量230万次,年度访问量1000万,成为学术搜索和社会网络挖掘研究的重要数据和实验平台。

https://www.aminer.cn/
专栏二维码
理论Nature驯化智能互联网
相关数据
权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

网络流技术

在图论中,网络流(英语:Network flow)是指在一个每条边都有容量(capacity)的有向图分配流,使一条边的流量不会超过它的容量。通常在运筹学中,有向图称为网络。顶点称为节点(node)而边称为弧(arc)。一道流必须匹配一个结点的进出的流量相同的限制,除非这是一个源点(source)──有较多向外的流,或是一个汇点(sink)──有较多向内的流。一个网络可以用来模拟道路系统的交通量、管中的液体、电路中的电流或类似一些东西在一个结点的网络中游动的任何事物。

推荐文章
暂无评论
暂无评论~