社會和資訊網路:基於圖表的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