本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：工作論文
- 編號：工作論文 #802
- 日期：2026-03-18
摘要
網路的穩健性在於它不易因刪除節點而斷開連線。斷開一對其他節點所需刪除的最小節點數稱為該對的連通性。可以證明，連通性也等於節點之間的節點無關路徑的數量，因此我們可以透過計算節點無關路徑的數量來量化網路的穩健性。不幸的是，計算這樣的數字被認為是一個 NP 難題，需要指數級的時間才能完成。在本文中，我們提出了一種近似演算法，該演算法在最壞情況時間內（與圖大小呈線性關係）為有向圖或無向圖上的任意一對節點之間的節點獨立路徑數量提供了良好的下界。同一演算法的變體也可以以相同的近似值計算圖的所有 $k$ 分量。根據經驗，我們的演算法在隨機圖上的準確率超過 99%，對於幾個現實世界的網路來說，準確率是 100%。作為演算法的演示，我們將其應用於傳統 NP 硬演算法完全難以處理的兩個大圖——科學家之間的合作網絡和生物技術公司之間的商業聯繫網絡。