網(wǎng)絡社團GN算法研究

摘要：隨著復雜網(wǎng)絡社團理論研究的不斷深入，尋找和分析社團結構對于反映和理解網(wǎng)絡的構成具有重要的意義。本文針對社團結構檢測問題，簡要描述了社團結構的基本概念及其衡量標準，在廣度優(yōu)先搜索策略和隊列的應用基礎上，實現(xiàn)了一個用于快速查找社團結構的GN算法。關鍵詞：復雜網(wǎng)絡；社團結構；社團檢測；可視化實驗平臺Abstract:Alongwiththecomplexnetworktheorythedeepeningoftheresearchcommunity,seekingandanalysisforreflectingthecommunitystructureandunderstandthestructureofthenetworkhasanimportantsignificance.thisarticleinviewofthecommunitystructuretodetectproblems,thispaperbrieflydescribesthebasicconceptofcommunitystructureanditsmeasures,inthebreadthfirstsearchstrategyandqueueofapplicationbasis,throughthejavalanguageimplementsausedtoquicklyfindthecommunitystructreGNalgorithm.Keywords：complexnetwork;communitystructure;communitydetection;experimentalplatform1引言近年來，隨著小世界模型與無標度模型的提出，復雜網(wǎng)絡的研究不再局限于數(shù)學的范疇，逐漸受到生物學、計算機科學、社會學、統(tǒng)計物理學和經(jīng)濟學等多個領域的廣泛關注，并且表現(xiàn)出了一定的應用價值。在研究過程中，人們發(fā)現(xiàn)許多實際網(wǎng)絡都具有一個共同的特性，人們稱之為網(wǎng)絡中的社團結構[1,2,3,4]。在探索復雜網(wǎng)絡的結構中，單純的描述性的定義無法直接應用，算法對網(wǎng)絡的社團結構并沒有一個量的描述。因此，不能直接從網(wǎng)絡的拓撲結構來判斷它所求得的社團是否是實際的網(wǎng)絡中的社團結構，從而需要一些附加的關于網(wǎng)絡意義的信息來判斷所得到的社團結構是否具有實際的意義[5,6,7]。本文針對復雜網(wǎng)絡中相互獨立的社團結構檢測問題進行研究，在深入理解GN社團檢測算法的基礎上，介紹了GN算法的設計并從理論上對算法的思想進行了分析，同時，本文設計實現(xiàn)了一個用于社團結構檢測算法實驗的可視化平臺，該平臺集成了使用Java語言實現(xiàn)的GN算法，并對此進行了分析實現(xiàn)。2算法描述在社團結構檢測算法中，劃分得較好的社團，內(nèi)部連接的稠密程度應該高于隨機連接網(wǎng)絡的期望水平。下面用函數(shù)定量描述社團劃分的模塊化程度。假設復雜網(wǎng)絡已經(jīng)被劃分成個社團，那么先定義一個維的對稱矩陣，其中的元素表示連接社團和社團中的節(jié)點的邊占所有邊的比例，這個矩陣的跡表示網(wǎng)絡中所有連接社團內(nèi)部節(jié)點的邊占總邊數(shù)的比例，定義列（或者行）的加總值來表示所有連接了社團中的節(jié)點的邊占總邊數(shù)的比例[8,9.10]。由和的定義可知，從而，函數(shù)可以表達為:其中，“”為矩陣的模，即中元素的加總。如果社團內(nèi)部節(jié)點間的邊沒有隨機連接得到的邊多，則函數(shù)的值為負。當函數(shù)的值趨于1時，表明社團結構劃分的相當好。在實際應用中，的值一般處于0.3～0.7之間。GN方法就是一種代表性的分裂方法，它的基本思想是不斷地從網(wǎng)絡中移除介數(shù)最大的邊，邊介數(shù)的定義是網(wǎng)絡中經(jīng)過每條邊的最短路徑的數(shù)目，邊介數(shù)為區(qū)分一個社團的內(nèi)部邊和連接社團之間的邊提供了一種有效的衡量標準[6]。GN算法的基本流程如下：(1)計算網(wǎng)絡中各條邊的邊介數(shù)；(2)找到邊介數(shù)最大的邊并將它從網(wǎng)絡中移除；(3)重新計算網(wǎng)絡中剩余各條邊的邊介數(shù)；(4)重復步驟(2)和(3)，直到每個節(jié)點是一個單獨的社團為止。3社團結構搜索策略分析在網(wǎng)絡搜索過程中，每個節(jié)點都清楚的知道其他各個節(jié)點上存儲的信息，并且清楚怎么在最短的路徑內(nèi)到達對方，那么消息就可以從源節(jié)點依次經(jīng)過最短路徑上的各個節(jié)點，一直傳遞到目標節(jié)點。然而，在許多實際的網(wǎng)絡中，單個節(jié)點是無法充分了解整個網(wǎng)絡的全局結構的，更無法充分掌握目標節(jié)點在網(wǎng)絡中的具體位置，此時，一個最簡單的搜索策略就是廣播搜索策略，也就是廣度優(yōu)先搜索（breadth-firstsearch,BFS）策略。當源節(jié)點s應用BFS策略在網(wǎng)絡的節(jié)點上尋找指定的信息時，源節(jié)點s首先查找自身所有的鄰居節(jié)點，詢問是否含有目標信息，如果s的鄰居節(jié)點中有節(jié)點存儲了目標信息，則將目標信息返回給源節(jié)點，如果沒有鄰居含有目標信息，則所有的鄰居將查詢繼續(xù)傳遞給各自的鄰居節(jié)點，直至搜索到目標信息為止。查詢過程如圖1所示。 t t s s t t s s圖1BFS搜索源節(jié)點s到目標節(jié)點t的路徑經(jīng)分析發(fā)現(xiàn)，我們可以利用BFS策略來獲取任意兩個節(jié)點之間的最短路徑，即假設從一個源節(jié)點出發(fā)，令此節(jié)點與所有鄰居節(jié)點之間的距離為1，所有鄰居的鄰居節(jié)點與源節(jié)點的距離為2，以此類推。從而，如圖1中運用BFS策略所得到的源節(jié)點s與目標節(jié)點t之間的路徑長度就等于兩節(jié)點之間的最短路徑長度[9]。并且由于查詢是并行進行的，故搜索范圍將以幾何級數(shù)的方式進行增長，即短短幾步之內(nèi)查詢就將遍布整個網(wǎng)絡，使得搜索速度方便快速。4GN算法實現(xiàn)假設一個圖的節(jié)點數(shù)為，邊數(shù)為，每進行一次廣度優(yōu)先搜索就可以得到一個節(jié)點與其他各節(jié)點間的所有最短路徑，且算法復雜度為。假設每個源節(jié)點與其他節(jié)點之間只存在一條最短路徑，所有這些最短路徑就構成了一棵最短路徑樹[5]，如圖2。利用這棵樹，對這些路徑中的每一條邊分析其邊介數(shù)。首先，找到這棵樹的葉子節(jié)點，即那些不被其他任何節(jié)點間的最短路徑通過的節(jié)點，我們?yōu)檫@棵樹中每一條與這些葉節(jié)點相連的邊賦值為1；然后，從與樹的源節(jié)點距離最遠的一條邊開始，逐漸上移，依次為每一條邊賦值，其值為緊接在該邊下的所有臨邊的值之和再加1。按照這個規(guī)則，直到遍歷這棵樹上所有的邊，這些邊的值即為它相對于某個源節(jié)點的介數(shù)，對所有可能的源節(jié)點重復進行這個過程，然后把這些邊每次的值相加，最終結果即為所有節(jié)點對之間最短路徑的邊介數(shù)。廣度優(yōu)先搜索和遍歷樹的所有邊并且為其賦值這兩個過程在最壞的情況下算法的復雜度為，而整個網(wǎng)絡共有ｎ個節(jié)點，因此總體上講這種算法的復雜度為[7]。 s s12 4 11/6 25/6 1125/65/6 7/3 2 112/31/31葉子節(jié)點 31(b)圖2邊介數(shù)的計算5.GN算法實例利用GN算法分析空手道俱樂部網(wǎng)絡，俱樂部的人員形成人際關系網(wǎng)，如圖3所示。利用GN算法分析關系網(wǎng)，網(wǎng)絡被分為兩個社團，結果如圖3示。當網(wǎng)絡分為兩個社團時，模塊度有一個極大值，這表明這個網(wǎng)絡自然地分裂成這種情況。另外，若將分裂后各成員屬于哪一個子俱樂部作為該俱樂部實際的分裂情況，可以發(fā)現(xiàn)，利用這些算法所得到的網(wǎng)絡劃分形式與實際分裂情況幾乎是完全一樣的。只有一個節(jié)點3，沒有被正確的歸類，而我們仔細觀察可以發(fā)現(xiàn)，3本身就位于邊界地帶，本身就有歧義性。圖3空手道俱樂部社會關系網(wǎng)103334243192321191615263227252829341421822201813127176511圖4空手道俱樂部網(wǎng)絡樹狀結構6.結論隨著復雜網(wǎng)絡的飛速發(fā)展，復雜網(wǎng)絡所具有的社團結構特征引起了人們越來越多的關注。對社團結構進行分析研究具有重要的理論意義和應用價值，有助于幫助人們更好地理解和掌握網(wǎng)絡結構功能等多方面的特性，基于這一原因，查找和檢測社團結構成為我們研究網(wǎng)絡的基礎。只有選擇一個先進、高效、經(jīng)濟、實用的社團結構查找算法，才能跟上人們對復雜網(wǎng)絡研究水平的不斷提高。本設計針對網(wǎng)絡中相互獨立的社團結構檢測問題進行研究，對社團結構的對稱特性做出簡要概述，在此基礎上，綜合介紹了復雜網(wǎng)絡以及社團結構的基本概念和衡量標準，并且對目前比較常用的經(jīng)典全局和局部社團檢測算法給以比較評價。參考文獻[1]王立敏,高學東．基于最大節(jié)點接近度的局部社團結構探測算法［J］．計算機工程，2010.[2]汪小帆．復雜網(wǎng)絡的一種快速局部社團劃分算法［J］．計算機仿真，2007.[3]楊博,劉大有.復雜網(wǎng)絡聚類方法［J］．軟件學報,2009.[4]劉紹海，劉青昆.復雜網(wǎng)絡基于局部模塊度的社團劃分方法［J］．計算機工程與設計,2009.[5]汪小帆，李翔，陳關榮.復雜網(wǎng)絡理論及其應用［M］．北京：清華大學出版社,2006.