摘要 網路中社群結構的發現和分析是物理學界最近備受關注的一個主題，但迄今為止提出的大多數方法由於其計算成

本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。

原文連結

• SFI 頁面

論文資訊

• 類型：已發表論文
• 日期：2022-09-02

摘要

網路中社群結構的發現和分析是物理學界最近備受關注的一個主題，但迄今為止提出的大多數方法由於其計算成本而不適合非常大的網路。在這裡，我們提出了一種用於檢測社群結構的分層聚集演算法，該演算法比許多競爭演算法更快：它在具有 n 個頂點和 m 個邊的網路上的運行時間為 O(mdlog n)，其中 d 是描述社群結構的樹狀圖的深度。許多現實世界的網路都是稀疏且分層的，具有 m n 和 d log n，在這種情況下，我們的演算法基本上以線性時間 O(n log2 n) 運行。作為該演算法應用的一個例子，我們用它來分析大型線上零售商網站上銷售的商品網絡，如果同一買家經常購買這些商品，則網絡中的商品就會被連結。該網路擁有超過 40 萬個頂點和 200 萬條邊。我們證明，我們的演算法可以從該網路中提取有意義的社區，揭示客戶購買習慣中存在的大規模模式。