本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
動態網路中的社群偵測是獲取複雜系統的粗粒度視圖並調查其底層過程的常用方法。雖然機器學習和物理文獻中已經提出了許多方法，但我們缺乏對它們的優點和缺點的理論分析，或者對何時可以檢測到社區的最終限制的理論分析。在這裡，我們研究了動態網路中檢測社區結構的基本限制。具體來說，我們分析了動態隨機區塊模型的可偵測性限制，其中節點隨著時間的推移改變其社群成員資格，但邊緣在每個時間步獨立產生。使用空腔方法，我們根據變化率和群落強度得出精確的可檢測性閾值。低於這個尖銳的閾值，我們聲稱沒有有效的演算法可以比機會更好地識別社區。然後，我們給出了兩種最佳演算法，因為它們一直成功達到這個閾值。第一個使用置信傳播，它提供漸進最優精度，第二個是基於線性化置信傳播方程式的快速譜聚類演算法。這些結果擴展了我們對社區檢測局限性的一個重要方向的理解，並引入了新的數學工具，用於對具有其他類型輔助資訊的網路進行類似的擴展。