上世紀60年代，Herbert Simon 首先提出了複雜系統具有模組結構特性的概念。而針對社區的研究實際上是從子圖分割問題演化而來，Kernighan-Lin 提出的二分算法使得子圖分割問題逐漸成為當時圖挖掘領域關注的重點。另外，在社會學領域，社會學家也發現社區結構在各種複雜網路中的普遍存在性。進入21世紀後，社區的研究開始被研究者所重視，而近年來隨著社交網路的崛起，這一領域的關注度已大大提升。
基本介紹
- 中文名：社區發現算法
社區發現的研究內容,社區發現面臨的挑戰性問題,社區發現相關工作,傳統非重疊社區發現,重疊社區發現,
社區發現的研究內容
社區反映的是網路中的個體行為的局部性特徵以及其相互之間的關聯關係，研究網路中的社區對理解整個網路的結構和功能起到至關重要的作用，並且可幫助我們分析及預測整個網路各元素間的互動關係。實際上,社區發現已經在多個領域發揮著作用:在生物領域的新陳代謝網路分析、基因調控網路分析、主控基因識別等方面有很重要的作用,如預測蛋白質相互作用網路中的複合體和社區模組對於理解生物系統的組織和功能以及未知蛋白質功能預測具有重要的意義,而在近年來全球的傳染病病毒、細菌等傳播都有逐年增長的態勢,在特定的疾病和病毒傳播網路中,可通過研究分析並找出傳染病的關鍵社區、關鍵節點以及重點防護易感人群,以預測傳播路徑從而及時切斷傳播路徑達到對網路進行控制的目的。而最近的一些權威研宄揭示了病毒可以被局限在高影響力的節點、高權重的邊以及核心層的周圍,因此社區發現在傳播演化和預測防控領域的作用將更值得深入研究。另外,自“911事件”以來,世界各國政府、警方和學者都在試圖用包括社區發現在內的多種社會網路分析手段對恐怖主義活動、犯罪活動進行分析,通過發現社會網路、電訊網路以及網際網路中的犯罪網路,並迅速鎖定犯罪分子的領導者,對其及其團伙的犯罪行為進行全方位的關聯追蹤,進而有效打擊犯罪網路,維護社會政治經濟的穩定社區發現在網際網路Web上的套用則更為廣泛,如在微博中利用社區發現用於精準廣告投放,對電子商務中的用戶進行社區發現從而幫助其建立更可靠的推薦系統,在搜尋引擎中對搜尋記錄進行基於主題詞的Web文檔社區發現從而分析用戶行為,可以為用戶提供更加個性化的搜尋結果。
社區發現面臨的挑戰性問題
針對社區發現的研宄,是一項網路科學中的基礎性研究,其理論和套用價值都很大,在過去十多年內吸引了很多研究者的關注。於此同時,我們也注意到,在十多年的發展中,社區發現研究的重點和焦點都發生了一些變化,針對當前網際網路技術推動下的線上社交網路等社會網路環境中的網路拓撲及社區結構的若干特點,社區發現的研宄面臨著如下若千挑戰性
問題:
1)社區的重疊性
傳統的社區發現研究一般基於“每一個節點都唯一歸屬於某個社區”的假設,而在現實社會網路中,人們往往同時屬於不同的社區,而這種同時屬於多個社區的人又是信息傳遞、社會交往中的關鍵。因此,針對重疊社區發現的研宄應得到研宄者的重視和關注。
2)社區的局部性
傳統的社區發現算法很多都基於全局的信息,例如GN算法中的"邊介數”、基於隨機遊走的算法中任意兩點間的相似度、基於模組度的算法中的模組度等,都必須在考慮整個網路結構的前提下才能得出。隨著信息化程度的不斷提高,社會網路規模越來越龐大,獲得網路的全局信息變得十分困難,而且這些社區發現算法在海量社會網路數據下顯得非常低效。另一方面,社會網路通常是稀疏的,絕大多數個體與外界的直接聯繫都是有限的,而很多研究和套用都只關心某些節點所在的局部結構。甚於這些考慮,局部社區的概念被提出,相關問題需要進一步深入研究。
3)網路的多模式性與多維性
傳統的網路分析中的節點對象通常是單一類型的,如:節點只代表了人、用戶或者網頁其中的一種,而多模式網路中的節點類型則是多樣化的。比如社交網路中的某個用戶分享的項目種類是多樣化的,包括圖片、視頻、日誌等,與其將這些互動的不同類型實體建模為節點的不同屬性,不如建模為多模式網路更為方便。
網路的多維性是指網路中的節點(用戶)之間的邊(連線)具有多種類型,而由這些節點及不同類型的邊所組成的不同“維度”的網路(圖)就稱之為多維度網路。其中,每一個維度的網路表示了節點間不同類型的聯繫(互動),而邊上往往又附帶有權值信息,其代表了節點間互動的程度與連線的強度。
因此,傳統的對於單一模式、單個維度網路的單一分析在這裡己經不再適用,如何在多模式、多維度網路當中解決不同模式及維度下的信息融合、共享以及進行社區發現等相關問題也亟待解決。
4)網路節點角色的差異性
傳統的圖挖掘、網路分析方法,並沒有將網路中每個節點角色進行過多的區分,認為節點的地位是等同的。實際上,在各種複雜網路中尤其是社會網路中,都存在著帕累托效應(二八規則),即節點的角色存在著差異。只有大約百分之二十甚至更低比例的節點,在網路中發揮了領袖節點的作用,它們更具有權威性、中樞性、核心型等特徵。同時也具有更多的經驗和影響力,對社區的形成起著決定性的作用,對網路拓撲結構的演化、網路中的信息流通和傳播有重大影響。在套用和分析中,首先應確定此類關鍵節點的存在性。而社會網路往往具有更為龐大的規模,如何快速有效地挖掘此類成員成為一個挑戰性的問題。
5)網路的動態性
傳統的社區研宄一般是針對靜態的網路展 研宄的,這種研究視角不能很好地反映諸如信息擴散、同步等動態過程。研究網路的動態性的目的在於揭示網路拓撲結構對發生在其上的動態過程的影響,以及這些動態過程是否能夠反映其“承載網路”的拓撲結構特徵。
研究社區結構和網路動態性的關鍵在於社區演化問題,其主要關注網路自身結構和在其上頻繁發生的互動過程相互作用的結果,如社區形成、社區生長、社區縮減、社區合併、社區分裂、社區消亡等。
社區發現相關工作
傳統非重疊社區發現
傳統意義上的社區指的是網路中的一組節點間具有較大的相似性,從而形成的一種內部連線緊密,而外部稀疏的群體結構。而非重疊社區指的是每一個節點僅可屬於一個社區,社區與社區之間沒有交集。
1)傳統方法
除了簡單利用相似度來做層次聚類的方法外,譜方法最早被用於解決圖分割問題,由於問題的相似性,它被廣泛地運用到社區發現中但該類方法計算的時間複雜度較高,由於涉及到許多矩陣特徵向量的計算,例如相似度矩陣,因而計算的時間複雜度可達0(n^3),在大規模網路套用中,它的效率成為一個很大問題。當然,一些以犧牲精度為代價的近似方法相繼被提出,提高了譜方法的效率。另外,譜方法也是很少利用權值信息。"隨機遊走"這一概念也被成功地引入社區發現中,很多研究者在這一方面做了很多工作並得到了很好的效果。其基本思想是,由於社區結構內部的高緊密性、高連通性,一個"隨機漫步者"總是會在某個社區內部行走很長時間。因此,從一個節點出發,"隨機漫步者"會在較少的步數內到達同一社區內的節點,或者可以以此定義某種相似度來進一步做社區發現。另外很重要的一點是,基於隨機遊走的方法易於擴展到加權網路的社區發現,這也是其優勢之一。Chen等人利用稀疏矩陣技術中的重排列矩陣(阻塞矩陣)來識別稠密子圖,提出了一種在給定的稀疏圖中識別出稠密子圖的方法,其方法不需預先知道具體的族個數。
2)基於模組度的最佳化方法
對於非重疊社區發現算法的研究主要歸功於Girvan與Newman在2002年的開創性研究工作,其研究成果證實了眾多現實網路中都存在這種社區結構,同時他們所提出的GN社區發現算法也多次被引用,隨後的Fast Newman算法改進了 GN算法的性能。Radicchi快速分裂算法採用聚類係數來代替邊介度提升算法的速度。Newman在2004年提出了一種被廣泛套用的社區結構度量函式-模組度(Modularity),使非重疊社區發現研究得到空前的發展。基於模組度的最佳化算法逐漸出現,Duch的極值最佳化算法,Guimera的基於模擬退火的GA算法等,這類方法將社區發現問題轉化為一個最佳化問題,進而去尋找一個目標函式
的最優解。而Blonde等在2008年提出的一個(Fast Unfolding)多層次貪婪層次合併算法被公認為是當前執行速度最快,準確率也很高的非重疊社區發現算法之一。
何東曉等人提出了一種基於聚類融合的遺傳算法,並將其用於網路社區發現問題。該算法將聚類融合的思想引入到遺傳算法的交叉運算元中,利用父類個體的聚類信息以及網路拓撲結構中的局部信息來共同產生新的個體金弟等人從仿生學的角度出發,並利用馬爾可夫鏈及隨機遊走的思想,提出了利用基於隨機遊走的蟻群算法來發現社區結構。
傳統的基於模組度的社區發現方法大多只能發現相似規模的社區,林旺群等人則提出了一種基於帶權圖並行分解的層次化社區發現方法,該方法採用圖劃分的方式定義社區結構,並基於此實現了社會網路社區發現算法黃髮良等人認為基於單一評判指標來做最佳化的社區發現算法有很大的局限性,因此提出用多目標最佳化方法來處理網路社區發現問題,並提出了一種基於多目標粒子群最佳化的網路社區發現算法。
儘管自從Newman建議使用模組度作為社區結構強度的衡量標準以來,許多基於模組度最佳化的方法都被提出。然而,還缺乏近似的算法來對這個問題提供可靠的理論證明。因此,Dinh提出了一種基於模組度的多項式時間的近似算法,並且在無尺度網路的環境中,給出了理論證明。
重疊社區發現
傳統的社區發現問題的研究中都認為每個節點只能歸屬於唯一的一個社區。而在現實的網路中,節點往往同時歸屬於不同的社區,而這種同時屬於多個社區的節點又是信息傳播和網路演變中的關鍵部分。因此,針對重疊社區發現的研宄得到了研究者的重視和關注,且近年來越來越受到關注,主要有以下幾類方法:
1)基於派系過濾的方法
2005年,匈牙利科學院的Palla等人在《Nature》上發表了一種基於派系過濾的重疊社區發現算法,隨後,該算法被擴展套用到有權網路、有向網路、二部網路等,但該方法不能覆蓋網路中的所有節點,並且自由參數較多,不同參數設定對結果影響較大。沈華為等提出了極大完全子圖來代替節點作為社區的基本構成單元,定義了一種相對普適的網路模組度用以度量網路的重疊社區結構,在此基礎上提出了一種同時體現層次性及重疊性的社區發現算法,並成功套用於學術合作網、蛋白質互動網路等T.S.Evans的Clique Graph也是借鑑了派系過濾的思想,將網路中的派系建立成派系圖用以研究社區結構。
2)基於局部擴張及最佳化的方法
傳統的社區發現算法很多都是基於全局的信息,例如GN算法中的邊介數、基於隨機遊走的算法中任意兩點間的相似度、基於模組度的算法中的模組度等,都必須在考慮整個網路結構的前提下才能計算得出。而隨著網路規模的不斷增大,例如線上社交網路這種龐大的網路,要獲得網路的全局信息是十分困難的,並且獲取過程中的計算量也十分巨大,因此傳統的社區發現算法在這種大規模網路環境下的效率很低。但另一方面,大部分複雜網路又表現出一定的稀疏性特徵,其中的絕大多數元素與外界的直接聯繫都是很有限的,而很多研究和套用都只關心某些節點的局部網路結構。基於這些考慮,局部社區的概念被提出,且近年來在大規模網路中發現局部社區的研究受到越來越多的關注。局部社區發現算法可以從網路中獲得自然合理的重疊社區結構,這類算法通常不去獲取網路中的全局信息,只獲取初始研究節點所在網路區域的局部信息,避免了分析複雜且難以獲取的全局網路信息,因而此類算法能快速有效的發現網路中的社區結構。
3)基於線圖/邊社區的發現方法
Evans和Lambiott提出了一種基於邊社區的重疊社區發現方法丨其基本思路是將原圖轉換為線圖,然後將線圖中的社區轉化為節點型的重疊社區,Ahn則在提出邊社區概念的同時為我們揭示了這種邊社區在真實網路中的普遍存在性Kim等人提出了基於資訊理論編碼的邊社區發現算法其基本思想是對一個邊社區結構進行編碼,然後求出最小的平均編碼長度對應的最好的社區劃分,該方法的速度較快,但對於規模較小的邊社區並不適用。Ye利用Fast Unfolding算法先找出非重疊的節點型社區,然後根據邊兩端節點的類別來確定這條邊的歸屬,其工作證明了針對節點的社區發現算法都可以套用到對邊社區的發現上來,但缺點是計算過程較複雜,通常需要多次轉換。
