近日，我校网络空间安全学院本科生马一心在王伟老师的指导下，与同院本科生薛潇雨，西安交通大学教师蔡萌合作在《中国物理B》(Chinese Physics B) 发表“Shortest path of temporal networks: An information spreading based approach”一文。马一心同学为第一作者，王伟老师为通讯作者。Chinese Physics B是中国权威物理类期刊，2019年SCI影响因子为1.469。

复杂网络可以应用在现实世界的许多系统中，例如网络安全舆情传播与溯源，物流运输等[1]。大量的实证研究表明，现实中很多网络结构是随时间变化的，这些应由时序网络描述更为准确[2]。在网络传播过程中，信息通过节点传播，从而在不同的节点之间形成大量的路径。最短路径是图论和网络科学理论研究的主要问题，且在许多方面可拓展为最高效率问题。随着科技的发展，最短路径问题在计算机科学、网络舆情预测与防控等领域发挥越来越大的作用。

该论文将时序网络中的最短路径分布（Shortest Paths Distribution，SPD）计算过程看作马尔科夫信息传播的方式，提出了一种计算时序网络最短路径的新方法。通过预测马尔科夫信息传播过程，他们计算了四个异质时序网络的SPD。此外，该论文也利用时序网络信息传播的仿真来验证该方法的有效性。

图1在Activity-driven（AD）网络中比较了预测与仿真的结果，红色代表预测信息在网络中的传播结果，蓝色代表进行仿真信息传播后的结果，图1(a)-(c)分别代表参数不同的AD网络。图中的结果证明了该方法可以准确预测信息的传播情况。

图 1 预测与仿真结果在Activity-driven网络上的比较

基于此，作者进一步研究了传播中具有较大影响力的节点。通过对所有节点在α=1的SI（Susceptible-Informed）模型中前期的连边情况以及传播范围的统计与判断，该论文提出了五种不同的策略，并且在图2(a)-(d)四种不同的网络上进行仿真传播，从而对比五种策略初始节点的影响力大小。图中展示了多轮传播后的范围均值和标准差，并且比较传播范围得出最优的策略。

图 2 五种种子选择策略下的信息传播范围随时间变化

该论文所提出的时序网络最短路径分布计算方法，有效地结合了网络结构信息和传播动力学信息，并且提供了一种研究信息传播促进策略的思路。

论文详细信息：Ma Yixin, Xue Xiaoyu, Cai Meng, and Wang Wei, “Shortest path of temporal networks: An information spreading based approach”, Chinese Physics B 29 (12), 128902 (2020).

全文可通过链接http://doi.org/10.1088/1674-1056/abb302获取。

参考文献：

[1] Newman, Mark. Networks. Oxford University Press, 2018.

[2] Holme, Petter, and Jari Saramäki. "Temporal networks." Physics Reports 519.3 (2012): 97-125.