1、社區劃分算法GNGN算法什么是社區劃分現實生活中存在著各種各樣的網絡系統，如人際關系網、合作網、交通運輸網、計算機網等。由于這種網絡是真實復雜系統的拓撲抽象，因此它被稱為復雜網絡。通常整個網絡是由若干個“群（group）”或“團（cluster）”構成的。每個群內部的節點之間的連接相對非常緊密，但是各個群之間的連接相對來說卻比較稀疏。如下圖所示。圖中的網絡包含三個社團，分別對應圖中三個圓圈包圍的部分。在這些社團內部，節點之間的聯系非常緊密，而社團之間的聯系就稀疏的多。社區劃分就是在大型復雜網絡中進行社區搜尋或發現社區。GNGN算法介紹 GN算法是一個經典的社區發現算法，它屬于分裂的層次聚類算法

2、。其基本思想是不斷的刪除網絡中具有相對于所有源節點的最大的邊介數(ege betweenness)的邊，然后，再重新計算網絡中剩余的邊的相對于所有源節點的邊介數，重復這個過程，直到網絡中，所有邊都被刪除。二、G-N G-N 算法的思想流程如下： 1、計算網絡中所有邊的邊介數。 2、找到邊介數最高的邊并將它從網絡中移除。 3、重復步驟1,2，直到每個節點就是一個退化的社區為止。邊介數定義和計算 最短路徑邊介數方法是一種最簡單的邊介數度量方法，一條邊的邊介數(betweenness)是指從某個源節點 S 出發通過該邊的最短路徑的數目，對所有可能的源節點，重復做同樣的計算，并將得到的相對于各個不同的

3、源節點的邊介數(betweenness)相加，所得的累加和為該邊相對于所有源節點的邊介數。 假設有一個具有 m 條邊和 n 個節點的圖，考慮一種比較簡單的情況，假設從任何一個源節點出發，對該圖進行搜索，該源節點與其它節點之間都只存在一條最短路徑，圖中的所有最短路徑構成一個最短路徑樹。利用這顆最短路徑樹來計算每條邊的邊介數。1，找到這棵樹的葉子節點，并為每條與葉子節點相連的邊賦值為 1 ；2，按照自下而上的方向為該搜索樹中的每條邊賦值，從與源節點 S 之間距離最遠的邊開始，其值等于位于該邊之下的所有鄰邊的值之和再加上 1；3，按照這種賦值方式，對搜索樹中的所有邊進行遍歷，那么每條邊的相對于某個源

4、節點 S的邊介數就是該邊的值，對于所有可能的源節點，我們都重復上述過程；4，將每條邊的相對于各個源節點的邊介數相加 ， 最終結果就是每條邊的相對于各個源節點的邊介數，即所有節點對間的最短路徑的邊介數。111242但是，在大多數的實際網絡中，每個源節點與其它節點之間并不只是存在一條最短路徑， 一些節點對之間存在若干條長度相等的最短路徑。從源節點 S 出發，為每個節點 i賦值，該值為從一個源節點 S 出發到達其它節點 i 的最路徑的數目用 wi表示。具體步驟如下:1. 定義源節點 S 的距離為 ds= 0，并賦予一個權值為 ws= 1。2. 對于每一個與源節點 S 相鄰的節點 i，定義它到源節點的

5、距離為di=ds+1 ，以及該節點的權值為 wi= ws= 1。3. 對于每一個與任意節點 i 相鄰的節點 j，我們根據具體情況，采取以下三個步驟之一： 如果節點 j 沒有被指定距離，那么，指定其距離為 dj= di+1，權值為 wj= wi；如果已經指定了節點 j的距離，并且節點 j 的距離值為 dj= di+1，那么就要在原來的基礎上將節點 j 的權值再增加 wi，使其權值為wj，即 wj wj+wi；如果已經指定了節點 j 的距離，并且距離為 dj di+1，那么，直接執行步驟 4。4. 重復執行第 3 個步驟，一直到網絡中不存在滿足以下條件的節點，即其本身已經被指定了距離，但是其鄰接點

6、卻沒有被指定距離。(1,1)(0,1)(1,1)(2,1)(2,1)(2,2)(3,2)(3,1)(3,3)(1,1)(0,1)(1,1)(2,1)(2,2)(3,1)(3,3)從節點 j 經過節點 i 到達源節點的最短路徑的數目與節點 j 到達源節點的最短路徑的數目之比為 wi/wj，對于源節點 S，應該采取以下步驟計算邊界數：1. 找到所有的葉子節點 f，該葉子節點 f 不被任何從源節點出發到達其它任何節點的最短路徑所經過。2. 假設葉子節點 f 與節點 i 相鄰，那么就將權值 wi/wf賦給從節點 f 到節點 i 的的邊。3. 從距離源節點 S 最遠的邊開始，從下至上直到源節點 S為從節點 i 到節點 j 的邊賦值為位于該邊之下的所有鄰邊的權值之和再加上 1，然后，再將其和乘以 wi/wj，最后的結果就是該邊的邊介數。4. 重復步驟 3，直到遍歷圖中的所有節點。11/3(1+1/3+1)*12