社區發現算法是一種旨在識別網絡中具有緊密內部連接和稀疏外部連接的群體結構的技術。這項研究始于上世紀60年代，隨著社交網絡的興起，其重要性和關注度日益提高。
歷史背景
社區發現算法的研究源于對復雜系統模塊結構特性的認識。Kernighan-Lin提出的二分算法促進了子圖分割問題的研究，這成為了圖挖掘領域的重要課題。社會學家也在社會網絡中發現了社區結構的普遍性。21世紀初，社區研究開始受到重視，隨著社交網絡的普及，這一領域的研究變得更加活躍。
社區發現的應用
社區發現算法在網絡分析、生物學、傳染病傳播等領域有著廣泛的應用。在生物學中，它可以用于新陳代謝網絡分析、基因調控網絡分析和主控基因識別。在傳染病傳播方面，社區發現可以幫助預測傳播路徑，以便及時控制疫情。此外，社區發現還在反恐、犯罪分析和社會網絡分析中發揮作用。
社區發現面臨的問題
社區發現算法的研究面臨著多重挑戰，包括社區的重疊性、局部性、多模式性和多維性、節點角色的差異性以及網絡的動態性。這些問題都需要進一步的研究和發展。
相關工作
傳統非重疊社區發現
非重疊社區發現算法最初基于相似度或譜方法，但由于計算復雜度高，后來發展出了更快捷的近似方法。Girvan與Newman的工作推動了非重疊社區發現的研究，他們的模塊度度量法尤其重要?；谀K度的優化算法隨之涌現，其中包括Duch的極值優化算法和Guimera的模擬退火算法。Blondel等人開發的Fast Unfolding算法被認為是最快的非重疊社區發現算法之一。何東曉等人提出了基于聚類融合的遺傳算法，金弟等人則提出了基于隨機游走的蟻群算法。
重疊社區發現
重疊社區發現算法的研究受到了廣泛關注，因為它更能反映現實網絡的特點。Palla等人提出的派系過濾算法是早期的重要成果。沈華偉等人提出了基于極大完全子圖的社區發現算法。Evans的Clique Graph和Ahn的邊社區發現方法也都體現了重疊社區的重要性。
參考資料 >
萬物皆網絡,萬字長文詳解社區發現算法Louvain - 知乎. 知乎.2024-11-11