在線社交網絡社區發現

在線社交網絡社區發現涵蓋了多方面的內容，包括在線社交網絡表示模型、在線社交網絡社區發現算法和在線社交網絡社區發現評價指標等等內容。

從本質上講，在線社交網絡中的虛擬社區發現就是將網絡節點按照其內在的拓撲結構連接緊密程度劃分成若干子圖的過程，在計算機科學領域，該問題一般被稱作圖分割問題。對於圖分割問題的研究可以追溯到上世紀，其中兩個最重要的算法即Kernighan-Lin算法 ^[1]  和譜平分法 ^[2]  。進入21世紀以來，隨着複雜網絡科學的發展，網絡社區結構的發現問題獲得了各領域專家的更多重視。Michelle Girvan和Mark Newman在2002年提出了一個新的分裂算法，即GN算法 ^[3]  。在該算法中，為了衡量網絡社區結構劃分的好壞，他們基於複雜網絡和隨機網絡結構特徵的比較，提出了模塊度的概念，拉開了社區發現蓬勃發展的序幕。針對網絡拓撲結構中若干節點同時隸屬於多個社區的現象，Gergely Palla等在2005年提出了重疊社區概念，利用派系和團的定義去發現網絡中的重疊社區和處於社區邊界位置的橋節點 ^[4]  。通過研究真實網絡拓撲結構特性和假設的網絡模型之間的差異，借用貝葉斯推斷等數學工具，Mark Newman等人提出了基於概率模型的社區結構發現算法，通過最大化似然概率，實現重疊結構的社區的發現。