基于反向感染的复合种群网络传播溯源算法

阳成 王建波 许小可 杜占玮

摘 要：流行病的传播会对整个人类社会构成巨大威胁，因此迅速识别传播源并及时采取控制措施至关重要。然而，由于流行病传播过程具有多样性、信息不确定性等因素，使得快速准确识别传播源成为一项挑战。结合反向感染算法、复合种群网络模型以及马尔可夫链理论，提出了一个在复合种群网络中识别传播源的新算法。该算法首先利用马尔可夫链来初步估计子种群被感染的时间，被感染子种群根据感染时间获得自己的身份信息，然后遍历所有获得感染子种群身份信息的子种群，将收集到的感染子种群身份信息传播给其所有邻居，最后根据获得所有感染子种群身份信息的时间顺序推断出复合种群网络的传播源。在真实的航空网和人造复合种群网络上进行大量仿真实验，发现无论在已知全部感染快照还是部分感染快照的情况下，该算法与其他传播溯源算法相比，识别传播源的准确性都有显著提升。该算法非常适合用于航空网这类复合种群网络，对现实世界中的流行病传播溯源和控制也具有参考意义。

关键词：复合种群网络； 传播溯源算法； 反向感染； 计算机仿真

中圖分类号：TP391.9   文献标志码：A

文章编号：1001-3695（2023）09-019-2681-07

doi：10.19734/j.issn.1001-3695.2023.02.0034

RIA-based tracing algorithm for propagation of metapopulation networks

Yang Cheng1， Wang Jianbo1，2， Xu Xiaoke3，4， Du Zhanwei2

（1.School of Computer Science， Southwest Petroleum University， Chengdu 610500， China; 2.School of Public Health， University of Hong Kong，Hong Kong 999077， China; 3.Center for Computational Communication Research， Beijing Normal University， Zhuhai Guangdong 519085， China; 4.School of Journalism & Communication， Beijing Normal University， Beijing 100875， China）

Abstract：The spread of epidemics poses a significant threat to the entire human community. Therefore， it is critical to identify the sources of transmission quickly and take timely control measures. However， the diversity of epidemic transmission processes and information uncertainty makes it challenging to identify the sources of transmission quickly and accurately. This paper proposed a new algorithm for identifying transmission sources in a metapopulation network by combining the reverse infection algorithm and Markov chain theory. The algorithm firstly used a Markov chain to initially estimate the time when a subpopulation was infected， and the infected subpopulation obtained its own identity information based on the infection time. Then， it traversed all subpopulations that obtained the identity information of the infected subpopulation and spreaded the collected identity information of the infected subpopulation to all its neighbors. Finally， the spreading source of the metapopulation network could be inferred based on the temporal order in which all the identity information of the infected subpopulation was obtained. Simulation experiments conducted on real airports networks and artificial networks show that the accuracy of this algorithm is significantly improved compared to other algorithms， regardless of whether all or partial of the infection snapshots are known. This algorithm is well-suited for metapopulation networks such as aviation networks and is also useful for real-world epidemic transmission tracing and control.

Key words：metapopulation network; propagation traceability algorithm; reverse infection algorithm; computer simulation

0 引言

非典型性肺炎［1］ 、甲型H1N1流感［2］、新冠肺炎［3］等呼吸道传染病具有高致死率和传染性，严重威胁人类健康，成为了制约人类社会发展的阻碍之一［4］。在互联网上，电脑病毒［5，6］的存在也给人们带来了许多负面的影响。2003年，出现了一种被称为“2003蠕虫王病毒”的病毒，当电脑感染该蠕虫病毒后，网络带宽被大量占用，导致网络瘫痪。这种病毒在亚洲、美洲、澳大利亚等地迅速传播，造成了全球性的网络灾害。2006年，一种被称为“熊猫烧香”的病毒在互联网上传播，上百万的用户受到影响。同时，随着人们交流的便捷，谣言［7～9］也很容易流行开来，影响了人们的生活。传播溯源［10，11］旨在基于感染快照、感染者流動信息等来识别传播源头的节点（例如，电脑病毒、谣言和流行病的传播［12］），被广泛地应用在流行病源头推测、互联网病毒源识别、社交网络中的谣言源追踪等方面。

传播溯源问题包括流行病在人群和个体网络中的时空传播溯源，计算机网络上的病毒溯源，以及社交网络上的谣言溯源。对于传播溯源问题的研究挑战主要来自以下几个方面：

a）网络结构复杂多样。从小世界网络［13］、无标度网络［14，15］再到多层网络［16，17］、高阶网络［18，19］，流行病或信息传播的载体越来越复杂。在多尺度视角下，单个个体作为节点组成的接触网络可以传播流行病；多个个体组成的城市作为节点组成的航空网也可以传播流行病。网络结构的复杂性，使得传播溯源往往需要对不同类型的网络设计不同的识别算法。

b）流行病类型多样。在流行病传播过程中，个体可以处于最常见的四个状态，即易感态（susceptible，记为S）、潜伏态（exposed，记为E）、感染态（infected，记为I）以及恢复态（re-covered，记为R）。生活中多种流行病可以用其组合的传播模型描述，例如：易感—感染（susceptible-infected，SI）、易感—感染—易感（susceptible-infected-susceptible，SIS）［20］、易感—感染—恢复（susceptible-infected-recovered，SIR）、易感—潜伏—感染—恢复（susceptible-exposed-infected-recovered，SEIR）等模型。

c）已知信息不确定。在流行病传播过程中，经过时间t，得到了包含每个节点的感染状态的快照。这里的传播时间t在某些情况下为已知量［21，22］，有时候，传播时间t也是未知量［23～25］；同时，感染快照中的状态信息有时候包含了所有的节点［26］，有时候只覆盖了部分节点［27～29］。

面对如此情况，国内外学者提出了各种方法来克服这些挑战。2010年，Shah等人［30］针对正则树上的 SI 传播模型提出一个谣言中心性（rumor centrality）指标，并据此提出了第一个解决溯源问题的算法。在该算法中，会构建一个正则树，某个节点是传播源的概率，与流行病从该节点出发感染其他节点的所有可能顺序的计数成正比。因此，依据文献［30］定义的传播中心性，得分最大的节点作为传染源的估计。2016年，Zhu等人［31］提出，依据流行病传播路径和传播源头的关系，用最可能的传播路径对应的源点来推断传播源。文献［31］借鉴文献［32］中离心率（eccentricity）的思想，定义感染离心率（infection eccentricity）为到所有被感染节点距离的最大值，并类比于Jordan中心（Jordan center）的概念，定义Jordan感染中心（Jordan infection center）作为感染离心率最小的节点，并将之称为反向感染算法（reverse infection algorithm）。Antulov-Fantulin等人［33］考虑在已知传播过程中T时刻所有节点的状态的情况下，提出了基于蒙特卡罗模拟的定位算法。算法非常容易理解，即通过直接模拟流行病传播的方法来估计传播源。对每个可能的传播源，重复做多次独立的、传播时间为T的蒙特卡罗模拟传播，然后通过计算T时刻所有节点状态来估计传播源。2017年，Xu等人［34］通过贝叶斯估计法提出了一种算法，在具有稀疏观察者的复杂网络中定位流行病源并找到初始时间。2019年，Xu等人［35］基于网络中有限的观察者，利用了网络结构和扩散动力学之间的相关性，提出了一种算法，用以识别推断传播源。2021年，Das等人［36］结合多种中心性算法，提出了一种组合网络中心性方法（CNCA）来推测传播源。

然而，现有方法可能在某一类溯源检测上具备一定的准确性，但如果扩展到其他的网络上时，会出现准确率的下降。比如，谣言中心性算法［30］能够在多种网络上取得一定的效果，但其准确率却没有特别高；反向感染算法［31］为了最小化源头到其他节点的最大距离而忽略了流行病传播的动态性；蒙特卡罗模拟的算法［33］需要了解传播时间。基于上述分析，本文提出了新算法，该算法首先利用马尔可夫链来初步估计子种群被感染的时间，然后所有感染子种群基于感染时间将自己的身份信息传播给其所有邻居，最先获得所有感染子种群身份信息的子种群推断为传播源。通过在多个网络上的实验以及多个方法的对比，本文算法的准确率较高，并且在不完全快照的情况下也能够识别部分传播源。本文的创新性主要有三点：a）基于反向感染算法，结合复合种群网络模型以及马尔可夫链理论，提出了一个在复合种群网络中识别传播源的新算法；b）利用马尔可夫链说明了子种群感染时间与感染人口状态转移的正相关性，并给出了Pearson相关系数和Spearman系数的实验结果；c）在真实航空网上验证了本文算法的正确性，证明了本文算法在全部快照和部分快照的情况下，都具有推断传播源的优良性能。

1 复合种群网络上的流行病传播溯源问题

1.1 复合种群网络

在现实生活中，个体处于诸如社区和城市这样的社会单位中。在复合种群网络模型中，对于社区和城市这样的社会单位，定义为子种群，不同的子种群通过交通路线的相互连接，从而形成人口流动。流行病的传播依赖于人与人之间的接触，在子种群内部，通过感染态个体与其他个体的接触，使得流行病在子种群内部进行传播；通过子种群之间的人口流动，使得流行病在不同的子种群之间扩散。

对于复合种群网络，考虑使用一个有向图G={V，E，W}来表示，其中V是节点的集合，表示复合种群网络中的子种群，E是边的集合，表示不同子种群之间的联系，W是节点与节点之间迁移率的集合。每一个节点可以是一个社区、城市、甚至国家。每一个节点内部有多个个体，各个个体之间能够进行随机接触，并发生相互反应（按SIR模型等）。在复合种群网络中，对于不同的子种群，如果子种群i、j之间存在连边eij∈E， 那么两个种群i、j之间的人口就能够依据迁移率wij∈W进行流动，否则不能进行人口流动。在每一个子种群内部，不同个体之间能够随机接触。图1给出了复合种群网络的示意图，不同的节点表示不同的子种群，当两个子种群之间存在连边时，它们的人口能够进行流动。在子种群内部，不同的个体之间是能够自由移动并相互接触。

1.2 流行病传播的SIR模型

在流行病模型中，每个个体可以处于最常见的四个状态：易感（S）、潜伏（暴露）（E）、感染（I）和恢复（R）。在本文中，使用SIR模型。最初，除了传播源子种群v*中的部分个体处于感染态，其他所有的个体都处于易感态。本文设置一个时间间隔（时间步），子种群内的每个个体在每个时间步开始时改变它们的状态。在每个时间步的开始，每个感染态个体以感染率β感染它的易感态邻居，使得易感态个体的状态能够转换为感染态；每个感染态个体以恢复率γ恢复至恢复态。由于易感态个体与恢复态个体均未表现出症状，所以这两个状态的个体在观测时是不能区分的。个体a在时间t时刻的状态用Pa（t）表示，它的取值如下：

Pa（t）=1  t时刻a个体处于感染态0  t时刻a个体处于易感态或恢复态（1）

在SIR模型中，将s（i，r）表示种群内的易感态（感染态，恢复态）的个体的比例。一个种群内，SIR模型中的状态转移方程可以由以下微分方程组表示：

dsdt=-βsi  didt=βsi-γi  dsdt=γi（2）

上述方程中忽略了网络结构，这些微分方程可以用于个体自由移动的网络的状态粗略近似。在复合种群网络模型中，在一个种群内，例如在子种群i，设置所有个体均可以自由移动并随机接触，使用Si（Ii，Ri）表示其易感态（感染态，恢复态）的人口数，那么对于子种群i，可以使用方程式（3）来表示种群内部人口状态的转移。同时，在SIR模型中，对于不同状态的人口，还具备以下性质：易感态个体可能被他/她的受感染的邻居感染，感染态个体可能恢复，并且恢复的个体不能被再次感染。

dSidt=-βSiIiNi  dIidt=βSiIiNi-γIi  dRidt=γIi（3）

对于被感染的子種群c∈V，当其中的传播源个体1被感染时，发生的流行病传播过程可以用图2表示。

在图2中，图（a）是不同个体之间的流行病传播示意图，个体1是传播源。个体1在t=0时刻被感染，并分别在t=1和t=2时刻感染个体2和3。在t=3时刻获取快照时，获得的快照如图（b）所示。对于子种群c，在时间t中的快照信息表示为Xc（t）={Pi（t）}。在t=3时刻，能够知道个体1～7是否处于感染态，本文将这个信息定义为Xc（3）。由于方程式（1），将无法区分恢复态的个体和易感态的个体，所以此时拥有的信息是

Xc（3）={0，1，0，0，1，1，1}

即某一个子种群c的快照用数学表示为

Xc（t）={Pi = 1， i∈VIc，Pj=0，j∈Vc＼VIc}（4）

其中：VIc表示子种群c内的所有感染个体的集合；Vc表示子种群c内所有个体的集合。上式表示在t时刻获得的子种群c内部的快照信息，其中，处于感染态的个体使用1表示，处于易感态或恢复态的个体用0表示。

1.3 传播溯源问题描述

在流行病的传播中，由于子种群v∈V内部的易感态个体和恢复态个体是不可区分的，所以也不能区分易感态的个体（子种群）和恢复态的个体（子种群）。所以，在时间t获取的快照为Y（t）={Yv（t），v∈V}，其中：

Yv=1  如果Xv（t）不全为00  如果Xv（t）全为0（5）

即当某个子种群内所有个体处于易感态或恢复态时，对应子种群的信息为0，其余情况取1。复合种群网络传播源检测问题是在给定复合种群网络图G和感染快照Y的情况下识别v*，其中t是未知参数。表1列出了所有符号的描述。

2 基于样本路径的传播溯源

在流行病传播中，传播源经常处于感染快照的中心。反向感染算法［31］是寻找感染快照的Jordan感染中心。在该算法中，首先定义网络中两个体i、 j的距离为d（i，j），其物理意义为两个节点之间最短距离，数值上的取值为最短距离的值。依据图论中的偏心率的定义，顶点v的偏心率e（v）是v和图中任何其他顶点之间的最大距离。图的Jordan中心是具有最小离心率的节点。按照类似的术语，定义感染偏心率e（v）：给定感染快照Y和网络图G，节点v与所有感染节点距离的最大值作为感染偏心率。同样地，定义图的Jordan感染中心为具有最小感染偏心率的节点。d（v1，v2）是v1与v2之间的距离，例如，在图3中，d（v1，v2）=1。感染网络的感染偏心率e（i）是某个节点i与其他所有感染态节点j∈VI之间的距离的最大值。也就是说，感染偏心率e（v）表示节点v与其他感染节点的最大距离，即e（v）=arg maxj∈VId（v，j）。在反向感染算法中，推断源是图的Jordan感染中心，即具有最小感染偏心率e（v）的节点：

v=argminv∈V e（v）=argminv∈V argmaxj∈VI d（v，j）（6）

在图3中，节点v3、v6、v8和v9被感染。v1、v2、v3、v4的感染偏心率分别为2、3、4、3，Jordan感染中心为v1。该方法依据感染快照的路径，Zhu等人［31］命名为最佳样本路径推测，其对应的算法称之为反向感染算法（reverse infection algorithm，RIA），对应的传播源是具有最小感染偏心率的节点。

3 基于反向感染的复合种群网络传播溯源

反向感染算法在一般网络特别是树型网络上的误差较小，该算法认为网络中的每一个节点代表一个个体，它们的权重相同。然而，随着交通越来越便利，流行病往往会很快传播到大尺度的空间范围，不同个体之间的连接关系（连边）也常常会发生变化。因此，现实中的网络结构需要适应性地调整，流行病传播溯源常在复合种群网络（即一个节点代表一个城市/社区）上进行考虑。在复合种群网络中，直接使用反向感染算法常常会出现误差，因为在复合种群网络中，不同的节点代表着不同的子种群而不是某一个个体，所以不同的子种群的感染状态并不完全相同，即很少出现不同的子种群之间处于感染态的人数、处于感染态人数的比例等信息完全一致，所以不同的感染子种群之间的权重应当不同。针对上述反向感染算法对复合种群网络中的流行病传播溯源的不完全适应问题，结合复合种群网络，提出了本文算法，可以解决复合种群网络中的流行病溯源问题。在复合种群网络中，不同子种群的权重应当与该子种群内部感染状态有关。首先，先分析不同子种群的人口状态转移方程。在复合种群网络的 SIR 模型中，对子种群i而言，其感染态人口的变化按照下述方程进行变化：

dIdt=βSiIiNi-γIj+∑j∈N（i）wjiIj-∑j∈N（i）wijIi

dIdt=∑Sk=0（βIiNi）k（1-βIiNi）1-k+∑j∈N（i）∑Ijn=1n！∏nm=1wmjiNjm！-∑j∈N（i）∑Iin=1n！∏nm=1wmijNim！（7）

其中：S、I、N 分别代表易感态人口数、感染态人口数、总人数。对于子种群i而言，人口状态的转移包括自身人口状态转移以及人口的迁移。其中对于其所有邻居的迁移对它的影响可以表示为

P=Ni∑j∈N（i）wij-∑j∈N（i）Niwji（8）

而两邻居种群i、 j之间的迁移人数为

Qij=NiwijQji=NjwjiQij=Qji（9）

根据人口流动分析，两城市之间的人口变化很小，所以式（8）约为0，即P≈0，即忽略人口的迁移现象。此时，不同时刻的人口状态与上一个时刻相关，人口状态转移方程用马尔可夫链表示为

Si（t+1）=Si（t）-βSi（t）Ii（t）Ni（t）Ii（t+1）=Ii（t）+βSi（t）Ii（t）Ni（t）-γIi（t）Ri（t+1）=Ri（t）+γIi（t）（10）

通过式（10）可以看到，对于某一个子种群而言，所处的时间不同，其内部不同状态的人口规模不同。忽略迁移影响较小的人口变化，可以依据式（10）来初步估计不同子种群的感染时间tv，来估计复合种群网络模型下不同子种群的权重。

对于相邻的子种群，如果在t时刻i种群被感染，t+1时刻其邻居种群j被感染，显然，他们的感染时间差与距离差相同，即dt（vi，vj）=d（vi，vj）=tvi-tvj=1。如果在t时刻i种群被感染，t+m（m＞1）时刻其邻居种群j被感染，显然，他们的感染时间差大于1，即tvi-tvj＞1，那么两者之间的感染时间差表示为dt（vi，vj）=tvi-tvj＞d（vi，vj）=1。如果在t时刻i子种群被感染，t+m（m≥1）时刻其邻居子种群j被感染，t+n（n≥1）时刻其邻居子种群k被感染，显然，此时dt（vi，vj）≥1，dt（vi，vk）≥1，但另外两个不相邻的子种群j与k之间的距离可能会大于时间之差，即tvj-tvk＜2，d（vj，vk）≥2，而在传播过程中，显然由子种群j传播流行病信息至子种群k的时间不会小于距离，即连个不相邻的子种群j与k的感染时间差表示为dt（vi，vj）=max（d（vi，vj），tvj-tvk）。统一表示，两个不同的子种群i、 j之间的时间差为

dt（vi，vj）=max（d（vi，vj），tvi-tvj）（11）

所以，在复合种群网络中，子种群i的感染偏心率表示为dt（vi）=argmin（max（dt（vi，vj）））。那么，推断的传播源可以表示为

v=argminvi∈V，vj∈VI（max（dt（vi，vj）））=argminvi∈V dt（vi）（12）

依据上述思想，本文得到了算法1（reverse infection-based-detection source-algorithm，RIDSA）。算法1的时间复杂度为VI+c×dI×VI，空间复杂度为VI+V×VI，其中，VI是被感染子种群的数量，V是所有子种群的数量，c是复合种群网络G的平均度，dI是感染快照Y的直径。在本算法中，首先需要估算被感染个体的马尔可夫链时间，此時，时间复杂度为VI；其次，在传播溯源阶段，被感染子种群的信息需要传递给其邻居，耗时c×VI，在推断出传播源时，信息已传遍整个网络，耗时c×VI×dI，总时间复杂度为VI+c×dI×VI。在传播溯源过程中，本算法需要保存的信息为感染时间矩阵，占空间VI，还需要为每一个子种群储存接收到的感染信息，占空间V×VI，总空间复杂度为VI+V×VI。

算法1 基于反向感染的复合种群网络传播溯源算法（RIDSA）

输入：感染快照Y；传播网络G。

输出：推断的传播源v。

1 for v∈Y do

2  通过方程式（10）计算马尔可夫链估计的时间MTv

3  添加估计的时间到矩阵MT（v，MTv）

4 根据MTV对时间矩阵MT进行排序

5 初始化时间t

6 while true do

7  for v∈Y do

8   if 子种群 v not in G

9    if 子种群v估计的感染时间MTv≥t do

10     添加子种群v到G

11  else

12   反向感染子种群v的邻居

13   for vi∈N（v） do

14     将子种群v添加到子种群vi的信息集合Infvi

15  t=t+1

16  if Infv=Y do

17   推断的传播源v=v并退出循环

18  else

19   重复 7～19行

20 返回推断的传播源v

4 计算机仿真验证

本章评估了本文算法在不同网络上的性能，包括人造网络和真实世界网络。

4.1 基于复合种群网络的蒙特卡罗模拟随机流行病过程方法

在模拟流行病的传播中，本研究采用蒙特卡罗方法来进行实验。考虑到实验的偶然性偏差，本文在不同的传播网络中筛选出人口和度数不同的子种群设计传播实验，每一个子种群进行10次的传播模拟，使用得到的实验数据进行传播溯源。

本仿真的模拟过程主要包括种群内部的传播以及不同种群之间的扩散两个方面。

a）传播过程，即子种群内部的感染过程。在每一个子种群内部，易感态个体、感染态个体和恢复态个体是均匀混合的，每一个个体都有几率接触到其他个体。在一个时间步上，根据SIR传播模型，人数的变化的期望值是一个确定的值，但考虑到现实生活中的随机变化，本文采用二项分布来模拟人数变化的随机性。需要注意的是，人数变化的期望值应当是SIR模型下的人数变化值，即本文采用的模拟过程使得人数在期望值附近波动。

b）扩散过程，即子种群之间的人口迁移，相当于现实生活中的人员流动。每座城市或者社区之间，会存在一定的人员流动，且每一个时间步流动的人口数量可能会有所不同。此处，本文采用多项分布进行模拟，对每一种人口均设置流动性，而子种群的总的流动人数的期望符合本文给定的迁移率。此处需要注意的是，每个子种群的人数不同，迁移率也不同。

4.2 马尔可夫链下的传播时间相关性分析

为了验证方程式（10）对感染时间先后顺序的估计，本文设计了在六个不同的人造网络（artificial network，AN）上进行模拟实验，网络信息如表2所示。

在现实生活中，不同子种群之间的感染率与恢复率会受到气温、医疗等影响而不同，因此本实验通过设计不同感染率与恢复率来模拟流行病在不同地区的传播情况。在不同的人造网络中，从感染开始时，记录不同网络每天的感染状况与真实时间，根据真实的传播时间与通过方程式（10）得到的马尔可夫链下估计的时间的数组，通过方程式（13）来计算Pearson相关系数和Spearman系数，分析不同感染率与恢复率下的相关性，实验结果如图4所示。

r=N∑xi×yi-∑xi∑yiN∑x2i-（∑xi）2×N∑y2i-（∑yi）2r=∑i （xi-）（yi-）∑i （xi-）2∑i （yi-）2（13）

通过图4可以看到，SIR模型下，当感染率与恢复率发生变化时，真实传播时间与估计时间的相关性得分很高，均在0.80以上。可以说明，通过马尔可夫链估计时间能够代表不同子种群感染的先后顺序。

4.3 真实航空网上和人造网络完整快照的传播溯源结果

本节使用真实航空数据构建的美国航空网络（American airlines network，AAN）和四种常用的人造网络（规则网络RG、ER网络、WS网络和BA网络）进行传播过程仿真。美国航空网络中，知道网络拓扑，包括子人口规模和旅行人数和旅客的城市人口。人造网络中，本文依据美国航空网络中的迁移率分布等信息，参考文献［37］构造出了对应的人造网络。对于传播源子种群的筛选，本实验中选择了低于平均度的子种群占40%，高于平均度的子种群占60%；同时，低于人口平均数和高于人口平均数的子种群均约占50%。考虑到不同算法是溯源条件不同，选择与本文算法与溯源条件相同的算法如谣言中心性算法［30］、RIA算法［31］、STC算法［35］、CNCA算法［36］、有效距离溯源［38］、K-center算法［39］进行比较，通过不同算法的实验结果来分析本文算法的准确率。

在复合种群网络中，设置感染概率β=0.3、恢复概率γ=0.2进行流行病的传播仿真。持续时间t是依据传播范围进行选择的整数。对于整个复合种群网络，通过对感染规模的估计，当所有子种群均出现感染者时，停止感染仿真，并获取这个时候的快照。依据此时的快照数据，对不同算法的溯源准确率和误差距离进行统计，得到的实验结果如下。

为了直观地表示本文算法的准确率，给出了图5和6的实验图。

在图5（a）、图6（a）中，本文算法的准确率在80%以上，具备较高的准确率；而其他对比算法的准确率较低。常用的统计方式还有溯源误差距离，本文统计了真实传播源头和推断源头之间的距离，实验结果如图5（b）、图6（b）所示。在图5（b）、图6（b）中，本文算法的誤差距离在0.2跳以下，即真实的传播源与推断的传播源之间的平均差距为0.2。STC算法利用了感染时间与路径的相关性，误差距离在0.7～0.9。而原始的反向感染算法、谣言中心性算法、K-center算法、有效距离的溯源算法的误差距离在1.0～1.6，误差大于本文算法。在复合种群网络上的实验结果表明，本文算法能够减小溯源误差距离。同时，考虑到同一个子种群在网络的位置相同，那么它的溯源结果很有可能具有收敛的性质，本文统计了相同子种群的实验结果，发现90%左右的子种群在多次模拟中的结果收敛，10%左右的子种群实验结果不收敛。通过分析发现，这些子种群的度值远大于平均度，从而在本实验中偶然性的影响下导致了实验结果不收敛。

在准确率的测试中，本文算法取得了更好的准确率。分析主要原因如下：本文算法考虑了子种群内部的感染信息与未感染子种群的信息；其次，STC算法的表现优于其他的算法，是因为其考虑了节点感染先后顺序和有效距离路径的相关性；再次，其他算法几乎只从传播路径的角度分析了传播源，而没有考虑复合种群网络上流行病传播的更多信息，比如节点感染时间与节点感染先后顺序。RC、RIA会考虑了感染节点与传播路径的关系；CNCA虽然考虑了多种中心性算法，但这些中心性算法之间本身就存在一定的耦合性；ED、K-center提出了设置有效距离的方法，但是对子种群本身的感染状态等信息未加以利用。从结果上来看，本文算法可以利用复合种群网络上的更多信息，从而能更准确地推断真正的传播源。当复合种群网络的信息减少，比如，当所有的子种群的人数进行坍缩至1人时，复合种群网络退化为普通的传播网络，此时，本文算法也会坍缩至RIA算法，从而会使实验准确率下降。值得一提的是，当将复合种群网络看做普通网络时，其余算法的传播溯源的结果仍能够保持一定的准确率，而当复合种群网络快照进行减小时，本文算法的准确率也会下降。复合种群网络上的实验结果表明，本文算法能够提高溯源准确率。接着，本文统计了不同算法在不同误差距离的分布情况，得到的结果如图7和8所示。

可以看到，本文算法90%以上的误差为0，即找到了传播源头，而未找到传播源头时，误差也在1跳内。STC算法的误差距离在0～2，也具备较高的准确率。而其他算法的误差距离多在1～2，误差大于本文算法。RC、RIA、CNCA算法利用感染节点在感染快照中的位置来进行传播溯源，却没有考虑到复合种群网络中，不同节点之间的距离与节点之间的迁移率存在关系；ED、K-center算法通过设置有效距离来进行传播溯源，考虑了迁移率的因素；STC算法使用节点感染顺序与有效距离之间的关系来进行传播溯源，准确率高于其他的算法；本文算法考虑了复合种群网络中的子种群内部的信息，结合子种群在感染快照中的位置来进行传播溯源，相较于其他算法，结果有明显的提升。在复合种群网络中，不同的子种群内部感染人数和感染比例不同，那么处于子种群被感染的时间越久，那么该子种群是感染源的概率越大；该子种群所占的权重也应当越大。这是复合种群网络的特性，也是现实生活中个体的现实属性，是如今的传播溯源算法需要考虑的问题。

4.4 真实航空网上部分快照的传播溯源结果

对于信息获取不完全的情况，通过随机减少快照的比例来进行实验。假设获取快照的比例为20%、30%、50%、70%、100%时，本文算法的准确率和误差距离的实验结果如图9所示。

在图9中，可以看到，当能够获取20%的感染快照时，本文算法已经能够达到20%左右的溯源准确率，且误差距离在1.0附近。在不同的复合种群网络中，当快照规模达到50%时，本文算法溯源准确率已经达到50%；当获取完整快照时，几乎已经能够准确找到所有感染源头。图9（a）（b）显示了本文算法在获取不同快照信息时的准确率和误差距离。随着获取信息的增加，准确率在逐渐增加，误差距离在逐渐减小。在不要求更高的准确率时，部分快照的信息已经能够用来溯源；如果要求更高的准确率，本文算法需要更准确的快照。在不同的流行病的感染率、恢复率可能会不同。为了验证本文算法的鲁棒性，本节在美国航空网络（AAN）设置不同的感染率、恢复率进行流行病传播仿真，使用仿真结果进行溯源实验，得到的结果如图10所示。

图10（a）（b）分别表示在AAN中的不同感染率、恢复的溯源结果。可以发现，不论是在固定感染率并设置不同的恢复率，还是固定恢复率并设置不同的感染率的实验中，本文算法的准确率均在80%以上，准确率的分布相近。本文算法在不同的流行病参数下均表现出较高的准确率，表明其具有良好的扩展性。

4.5 2022年上海市新冠疫情的传播溯源结果

2020年3月份左右，上海市爆发了新冠疫情。本节收集了上海市16个区的感染数据。依据2022年4月5日至8日的数据，使用重力模型［40］进行来模拟人口流动，当人口变化保持稳定时，构造出的上海市的网络如图11所示。使用本文算法进行传播溯源。不同区的得分如图12所示。

在图12中可以看到，从2022年4月5日至8日，浦东区的得分均为最高，从而推断浦东区为传播源头。

5 结束语

本文研究了流行病在復合种群网络中的传播，通过分析不同子种群的感染规模及状态来进行传播源检测的问题。结合RIA算法以及流行病在复合种群网络上的传播特性，本文考虑了复合种群网络与普通网络的区别、流行病传播的马尔可夫链、时间变化等因素，提出了一种适合复合种群网络的传播溯源算法。在几个不同的网络上评估了本文算法的性能。仿真结果表明，该算法在传播源检测问题上表现良好。同时，当实验只能获取部分快照时，本文算法也表现出了良好的准确率。本文算法考虑了子种群内部的感染信息与未感染子种群的信息，以及考虑了感染快照的路径信息。其次，STC算法的表现优于其他的算法，是因为其考虑了节点感染先后顺序和有效距离路径的相关性。再次，其他算法几乎只从传播路径的角度分析了传播源，而没有考虑复合种群网络上流行病传播的更多信息，比如节点感染时间与节点感染先后顺序。值得注意的是，其他算法几乎没有依赖于网络的特殊性，所以这些方法在许多网络上均具备一定的鲁棒性，而本文算法则更加依赖复合种群网络上的快照的实验数据，这将直接与本文算法的准确率相关联。作为进一步的研究，有三个方向值得探索。a）通过真实传播时间与马尔可夫链下估计的时间的相关性分析，本文发现在复合种群网络模型中，给定感染率与恢复率，流行病的传播先后顺序能够进行估计。如果能够准确地估计不同子种群的传播时间，或许能够更加准确地识别传播源。b）到目前为止，本文已经得出了SIR模型下的单一信息源的方法，将它扩展到其他模型下的多信息源检测，对它们进行扩展是很有意义的。c）当快照足够完整时，如果能够准确估计传播时间，那么新的方法或许能够不依赖于传播路径，即能够在时变网络等模型下进行传播溯源。

参考文献：

［1］Bell D M. Public health interventions and SARS spread， 2003［J］. Emerging Infectious Diseases， 2004，10（11）： 1900-1906.

［2］Neumann G， Noda T， Kawaoka Y. Emergence and pandemic potential of swine-origin H1N1 influenza virus［J］. Nature， 2009，459（7249）： 931-939.

［3］Wu Fan， Zhao Su， Yu Bin， et al. A new coronavirus associated with human respiratory disease in China［J］. Nature， 2020， 579（7798）： 265-269.

［4］李翔， 李聰， 王建波， 复杂网络传播理论——流行的隐秩序［M］. 北京： 高等教育出版社， 2020：10. （Li Xiang， Li Cong， Wang Jianbo. Theory of spreading on complex networks： hidden rules of epidemics ［M］. Beijing： Higher Education Press， 2020： 10.）

［5］Shah D， Zaman T. Detecting sources of computer viruses in networks： theory and experiment［C］//Proc of ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems. New York： ACM Press， 2010： 203-214.

［6］Wang Pu， González M C， Hidalgo C A， et al. Understanding the spreading patterns of mobile phone viruses［J］. Science， 2009，324（5930）： 1071-1076.

［7］Bellet A， Guerraoui R， Hendrikx H. Who started this rumor？ Quantifying the natural differential privacy of gossip protocols［C］//Proc of the 34th International Symposium on Distributed Computing. ［S.l.］： Schloss Dagstuhl-Leibniz-Zentrum für Informatik， 2020： 8：1-8：18.

［8］Grinberg N， Joseph K， Friedland L， et al. Fake news on Twitter du-ring the 2016 U.S. presidential election［J］. Science， 2019，363（6425）： 374-378.

［9］Cator E， Van M P. Second-order mean-field susceptible-infected-susceptible epidemic threshold［J］. Physical Review E， 2012，85（5）： 056111.

［10］Jiang Jiaojiao，Wen Shui，Yu Shui，et al. Identifying propagation sources in networks：state-of-the-art and comparative studies［J］. IEEE Communications Surveys & Tutorials， 2017，19（1）：465-481.

［11］Waniek M， Holme P， Farrahi K， et al. Trading contact tracing efficiency for finding patient zero［J］. Scientific Reports， 2022，12（1）： 22582.

［12］陈钰书， 刘影， 唐明. 具有非马尔可夫旅途感染的流行病传播模型研究［J］. 计算机应用研究， 2023，40（6）： 1739-1749. （Chen Yushu， Liu Ying， Tang Ming. Study on epidemic transmission model with non-Markovian journey infection［J］. Application Research of Computers， 2023，40（6）： 1739-1749.）

［13］Barabási A L， Albert R. Emergence of scaling in random networks［J］. Science， 1999，286（5439）： 509-512.

［14］Pastor-Satorras R， Vespignani A. Epidemic spreading in scale-free networks［J］. Physical Review Letters， 2001，86（14）： 3200-3203.

［15］Newman M E J. The structure and function of complex networks［J］. SIAM Review， 2003，45（2）： 167-256.

［16］Belyi A， Bojic I， Sobolevsky S， et al. Global multi-layer network of human mobility［J］. International Journal of Geographical Information Science， 2017，31（7）： 1381-1402.

［17］沈力峰， 王建波， 杜占玮， 等. 基于社团结构和活跃性驱动的双层网络传播动力学研究［J］. 物理学报， 2023，72（6）： 356-364. （Shen Lifeng， Wang Jianbo， Du Zhanwei， et al. A study on propagation dynamics of two-layer networks based on association structure and activeness drive［J］. Acta Physica Sinica， 2023，72（6）： 356-364.）

［18］Sartori F， Turchetto M， Bellingeri M， et al. A comparison of node vaccination strategies to halt SIR epidemic spreading in real-world complex networks［J］. Scientific Reports， 2022，12（1）： 21355.

［19］Armbruster A， Holzer M， Roselli N， et al. Epidemic spreading on complex networks as front propagation into an unstable state［J］. Bulletin of Mathematical Biology， 2022，85（1）： 4.

［20］周海平， 賴兵兵， 刘妮. 一类考虑病毒发生变异的SIS疾病传播模型［J］. 计算机应用研究， 2014，31（9）： 2773-2775. （Zhou Haiping， Lai Bingbing， Liu Ni. A class of SIS disease transmission models considering virus occurrence mutation［J］.Application Research of Computers， 2014，31（9）： 2773-2775.）

［21］Pinto P C， Thiran P， Vetterli M. Locating the source of diffusion in large-scale networks［J］. Physical Review Letters， 2012，109（6）： 068702.

［22］Lokhov A Y， Mézard M， Ohta H， et al. Inferring the origin of an epidemic with a dynamic message-passing algorithm［J］. Physical Review E， 2014，90（1）： 012801.

［23］Luo Wuqiong， Tay W P， Leng Mei. Identifying infection sources and regions in large networks［J］. IEEE Trans on Signal Processing， 2013，61（11）： 2850-2865.

［24］Luo Wuqiong， Tay W P. Identifying multiple infection sources in a network［C］//Proc of Conference Record of the 46th Asilomar Confe-rence on Signals， Systems and Computers. Piscataway， NJ： IEEE Press， 2012： 1483-1489.

［25］Luo Wuqiong， Tay W P， Leng Mei. Identifying infection sources and regions in large networks［J］. IEEE Trans on Signal Processing， 2013， 61（11）： 2850-2865.

［26］Dong Wenxiang， Zhang Wenyi， Tan C W. Rooting out the rumor culprit from suspects［C］//Proc of IEEE International Symposium on Information Theory. Piscataway， NJ： IEEE Press， 2013： 2671-2675.

［27］Karamchandani N， Franceschetti M. Rumor source detection under pro-babilistic sampling［C］//Proc of IEEE International Symposium on Information Theory. Piscataway， NJ： IEEE Press， 2013： 2184-2188.

［28］Louni A， Subbalakshmi K P. A two-stage algorithm to estimate the source of information diffusion in social media networks［C］//Proc of IEEE Conference on Computer Communications Workshops. Pisca-taway， NJ： IEEE Press， 2014： 329-333.

［29］Luo Wuqiong， Tay W P， Leng Mei. How to identify an infection source with limited observations［J］. IEEE Journal of Selected Topics in Signal Processing， 2014，8（4）： 586-597.

［30］Shah D， Zaman T. Rumors in a network： whos the culprit？［J］. IEEE Trans on Information Theory， 2011，57（8）： 5163-5181.

［31］Zhu Kai， Ying Lei. Information source detection in the SIR model： a sample-path-based approach［J］. IEEE/ACM Trans on Networking， 2016，24（1）： 408-421.（下转第2693页）

收稿日期：2023-02-07；修回日期：2023-04-06  基金项目：国家自然科学基金面上项目（62173065）

作者简介：阳成（1996-），男，四川绵阳人，硕士，主要研究方向为复杂网络、网络传播动力学；王建波（1980-），男（通信作者），四川成都人，讲师，硕导，博士，主要研究方向为复杂网络、网络传播动力学（phyjbw@gmail.com）；许小可（1979-），男，辽宁人，教授，博导，博士，主要研究方向为社交网络大数据、数据可视化、计算传播学；杜占玮（1988-），男，河北人，副研究员/研究助理教授，博导，博士，主要研究方向为计算流行病学、机器学习、数据科学.