社会和信息网络:基于图表的SIS流行病敏感性分析*

• 2019 年 12 月 30 日
• 筆記

原文题目： Graphon-based sensitivity analysis of SIS epidemics*

摘要:

在这项工作中，我们利用石墨的光谱特性来研究大网络上确定性SIS流行病的稳定性和鲁棒性。摘要研究了在有限秩的分段李普希茨图上随机采样的确定性SIS模型中附加噪声的存在性。我们推导出一个噪声指数来评估由于噪声而偏离无病状态的程度。对于有限图，索引依赖于图的邻接特征值。利用相关的图形算符的特征值，我们可以找到当网络规模趋近于无穷时的紧度指标的近似值。最后以一个数值例子来说明结果。

一、介绍

近年来,注意分析的工作增加了在科学界由于连续进化的世界走向网络化环境中,更多的连接是建立在每一个瞬间,从而生成网络与大量的组件,我们将称之为大型网络。传统上，研究人员使用图论的概念来分析网络，而网络图的完整知识是大多数应用所必需的。这种假设对于具有相对较少的代理的系统是合理的，但是对于大型网络，就会出现严重的问题。首先，由于数据中存在噪声和错误，以及链路和节点的不断演化，可能无法获得完整和更新的网络表示。其次，即使可以获得良好的网络拓扑知识，由于计算资源的限制，它们的庞大规模也会妨碍对动态的完整模拟或分析，或相关网络属性的计算。

最有希望解决这些问题的工具之一是图函数，也称为图元，它是稠密图[1]、[2]、[3]、[4]序列的极限。研究人员已经开发了许多图形在网络结构分析中的应用，包括中心测度[4]的近似和链接预测问题[5]。最近，研究人员也开始使用图形来研究大型网络的动态:感兴趣的问题包括建模电力网络动态[6]和流行病[7]，开发控制方法[8]，[9]，[10]，和研究大型群体博弈[11]，[12]。在这封信中，我们重点讨论了确定性易感-感染-易感(SIS)流行病模型，该模型描述了一种可以感染病原的疾病，而不管它们是否在早期被感染。该模型通常被解释为一个元种群模型，其中每个节点的状态是一个亚种群[13]、[14]、[15]、[16]中被感染个体的比例。即使流行病学的分析和控制是很好的研究课题，理论结果的适用性也常常受到一些限制性假设的限制，这些假设要求对节点的动态规律、节点的状态以及网络[17]、[18]的结构有完整的认识。网络知识的不确定性一直是均值场模型[19]、[15]研究传染病的动机之一。在本文中，我们采用了一种不同的方法，通过将网络建模为一个图形来考虑不确定性。在流行病模型[20]、[21]、[22]中，添加噪声也常被用来包括未建模的现象和特征。在网络动力学中，对噪声的鲁棒性通常可以通过网络[23]、[24]、[25]、[26]的频谱特性来表达。因此，研究石墨的谱支柱来评价石墨[7]所描述的大型网络的鲁棒性是很自然的。图形的特殊情况是与随机块模型[27]相对应的随机块模型，该随机块模型用于对实际社交网络[28]中经常出现的社区结构进行建模。例如，如果我们考虑在元种群中传播流行病的情况，一种自然的方法是将每个节点视为一个小种群，例如一个村庄或社区，而将每个块视为一个区域或城市。

本工作的目的是利用有限秩的分段李普希茨图(encom- pass随机块模型)的性质来分析SIS流行病在大型网络上的稳定性和敏感性。我们的主要贡献是证明石墨的光谱特性可以近似地评估稳定性和抗噪性。为了得到我们的近似结果，我们在第二节中介绍了图形及其相关性质。在第3节中，我们将在从图形取样的网络上对SIS流行病进行分析。我们定义了一个合适的灵敏度指数，我们用网络的光谱支撑来表示它，我们用底层图形的光谱特性来近似它。在第四节中，我们通过一个随机块模型的仿真来说明我们的结果。最后，第五部分是结论和未来的工作。这个部分包含了graphon的定义和相关的事实，将在接下来的部分中用到。

A. 图表:基本概念和例子

图的定义是一对G = (V, E) V{}是一个有限集的顶点或节点和E⊆{(i, j)∈V×V:我j}是边的集合。在这项工作中，我们考虑简单的图，这样它们是无向的(即它们是无向的)。，没有方向的边)，未加权(即不包含自循环或多边。若(i,j)∈E，则图a = [ai j]∈RN×N的邻接矩阵aij =1，否则aij =0。这个矩阵是真正的对称非负的特征值命令λ1 (A)≥λ2 (A)≥···≥λN (A)。我们用W表示所有有界对称可测函数W:[0,1]2→r的空间。这个空间中的元素被称为核，因为它们与积分算子有联系。这些tofallkernelsw∈W suchthat0≤W≤1表示为W0，其元素称为graphons，其名称为graph-function的缩写。为了考虑不同图形之间的差异，我们有时要对W的核集W1进行处理，使−1≤W≤1。定义一个图形的度函数为:

每个函数W∈W定义一个积分算子TW: L2[0,1]→L2[0,1] ：

该算子是紧致的，具有以0为唯一累积点的离散谱。每个非零特征值具有有限的多重性。如果相关算符的谱包含有限数量的非零特征值[29]，则称W为有限秩。阶跃图形是一个定义为阶跃函数的图形。将一个函数划分为S1，这种类型的石墨也被称为随机块模型石墨，因为它与随机块模型[30]的关系。步进图是有限秩的图，其秩至多等于步数。同时，用可积函数乘积的有限和表示的图形具有有限秩[4]。每个图G都有一个相关联的阶跃图WG，这是通过将[0,1]均匀划分为BNi区间得到的，其中BNi = [(i−1)/N,i/N]对于i = 1，…，N−1,BN =[(N−1)/N,1]，使:

其中1A(x)为指标函数。连接到阶跃图形的算子为:

TWG的谱由图的归一化谱(即λi (TWG) =λi (A) / N),连同无穷多为零。graphon通常是用一个像素的照片,其中每个点(x, y)∈[0, 1] 2是彩色和灰度级代表W (x, y)。一步graphon关联图G,我们想象一个0是一个白色的小广场和1一个黑色小广场我们可以欣赏在图1。

B. 规范

在研究果仁时，各种规范都涉及到[29]、[31]、[4]。对于1≤p <∞，我们定义核的Lp范数为

我们有lp规则和cut规则的不平等关系，如下：

通过考虑与核W∈W相关联的算子TW，可以定义算子范数:

graphons,算子范数等于最大的特征值接线员:| | | TW | | | =λ1 (TW)。对于W1的元素，cut和算子范数之间的关系为:

最后，我们可以将算子的Hilbert-Schmidt范数定义为:

对于所有W∈W，∥TW∥HS都是有限的(即:，内核操作符是Hilbert-Schmidt操作符)，而且：

C.采样与近似

使用采样方法[29]，可以使用一个图形W来生成随机图形。定义1(抽样图[4]):给定一个图形W，其大小N∈N，我们说，如果通过以下方式获得图G，则从W抽样:

1)修正确定性潜在变量{ui = i}N。N我= 1 2)N顶点{1,…，N}，并随机添加无向边之间的顶点i和j独立概率W(ui,uj)为所有i > j。

定义2(分段李普希茨graphon[4]):一个graphon W是分段李普希茨如果存在一个常数L和本土知识重叠序列间隔=[αk−1,αk)定义为0 =α0 <···<αk + 1 = 1,在一个有限的非负整数K,这样对于任何K, L,任何一组Ikl =翼×Il和双(x1, y1)和(x2, y2)∈Ikl我们有: |W(x1,y1)−W(x2,y2)|≤L(|x1−x2|+|y1−y2|)。定义3(足够大N[4]):给定一个分段李普希茨graphon W(根据定义2)和ν< e−1, N是足够大,如果满足以下条件:

引理1(定理1[4]):让W是一个分段的嘴唇——chitz graphon(根据定义2)和G与N个节点采样图从W . N足够大的概率至少1−ν:

通过考虑ν的恒定值,之间的差异算子范数有界是graphons: TWG−TW = O (logN / N) 1/2。

引理2:设W为分段李普希茨图，G为从W中采样N个节点的图。然后用概率N足够大,至少1−ν:

很容易看出，WG是一个阶跃图，取值为{0,1}，我们可以应用[31,Remark 10.8]中的不等式，从而:

A. SIS动力学及其稳定性

我们考虑了一个确定性的SIS模型，该模型建立在一个由具有相同覆盖率和感染率的连通图G所描述的网络上。每个agent的动态可以用[17]来建模:

Xi在(t)∈[0, 1]是第i个族群,被感染的比例在时间t,δ是回收率和β感染率。所有网络的模型可以用矩阵形式表示为:

其中x(t) = [x1(t)，x2(t)，…，xN(t)] t是系统的状态向量，I是单位矩阵，x (t) = diag[x1(t)，x2(t)，…，xN(t)]是一个对角矩阵，a是网络的邻接矩阵。

对于任意初始条件，当满足以下条件时，平衡态x = 0(无病态)是全局渐进稳定的[17，定理6]:

与graphons近似图来看,方便考虑序列的图形参数化它们的大小N .因此,它是合理的假设参数δ或β也依赖于N:在需要时,我们应当强调通过编写δN和βN这种依赖。作为石墨应用的第一个例子，我们根据石墨的特性，对从W中采样的图形确定了达到无病状态的条件。

命题1(流行的稳定性):让W是一块——明智李普希茨graphon和G图与N个节点采样W,代表网络(4)的SIS传染病模型。然后N足够大,疫情将达到无病状态的概率至少1−ν如果:

b .索引时对噪声敏感

当它的重点是稳定无病状态,它是自然的研究(4)在原点附近的线性化[32]：

在给定条件下，这种线性化是指数稳定的[18](5)。现在我们将注意力转向这种稳定性的鲁棒性，并更精确地量化流行病对平衡点附近噪声的反应。根据流行病[20]、[21]和一般网络系统[26]、[23]的多项工作，我们在(7)中加入了附加噪声，得到如下动态:

其中n(t)∈RN是一个合适的噪声处理[21]。这种噪声可以表示迁移或原始模型中没有包含的其他现象。因此，可以通过定义为渐近均方误差的噪声指数来衡量噪声对疾病传播的影响:

在适当的噪声矢量假设下，该指标由网络的特征值确定。

命题2:考虑系统(8)中给出满足条件(5)和噪声向量与零均值和汽车相关函数E (n (t) n (t−ξ)t] =σ2δ(ξ)我。然后,噪音(10)tN∑e2 (t−τ2)λi (A) dτ2指数(9)可以表示为:

我们从第三个项目开始学习：

对于标量a∈R，有a = tr(a)，可以对被积函数及其循环性质进行跟踪，得到:

因为噪音自动化关联函数的特点，所以我们有以下的式子：

使用线性的跟踪和狄拉克δδ的属性(τ−1)φ(τ)dτ=φ(a)对任何间隔Ia在其内部,任何测试函数,我们得到:

矩阵是对称的,可以分解成一个= QΛQT Q是一个正交矩阵和Λ是一个对角矩阵的对应的特征值。自从eA = QeΛQT,我们有:

回顾式(11)，我们发现当t→∞时，第一项由于条件(5)变为零，而第二项由于噪声的期望值为零而变为零。然后,

因为条件(5)意味着A的所有特征值都是负的。

我们的目标是估计从石墨采样的图形的噪声指数，利用石墨算子的谱。假设图W的秩为M，对于所有的N≥M我们定义:

λi (TW)的非零特征值是TW i = 1,……,M和λi (TW) = 0 = M + 1,…, N。我们将使用Jnoise Jnoise当G的一个近似是一个大型的W, N G图从W采样;定理1保证了近似误差小，概率高。因为这个结果涉及到流行的图表增加大小为N,我们必须指定参数的依赖NδNβN。显然,我们需要满足稳定条件(5)对所有N:实际上,我们需要更强的属性λ1(一)βN /δN仍有界离1也限制N→∞。因为几乎肯定λ1(一)线性增长与N(除了琐碎graphon W = 0),以确保统一的猛扑λ1βN /δN(一个),我们将假设感染强度βN /δN满足: 一些积极的常数β,δ。

定理1 (Graphon近似):让W是一块——明智李普希茨Graphon有限秩的M和N G图节点采样与N≥W M .如果δN =δ̄βN = N−1β̄满足条件(6),然后对N足够大,概率至少1−ν:

证明:在这个证明,我们将假设λi (TW)(即。TW的M非零特征值和N−M 0)在无添加的顺序排序:这个选择不会改变之和定义Jnoise符合W, N无添加的顺序λi (A)。这种一致性为了应用Wielandt-Hoffman定理会有用的。自从λi (A) = Nλi TW,δN =δ̄βN = N−1β̄,我们有:

我们将vector定义为：

所以numerator的总数是：

那么，其中的关系，向量规范∥·∥1≤意味着：

我们可以在[33，定理2]中将魏和夫曼定理推广到无限维空间，由于N≥M，得到:

的定义和证明完成通过使用φ(N)和应用引理1分母。

假设δ=δ̄是常数和β= N−1β̄意味着,随着图形大小,愈合率(这取决于每个)保持不变,而感染率下降。在[7]中也选择了这个自然标度定律。实际上，在稠密图上，这一假设意味着，在较大的图中，即使存在更多的潜在交互，连接的平均强度也进行了适当的调整:这一事实说明了个体之间接触率的自然限制。当我们让N走到正无穷,如果ν是常量或者某个常数αν= Nα,我们可以看到,上界定理1中给出的估计误差∆噪音趋于零为O (logN) / (N)。因此,通过选择α> 1和应用Borel-Cantelli引理,我们获得∆噪音几乎必然收敛于零率O (logN) / (N)。在定理1的假设下，索引Jnoise是有界的，并且是离0有界的。因此，相对误差∆noise/Jnoise也有相同的渐近行为。这种相对误差的渐近行为并不取决于假设βN = N−1β̄仍然是适用于任何选择δN和βN满足(6)和(12)。事实上,任何其他选择δN和βN满意(12)将修改Jnoise和Jnoise同样的乘法因子,G W, N,相对误差将保持不变。

四、数值模拟结果

我们用图2中的像素图来考虑随机块模型graphon WSB，其中：

graphon算子的非零特征值TWλ1 = 0.5275,λ2 = 0.2098,λ3 = 0.0126,λ4 =−0.0128和λ5 =−0.0971。我们假设βN =β= 0.1 andν= 0.02,满足条件(3)N≥40岁,我们从力生成采样图40≤N≤1000。为每个网络的价值δN = Nδ̄= Nβ̄(| | | TW | | | +φ(40)选择满足条件(6)和我们计算的相对误差∆噪声/ Jnoise, G获得图3的结果。我们可以观察到，当N增加时，相对误差趋近于零，如备注1所示。

五、结论

这项工作提出了一个大网络上SIS流行病的分析，假设网络是从一个图形中采样的。关于流行病稳定性的相关信息可以从图中推断出来，而不需要对整个网络拓扑进行计算，甚至不需要知道整个网络拓扑。在这方面，我们在命题1中推导出了一个稳定性判据，并定义了一个只依赖于图形的噪声灵敏度指数(定理1)。这项工作留下了几个问题，包括我们的结果扩展到从没有有限秩的石墨取样的网络:这种扩展可以通过在[7]中开发的光谱近似工具来实现。此外，我们认为石墨不仅可以帮助分析，还可以帮助控制流行:例如，石墨中心性[4]可以为有针对性的干预措施，如检疫或接种疫苗提供指导。

参考资料：

[1] L.Lova ́szandB.Szegedy,“Limitsofdensegraphsequences,”Journal of Combinatorial Theory, Series B, vol. 96, no. 6, pp. 933–957, 2006. [2] C. Borgs, J. T. Chayes, L. Lova ́sz, V. T. So ́s, and K. Vesztergombi, “Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing,” Advances in Mathematics, vol. 219, no. 6, pp. 1801–1851, 2008. [3] ——, “Convergent sequences of dense graphs II. Multiway cuts and statistical physics,” Annals of Mathematics, vol. 176, no. 1, pp. 151– 219, 2012. [4] M. Avella-Medina, F. Parise, M. Schaub, and S. Segarra, “Centrality measures for graphons: Accounting for uncertainty in networks,” IEEE Transactions on Network Science and Engineering, 2018. [5] Y. Zhang, E. Levina, and J. Zhu, “Estimating network edge probabil- ities by neighbourhood smoothing,” Biometrika, vol. 104, no. 4, pp. 771–783, 2017. [6] C. Kuehn and S. Throm, “Power network dynamics on graphons,” SIAM Journal on Applied Mathematics, vol. 79, no. 4, pp. 1271–1292, 2019. [7] S. Gao and P. E. Caines, “Spectral representations of graphons in very large network systems control,” in IEEE Conference on Decision and Control, 2019, pp. 5068–5075. [8] ——, “The control of arbitrary size networks of linear systems via graphon limits: An initial investigation,” in IEEE Conference on Decision and Control, 2017, pp. 1052–1057. [9] ——, “Optimal and approximate solutions to linear quadratic regula- tion of a class of graphon dynamical systems,” in IEEE Conference on Decision and Control, 2019, pp. 8359–8365.

[10] S. Gao and P. E. Caines, “Graphon control of large-scale networks of linear systems,” IEEE Transactions on Automatic Control, pp. 1–1, 2019.

[11] P. E. Caines and M. Huang, “Graphon mean field games and the GMFG equations,” in IEEE Conference on Decision and Control, 2018, pp. 4129–4134.

[12] F. Parise and A. Ozdaglar, “Graphon games,” in ACM Conference on Economics and Computation, 2019, pp. 457–458.

[13] A.LajmanovichandJ.A.Yorke,“Adeterministicmodelforgonorrhea in a nonhomogeneous population,” Mathematical Biosciences, vol. 28, no. 3-4, pp. 221–236, 1976.

[14] N. T. Bailey, “Macro-modelling and prediction of epidemic spread at community level,” Mathematical Modelling, vol. 7, no. 5-8, pp. 689– 717, 1986.

[15] R. Pastor-Satorras, C. Castellano, P. Van Mieghem, and A. Vespig- nani, “Epidemic processes in complex networks,” Reviews of modern physics, vol. 87, no. 3, p. 925, 2015.

[16] P.E.Pare ́,J.Liu,C.L.Beck,B.E.Kirwan,andT.Bas ̧ar,“Analysis, estimation, and validation of discrete-time epidemic processes,” IEEE Transactions on Control Systems Technology, 2018.

[17] C. Nowzari, V. M. Preciado, and G. J. Pappas, “Analysis and control of epidemics: A survey of spreading processes on complex networks,” IEEE Control Systems Magazine, vol. 36, no. 1, pp. 26–46, 2016.

[18] W. Mei, S. Mohagheghi, S. Zampieri, and F. Bullo, “On the dynamics of deterministic epidemic propagation over networks,” Annual Reviews in Control, vol. 44, pp. 116–128, 2017.

[19] G.Zhu,X.Fu,andG.Chen,“Spreadingdynamicsandglobalstability of a generalized epidemic model on complex heterogeneous networks,” Applied Mathematical Modelling, vol. 36, no. 12, pp. 5808–5817, 2012.

[20] E. Forgoston, S. Bianco, L. B. Shaw, and I. B. Schwartz, “Maximal sensitive dependence and the optimal path to epidemic extinction,” Bulletin of mathematical biology, vol. 73, no. 3, pp. 495–514, 2011.

[21] P. E. Pare ́, C. L. Beck, and A. Nedic ́, “Epidemic processes over time- varying networks,” IEEE Transactions on Control of Network Systems, vol. 5, no. 3, pp. 1322–1334, 2017.

[22] A.L.Krause,L.Kurowski,K.Yawar,andR.A.VanGorder,“Stochas- tic epidemic metapopulation models on networks: SIS dynamics and control strategies,” Journal of theoretical biology, vol. 449, pp. 35–52, 2018.

[23] F. Fagnani and P. Frasca, Introduction to Averaging Dynamics over Networks. Springer, 2018.

[24] X. Ma and N. Elia, “Mean square performance and robust yet fragile nature of torus networked average consensus,” IEEE Transactions on Control of Network Systems, vol. 2, no. 3, pp. 216–225, 2015.

[25] E. Lovisari and S. Zampieri, “Performance metrics in the average consensus problem: a tutorial,” Annual Reviews in Control, vol. 36, no. 1, pp. 26–41, 2012.

[26] F. Garin and L. Schenato, “A survey on distributed estimation and control applications using linear consensus algorithms,” in Networked Control Systems. Springer, 2010, pp. 75–107.

[27] P. W. Holland, K. B. Laskey, and S. Leinhardt, “Stochastic blockmod- els: First steps,” Social networks, vol. 5, no. 2, pp. 109–137, 1983.

[28] B. Karrer and M. E. Newman, “Stochastic blockmodels and com- munity structure in networks,” Physical review E, vol. 83, no. 1, p. 016107, 2011.

[29] L. Lova ́sz, Large Networks and Graph Limits. American Mathemat- ical Society, 2012.

[30] E. M. Airoldi, T. B. Costa, and S. H. Chan, “Stochastic blockmodel approximation of a graphon: Theory and consistent estimation,” in Advances in Neural Information Processing Systems, 2013, pp. 692– 700.

[31] S.Janson,Graphons,cutnormanddistance,couplingsandrearrange- ments. NYJM Monographs, 2013, no. 3.

[32] A.KhanaferandT.Bas ̧ar,“Anoptimalcontrolproblemoverinfected networks,” in International Conference of Control, Dynamic Systems, and Robotics, 2014.

[33] R. Bhatia and L. Elsner, “The Hoffman-Wielandt inequality in infinite dimensions,” vol. 104, no. 3, pp. 483–494, 1994.

原文作者： Renato Vizuete, Paolo Frasca, and Federica Garin

原文地址：https://arxiv.org/pdf/1912.10330.pdf