本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
常見的圖挖掘任務是社區檢測，它尋求基於網路連接性的統計規律將網路無監督地分解為群組。儘管有許多這樣的演算法，但社群檢測的「沒有免費午餐」定理意味著沒有演算法可以在所有輸入上都是最優的。然而，在實踐中，人們對不同演算法如何過度或不適合真實網絡，或者如何可靠地評估跨演算法的這種行為知之甚少。在這裡，我們對 16 種最先進的社區檢測演算法的過度擬合和欠擬合進行了廣泛的研究，這些演算法應用於 572 個結構多樣的現實世界網路的新穎基準語料庫。我們發現（i）在給定相同輸入的情況下，演算法發現的社群數量和組成差異很大； (ii) 演算法可以根據其在現實世界網路上的輸出的相似性分為不同的高級組； (iii) 演算法差異導致基於連結的學習任務的準確性存在很大差異； (iv) 沒有任何演算法在所有輸入的此類任務中始終是最好的演算法。最後，我們使用理論原理診斷來量化每種演算法對網路數據過度擬合或欠擬合的總體趨勢，並討論對社區檢測未來進展的影響。