Finding Patient Zero via Low-Dimensional Geometric Embeddings

在一個擁有 10,000 個節點的大型網路中，當傳染病或惡意網路攻擊爆發後，我們能否僅靠最終的感染狀態，精準抓出源頭的「零號病人」？一篇來自 arXiv 的最新研究提出了一種反直覺的幾何解法：透過 Johnson-Lindenstrauss 投影技術，將複雜的網路距離矩陣壓縮到極低維度的空間中。實驗數據證實，即使觀測資料經過大幅度壓縮，演算法依然能藉由計算感染者的幾何重心，精準定位出初始的感染源。

複雜網路中的零號病人難題與 SIR 模型

疫情傳播過程的動態模型，在現代社會的各個研究領域中無所不在。在流行病學中，它被用來追蹤疾病的擴散；在社會學中，它能模擬社群網路上的意見領形與謠言散播；而在電腦科學領域，這類模型更被廣泛應用於分散式資料庫的更新同步、網際網路路由表的建構，以及大規模企業網路中的網路攻擊防禦機制。

儘管學界對於「正向」的傳播擴散過程已經有相當透徹的理解，但對於「逆向」的追溯卻知之甚少。給定一個已經蔓延開來的傳染狀態，要在茫茫網海中逆向推導出最初的感染源（即零號病人，Patient Zero），是一個充滿挑戰的反演問題。過往的研究多半依賴完整的感染路徑紀錄，但在現實世界的監控系統中，我們往往只能取得殘缺或不完整的最終狀態快照。

為了建立這項難題的分析基礎，研究團隊採用了傳播學中經典的 SIR 模型（Susceptible-易感、Infected-感染、Removed-移除）的一個特例：獨立級聯模型（Independent Cascade Model）。在這個離散時間的模型中，每一回合受感染的節點都會以特定的機率 β 將病毒傳染給相鄰的易感節點，傳播後該節點即被標記為「移除」且不再具有傳染力。演算法的終極目標，就是透過這個最終觀察到的不完整集合，最大化找出真實零號病人 ω 的後驗機率。

導入 Johnson-Lindenstrauss 引理的低維壓縮

面對成千上萬個節點的網路，若要計算並比對每一個受感染節點到其他所有節點的距離，將會產生極為龐大的高維度矩陣。為了讓這套幾何追溯方法具備可擴展性（Scalability），研究人員巧妙地導入了數學界著名的 Johnson-Lindenstrauss (JL) 引理。

JL 引理指出，在一個高維度歐幾里得空間中的 n 個點，可以透過線性投影被映射到一個維度僅有 O(ln n / ε²) 的極低維度空間中，且任意兩點之間的距離都能被維持在 1 ± ε 的誤差範圍內。這意味著複雜的網路拓撲結構，可以在不流失核心空間特徵的前提下，被極度壓縮。

在實際的演算法實作中，這種降維映射通常是透過稀疏的隨機高斯矩陣來達成。透過這項技術，研究團隊得以將龐大且計算昂貴的網路距離特徵，轉換為輕量化的低維度幾何座標，為後續的重心定位運算鋪平了道路。

歐幾里得空間中的四階段感染重心估算演算法

基於上述的數學基礎，本篇研究提出了包含四個核心階段的重建演算法。首先是距離特徵擷取（Distance Signatures），演算法會針對每一個已感染的節點，計算其到達網路中所有其他節點的最短路徑距離，形成一個包含空間擴散結構的高維度矩陣 F。

第二階段是幾何嵌入（Geometric Embedding）。演算法利用一個數值服從常態分佈的隨機高斯 JL 矩陣 R，將高維度的特徵矩陣 F 投影至 k 維的歐幾里得空間中，獲得壓縮後的座標矩陣 X。這一步驟大幅去除了冗餘資訊，保留了最具指標性的相對距離。

緊接著進入傳播重心估算（Epidemic Center Estimation）階段。給定所有被感染節點在低維度空間中的嵌入座標後，演算法會透過計算這些座標的平均值，找尋出一個幾何上的「重心」向量 c。這個重心在幾何意義上，高度近似於整起傳播事件的幾何震央。

最後則是零號病人評分（Patient-Zero Scoring）。演算法會計算網路中所有潛在節點的嵌入座標與重心 c 之間的歐幾里得距離。距離重心越近的節點，其評分排名就越高；排名第一的節點，即為系統所推估的零號病人。

萬人規模 Erdős-Rényi 隨機圖的網路密度影響

為了驗證這套幾何演算法的有效性，研究團隊利用 Python 開發了專屬的模擬框架，並在擁有 10,000 個節點的 Erdős-Rényi (ER) 隨機圖上進行了大量測試。每次測試皆以單一已知的零號病人為起點，設定傳播機率 β = 0.25，並在經過 4 個回合後，記錄感染狀態交由演算法進行盲測還原。

模擬結果揭露了網路底層拓撲對追溯精準度的強烈影響。在觀察隨機圖的連通機率 p（即網路密度）時，研究發現了明顯的相變特徵。當網路處於極度稀疏的狀態時，疫情根本無法有效擴散，系統缺乏足夠的結構資訊，導致演算法排名表現不佳。

然而，當網路密度逼近臨界閾值、開始出現巨大連通分支（Giant Component）時，感染傳播的路徑完美保留了樹狀的拓撲特徵。在這個「黃金區間」，幾何特徵最為鮮明，演算法的預測排名達到了最佳的精準度。但若網路密度繼續增加至過度稠密，傳播路徑會產生嚴重的同質化（Homogenization）現象，導致各個節點的距離特徵變得模糊難辨，演算法的追溯能力也隨之再次下滑。

逼近極限的維度 k 與資料壓縮後的重建表現

除了網路密度，演算法面對的另一項終極考驗是資料壓縮的極限。在探討 JL 投影維度 k 對重建品質的影響時，數據呈現出非常符合理論預期的非線性曲線。

當設定的投影維度 k 極小的時候，幾何空間產生了嚴重的失真，重心估算器完全失效，推斷出的零號病人排名墊底。但令人驚豔的是，只要維度 k 一旦逼近網路規模的對數值（log n），這套極度壓縮的嵌入矩陣就能忠實地保留絕大部分的距離特徵，演算法預測準確率的排名中位數會瞬間產生斷崖式的改善。

隨著維度繼續上升，預測表現很快就會趨於平緩並貼近完美值。這證實了投入過多的運算維度只會帶來邊際效益遞減，只要達到對數門檻，極低維度的資料就足以完成高精確度的源頭追蹤。

只要網路密度不過度均質化，極低維度的幾何壓縮不但不會破壞傳播路徑的拓撲特徵，反而為真實世界中資料破碎的溯源難題，提供了一條兼具運算效率的新捷徑。