查看原文
其他

Barabási算法+Physics Reports精选,网络科学综述10年Top10 | 妙算复杂

胡乔、刘培源 集智俱乐部 2022-06-10


导语


自小世界网络模型和无标度网络模型提出后,复杂网络越来越成为重要的研究方法,其理论进展层出不穷。为了梳理近年来网络科学领域的趋势,我们利用AL. Barabási、王大顺、宋朝鸣等人提出的科学学算法,筛选出过去十年发表在Physics Reports杂志的网络科学相关综述文章,并从长期影响力的综合视角,筛选出最有代表性的10篇文章。

胡乔、刘培源 | 作者

梁金、徐恩峤 | 审校

邓一雪 | 编辑





一、十年网络科学综述合集




网络科学是复杂科学的核心内容之一,1998年提出的小世界网络[1]和1999年提出的无标度网络[2]是这一学科兴起的标志。两篇文章引领了一个时代,至今各自获得了数以万计的引用量,并使网络科学成为本世纪的热门研究领域。


20多年过去了,复杂网络、社会网络已经是教科书词汇,相关的研究者也越来越多。那么现在当我们谈论网络科学,我们在谈论什么呢?


回答这个问题需要借助高质量数据。Physics Reports是最有影响力的物理期刊之一,专门发表长文综述,论述相关领域的重要进展和研究趋势。2011年至2020年Physics Reports共刊出近400篇论文。我们使用文本分类方法从中筛选出所有与网络科学相关的论文,一共27篇。


根据这些论文,我们可以对近年的网络科学领域做一个数据概览。我们将这些文章按预估的最终影响力(下表中的 infinite_citation,即时间趋于无穷时的累积引用量,下一节将详细介绍)排序,结果如下:



让我们先来具体看看其中最受欢迎的10篇工作:


Top 1 空间网络

Barthélemy M. Spatial networks[J]. Physics reports, 2011, 499(1-3): 1-101.

复杂系统通常以网络形式组织,而节点和连边嵌入在空间中。真实空间中,连边的长度会产生成本,反过来会影响网络拓扑结构,因此表征和理解空间网络的结构和演变,对于理解交通、城市、通信、社交大脑等各种真实空间中的复杂系统至关重要。这篇论文回顾了从随机几何图、ER图、WS图、AB图及最优网络等模型的空间推广,还讨论了空间网络上的相变、随机游走、同步、导航、弹性和传播等过程。


Top 2 时序网络

Holme P, Saramäki J. Temporal networks[J]. Physics reports, 2012, 519(3): 97-125.

尽管网络结构有助于我们理解、预测和优化动力系统的行为,但许多情况下,连边并不是连续活动的,例如通信网络中连边仅仅表示瞬时连结的序列,再如在患者接触中连边是在一个不可忽略的时间段内活跃,而在大脑神经网络中连边则是神经元或神经区域从静态到动态的激活过程。这篇文章介绍了时序网络的一系列研究,并讨论分析拓扑和时间结构的方法,阐明它们与动力系统行为关系的模型。本文发布于时间网络兴起不久的2012年,当时该领域有多种称谓,如时态图、演化图、时变图、时聚图、时标图、动态网络、动态图、动力学图(temporal graphs, evolving graphs, time-varying graphs, time-aggregated graphs, time-stamped graphs, dynamic networks, dynamic graphs, dynamical graphs)等,这篇综述从一系列跨学科研究中梳理出与时序网络相关的研究。


Top 3 多层网络的结构与动力学

Boccaletti S, Bianconi G, Criado R, et al. The structure and dynamics of multilayer networks[J]. Physics reports, 2014, 544(1): 1-122.

经过21世纪前十年的发展,网络科学在从生命到社会的各类系统研究中获得巨大成功,而面向更加真实的复杂系统建模的多层网络研究,也在第二个十年逐渐兴起。这篇2014年的综述文章,从多层网络、网络的网络、相互依赖的网络以及超图等角度,对多层网络的定义、模型、特征、传播、同步及应用等做了全面的梳理和展望,并影响至今。


Top 4 连续时间量子游走:复杂网络上的相干传输模型

Mülken O, Blumen A. Continuous-time quantum walks: Models for coherent transport on complex networks[J]. Physics Reports, 2011, 502(2-3): 37-87.

量子输运是一个重要的跨学科领域。质量、电荷或能量的输运是许多物理、化学及生物过程的基础,其转移机制与效率则与系统底层结构息息相关,而其底层结构可以是简单晶体、复杂分子聚合体或者一般的网络结构。经典的输运过程可以用连续时间随机游走方法建模,而针对网络模型上激发的相干量子电动力学,连续时间量子游走方法则大有作为。该方法被证明在各种复杂系统的激发动力学中非常有用,例如拓扑无序系统的动力学、生物系统的激发动力学(光合作用等)、信息传递过程等。这篇综述概述了各类连续时间量子游走算法在不同网络上的呈现,讨论将方法应用于长程相互作用和静态无序系统。该文发表于2011年,代表着复杂系统研究的网络模型与量子信息等领域结合的趋势。


Top 5 计算网络生物学:数据、模型和应用

Liu C, Ma Y, Zhao J, et al. Computational network biology: data, models, and applications[J]. Physics Reports, 2020, 846: 1-66.

生命科学是复杂网络研究最佳的应用场景之一,从生物实体所涉及的错综复杂的相互作用中揭示出生物信息,具有重要意义。这篇综述总结了计算生物学的最新发展,介绍了各类生物网络的特性,总结了从网络指标到机器学习的各类基于网络的方法,并讨论如何根据这些方法获得新的生物学洞察。此外,这篇综述还突出了神经科学、人类疾病和药物研发领域的网络科学应用。作为物理学、计算机科学与生物学的典型交叉。该文发表后,集智俱乐部对此做了长文解读——《Physics Reports计算网络生物学长文综述:数据、模型和应用》。


Top 6 网络中的社团检测

Fortunato S, Hric D. Community detection in networks: A user guide[J]. Physics reports, 2016, 659: 1-44.

网络中的社团检测是现代网络科学中最热门的话题之一。社团或团簇通常是节点组,它们相互连接的概率高于其他组的成员。识别社团常常是一个定义模糊的问题,例如社团本身的定义,再如算法的验证和性能比较,这产生了许多混淆和误解。这篇综述则对相关问题做了全面的梳理,对比了各类流行方法的优缺点,并提供了使用建议。


Top 7 复杂网络中的 Kuramoto(振子)模型

Rodrigues F A, Peron T K D M, Ji P, et al. The Kuramoto model in complex networks[J]. Physics Reports, 2016, 610: 1-98.

一组振子的同步,是社会、物理、生物、技术等复杂系统中的涌现现象,而Kuramoto模型是描述这些复杂系统中相干行为如何涌现的经典方法。近年来,对于动态、异构的复杂系统,Kuramoto模型也展示出强大的能力。这篇综述梳理了Kuramoto振子网络同步领域的主要发展,特别是概述了网络模式对耦合相位振子的局部与全局动力学的影响,并讨论了工程、神经科学、物理学和地球科学等领域的应用方向。


Top 8 复杂网络中的关键节点识别

Lü L, Chen D, Ren X L, et al. Vital nodes identification in complex networks[J]. Physics Reports, 2016, 650: 1-63.

真实网络表现出异构性质,节点在结构和功能上扮演着截然不同的决策,因此识别关键节点非常重要,它能够帮助我们控制流行病爆发、分发互联网广告、预测科学出版物的流行等等。在这篇综述中,作者澄清了概念指标,对问题和方法进行分类,回顾了复杂网络关键节点识别的一系列技术,并在不同真实网络上进行了广泛的实证分析和对比。


Top 9 网络上的随机游走和扩散

Masuda N, Porter M A, Lambiotte R. Random walks and diffusion on networks[J]. Physics reports, 2017, 716: 1-58.

随机游走作为基本的随机过程之一,在科学中无处不在,近年来更是在规则网络和具有各种结构的网络上被广泛研究。这篇综述梳理了随机游走在网络上的理论和应用,突出单一和非自适应随机游走。文章重点区分了三种类型的随机游走:离散时间随机游走、以节点为中心的连续时间随机游走和以边为中心的连续时间随机游走,并从单一线路的随机游走拓展到各种类型网络上。


Top 10 复杂网络可通信性的物理学

Estrada E, Hatano N, Benzi M. The physics of communicability in complex networks[J]. Physics reports, 2012, 514(3): 89-119.

复杂网络研究的一个基本问题是提供系统不同部分之间相关性和信息流的定量测量,为此,近年来多个可通信性(communicability)概念被引入真实网络研究中。这篇综述通过考虑两个节点之间所有可能的路由来定义可通信性的测量。文章在各种生物、物理和社会网络上,讨论可通信性测量在复杂系统分析中的应用。


这10篇论文的核心都是网络科学方法,同时主题却十分广泛,似乎暗含了广阔的学术图谱。为进一步分析“网络科学在谈论什么”,我们从这27篇论文的题目和摘要中提取关键词,并按词频画出他们的词云如下。



从词云中我们观察到近十年网络科学发展的两个主要脉络:其一在于广度——即跨学科,物理学、计算机科学、数据科学、经济学、生物学、神经科学、科学学等领域,都在吸收网络科学理论和方法以促进自身发展;其二在于深度——即网络结构和动力学的进一步挖掘,结构包含了高阶网络、多层网络、嵌套网络、时序网络、社团划分等主题,动力学性质如扩散、渗流、同步、演化等主题。


我们还观察到,体现网络结构和动力学的关键词占据了更大的比重,并且从理论上挖掘网络性质的文章相对于跨学科应用的文章获得了更大的长期影响力,还出现了一篇最终引用量过万的论文。理论研究文章的关注度更高,体现了复杂网络/复杂系统建模这一科学主题的持久魅力和挑战性,同时相关的方法可潜在应用于多个领域。


相比之下,侧重于跨学科应用的研究工作受众范围更小,但所有这些研究共同组成了蔚为壮观的网络学科图景,并且足以产生多样化的实践价值。例如疫情期间,关于流行病传播的研究再度成为焦点。基于网络科学的流行病传播模型、网络分片等研究工作为疫情预测和制定防疫策略提供了重要的参考。


跨学科的发展脉络不仅在论文中鲜明体现,在集智社区也是如此。2021年,我们开展的网络科学第三期课程中,就有人类移动网络、流网络、脑网络、图神经网络、多智能体网络等主题。而深度挖掘网络的脉络上,则有多层网络、时序网络、超网络等主题。集智网络科学社群位列学科前沿,为孕育开创性发现提供了可能。


关心网络科学的读者朋友们,这份论文名单中哪些是你们刷过的论文?它们的长期影响力与你心中的网络科学论文重要性排序是否相符呢?欢迎大家留言讨论。





二、如何衡量论文长期影响力?




读者可能记得,上一期妙算复杂文章我们介绍了颠覆性指数Disruption来量化文章的创新性,它对于跨学科的论文评价尤其适用。但本文列出的综述文章,其价值主要不在于创新性,而在于梳理和总结相关主题的研究脉络和最新动向,并对领域发展提供前瞻性的意见。此时基于引用量刻画这类论文的影响力仍然是主要的方法。


不过,直接使用引用量评价论文(或期刊)的影响力存在着诸多问题:如论文发表时间有先后导致不能公正比较;又如现有的引用数(尤其是短期引用数,如3或5年)并不总能代表其长期影响;再比如期刊影响因子(IF)是基于论文引用量计算的,但是同一刊物同期发表的两篇文章,其引用量常常差别非常大。


有没有一种更合理的评价方案呢?大家可能注意到了,在上一节中我们不是按照引用量,而是按照最终引用量对论文进行排序,就是采用了集智科学家王大顺、网络科学家 Barabási 和宋朝鸣2013年在 Science 杂志[4]提出的方法,来衡量论文的长期影响力。下面将具体论述如何创建这样一个指标。


首先,相对于引用数量,引用模式或许可以给我们更多的信息。关于引用模式一个著名的结果是,不同学科的论文,其引用量分布(被引用一定次数的文章占学科内所有文章的比重)经过合适的缩放(rescaling)后服从统一的规律[5]。那么对单篇论文而言,其引用量有无演化规律可循,使我们能根据引用历史预测长期影响呢?


事实上,三大因素主导了单篇论文的引用模式:
  • 偏好依附(preferred attachment):较高引用的文章具有较大的概率被再次引用,这很好地解释了先发优势。偏好依附也是无标度网络的度形成幂律分布的一种方式。
  • 老化(aging):论文的新颖性随着时间推移而衰减。通常而言,在需要引用某主题的文章时,学者们常常引用最新研究,因为这些代表最前沿的进展。
  • 适应性(fitness):论文内在的创新性和重要性,适应性越高,论文被引用的概率越大。
结合这三个因素,我们可以将论文发表 t 时间后被引用的概率表示为三个因子的乘积,经过数学变换可以进一步得到论文 i 在发表 t 时间后的累计引用量的表达式:


其中λi刻画论文适应性的影响,μi, σi画老化效应的影响。Φ(x)是正态分布的累积分布函数,m是常量。给定一组数据 t 和,我们可以通过曲线拟合计算出最佳的λi, μi, σi,确定的表达式。然后代入不同的 t,就可以计算任意给定年份论文i的累计引用量。

至此,我们就有了预测论文长期引用量的方法。再进一步对引用量 c 和时间 t 做归一化,即滤除偏好依附、老化、适应性三大因素的影响,可以更直观地看到,归一化的论文引用量与时间呈现通用的累积正态分布关系,用曲线表示如下:


论文长期影响指标


当我们得到拟合曲线后,可以计算论文的几个特征指标。我们用表示当 t 趋向于无穷大时的值,也就是论文 i 的最终引用量,其表达式为


也就是说,尽管偏好依附和老化效应在短期内对论文的引用量有显著影响,但长期来看论文的最终引用量仅取决于论文适应性。因此可以用来比较不同时期发表的论文的长期影响力。

另一个指标表示论文引用量达到几何平均数()所用的特征时间,它反应了论文早期引用量的增长速率


可见这一特征时间主要取决于参数μi,而与λi, σi无关。




三、集智斑图实践




集智斑图是集智俱乐部创建的复杂科学内容聚合平台,包含了复杂科学最新论文、多领域学习路径、论文解读活动、自组织社区等模块。现在我们将论文长期影响力的预测方法应用到集智斑图的论文中。

对于每一篇论文 ,我们使用历史引用记录拟合参数,并计算论文的最终引用量,下面以排名第8位的论文 p: Vital nodes identification in complex networks 为例进行说明:

(1) 获取 p 发表后每年的引用数据
p 发表于2016年,2016-2021的引用量为: [8,75,123,155,166,132]
( 数据来源于semantic scholar)

(2) 计算 p 的累计引用数据
2016-2021年的累积引用量为:  [8,83,206,361,527,659]

(3) 拟合曲线①,计算出λ, μ, σ
拟合曲线可以使用python中的科学计算程序包scipy,其中的curve_fit函数可以用来做曲线拟合,默认使用的拟合方法是最小二乘法,计算得到的系数(mean ± std)为
λ= 4.06±0.07, μ=0.90±0.01,σ=0.79±0.04

(4) 计算最终引用量


预测的λ=4.06,该文章当前的引用数量为600+,但是预测的长期引用量到达了1100+,说明该文章本身的质量很高,尽管发表了5年仍然有较大的被引潜力。

我们画出 p 引用的实际值和预测值,可以见到本方法在有数据记录的时间段,仅使用λ, μ, σ三个参数取得了很好的拟合效果。同时本方法预测 p 在未来数年内仍有较大幅度的引用增长,之后才趋于稳定。


在我们选出的前10篇文章中,同样也有这样的例子,即长期引用量远大于当前引用,如排名第4的 Continuous-time quantum walks: Models for coherent transport on complex networks 和排名第10的 The physics of communicability in complex networks。这是因为它们的论文质量较高(λ分别为3.75和5.43),达到引用概率峰值的时间较长(分别为5.25年和14年)。尤其是后面这篇,与大部分文章的引用量集中在发表后的3-5年相比,这篇文章明显例外。在发表近10年后,它的引用量不但没有减少,而且呈现加速上升的趋势,使得拟合的达到了14年,长期引用量达到了4000+。这个预测是否准确呢,让我们拭目以待。


用同样的方法可以估计其它论文的长期引用量。需要注意的是,拟合曲线至少需要3个数据点,因此对于2020年及以后的论文,无法得到有效的预测值。这种情况我们做简单的处理:计算其他文章最终引用量与前两年引用量的平均比值,并假定这个比值适用于2020以后的论文,由此得到最终的引用量。




四、总结




本文是妙算复杂栏目第二篇文章,本文第一部分我们基于论文过滤算法,选出了Physics Reports中与网络科学相关的综述合集,并从数据分析的视角做了排序和简单评述。第二部分依据网络科学家 Barabási等人的算法,基于偏好依附、老化效应和论文适应性等三大因素,预测论文的长期影响力,并将这一算法应用在集智斑图实践中。

网络科学是一门充满魅力的学科,自上世纪末兴起以来吸引了众多研究者投身该领域。集智网络科学第三期课程指出:网络科学第一个十年,重点研究了网络的基本模型及其性质;网络科学第二个十年,重点转入了网络动力学的全面研究,以及网络动力学与网络结构相互关系的探索;网络科学第三个十年,高阶相互作用动力学将引起人们的极大兴趣。本文的分析是这一观点的印证,并补充了网络科学跨学科应用的图景。

最后,感谢集智网络科学社区陈关荣、史定华、陆君安等老师为本文贡献的专业观点和宝贵意见。也欢迎社区的技术力量加入计算社群,用技术和计算的力量促进内容创作、提升社区体验。

参考文献

[1] Watts, D., Strogatz, S. Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998). https://doi.org/10.1038/30918
[2] Barabási, Albert-László, and Réka Albert. "Emergence of scaling in random networks."
Science 286.5439 (1999): 509-512.
[3] https://api.semanticscholar.org/graph/v1
[4] Wang, Dashun, Chaoming Song, and Albert-László Barabási. "Quantifying long-term scientific impact." Science 342.6154 (2013): 127-132.
[5] Radicchi, Filippo, Santo Fortunato, and Claudio Castellano. "Universality of citation distributions: Toward an objective measure of scientific impact." Proceedings of the National Academy of Sciences 105.45 (2008): 17268-17272.


集智计算社群欢迎你的加入!


我们是集智算法组,为集智俱乐部公众号/集智斑图/集智学园/集智百科等产品提供算法支撑和服务。目前的算法开发范围包括而不限于文本分析、术语和概念挖掘、引文网络分析、科学影响力评价、推荐系统、图神经网络等。我们在集智社群的知识和科技氛围中成长,也将成果反哺于集智社群。如果你是算法爱好者并对上述某个算法分支感兴趣,欢迎加入我们组织的集智计算社群;如果你有其它用科技赋能集智的好点子,期待你的分享。


微信加入集智计算社群请扫码:


实习生简历请投至huqiao@swarma.org



推荐阅读



点击“阅读原文”,加入集智计算社群

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存