一種新的在線社交網絡社區發現算法

何道兵，劉小洋，丁 楠

(重慶理工大學計算機科學與工程學院，重慶400054)

1 前言

在線社交網絡社區發現研究算法，隨著時代的發展，已經成為了一個值得深入研究的科學問題。社交網絡現在已經成為了人們生活不可缺少的一部分，是對現實關系的一個映射，是基于互聯網和通信平臺形成的一個大數據網絡。對網絡數據和結構的認識[1-3]，能讓人們更好的理解網絡上事物發生過程，使人們更好的設計、控制網絡。而虛擬社區的發現作為網絡科學的經典問題，讓眾多學者不斷地追尋探索[4-7]。研究發現在現實中包含著各種多樣的網絡，就像社交、技術、生物等方面因某種關系而產生網絡，這些網絡都具有一個共同特性就是社區結構。同一特性節點以及它們的關系連邊所構成的圖便是網絡社區，不同的社區連接組成社交網絡，社區內部連接邊比社區之間連接邊往往更加稠密。社區結構是社交網絡的重要結構特征之一[8-12]，它代表了真實網絡的異質性和模塊化的特點，它在網絡的功能和拓撲分析中發揮著重要作用。此外，社交網絡通常在社區上會展現出單個節點和整個網絡所不具備的特點。因此，對社會網絡社區發現算法的研究在很多方面具有重要意義[13-16]。

本文為了克服傳統的社交網絡社區發現算法僅僅是從數學理論上進行分析的不足之處，采用微博用戶數據集和karate數據集上進行社區劃分，運用了凝聚思想并引入模塊度增量的概念來構建社交網絡社區發現算法。

2 相關工作

在最近幾年中，復雜網絡中社區結構的發現和分析越來越受到社會的重視，已經出現了許多社區發現算法。自Girvan和Newman提出 GN 算法以來由計算機科學、物理學以及數學等多個學科發展出許多社區發現的算法，并廣泛應用于各個科學領域的具體問題中[17-19]。

在最開始大家的理解，社區指的是在一個系統中某些個體因為有一些共同點或者相似點，分析而形成在外部稀疏且在內部緊密的連接結構。非重疊社區發現是一種硬劃分，其中每個節點只能屬于一個社區，社區之間沒有交集。非重疊社區研究主要有傳統方法的譜方法以及基于模塊度的GN算法，對于非重疊社區發現算法的研究主要歸功于Girvan與Newman在2002年的開創性研究工作[20-22]。

在真實的社交網絡中，人們往往同時屬于不同的社區，并且屬于多個社區的人。一方面，重疊節點是網絡中關鍵點，重疊社區因此而產生聯系；另一方面，重疊社區反映了更加真實的網絡結構[7]。因此，對重疊社區進行發現和研究是更符合現實網絡的真實性的，更具有社會價值，更應引起研究者的重視和關注。重疊社區發現方法主要有以下幾類：基于派系過濾的重疊社區發現算法，基于局部擴張及優化的方法，基于線圖/邊社區的發現方法。隨著近十多年來的研究和發展，社區發現研究的重點一直都在發生改變，根據當前互聯網技術驅動的社交網絡環境中的網絡拓撲和社區結構特征，社區發現的研究仍然面臨著若干的挑戰性問題[23-24]。

3 傳統社區發現算法

3.1 采用分裂思想的算法

在2002年由Girvan和Newman提出的分裂算法，現如今已經成為了社區發現算法的一大經典算法，就是GN算法[25-26]。眾所周知，社區與社區之間的聯系相對來說較為稀疏，這也就代表著社區與社區之間的溝通渠道相對較少，因此一個社區與另一個社區需要通過這些溝通渠道中的至少一個。如果能夠從中找到這些較為重要的溝通通道并且進行移除的話，那么網絡就自然而然地會進行社區劃分。Girvan和Newman提出了使用邊介數來對每條邊的網絡連通重要性進行記錄，在對網絡結構進行社區發現過程中，分析時需要關心網絡圖是有向邊還是無向邊，是正權邊還是負權邊，頂點是否存在自環的可能。邊介數指的是網絡中的頂點間的最短路徑經過該邊的次數，對于無權圖，最短路徑是頂點之間數量最少的邊，而有權圖中為兩點之間權值和最少的連邊。邊介數的數學公式定義見式(1)。

(1)

其中的σst(v)表示的是從上s→t最短路徑上經過了節點v的最短路徑數，σst表示了s→t上的最短路徑數。每次需要找到s節點到v節點的最短路徑上v的前驅節點集合，因為s到v的最短路徑上一定會經過v的某前驅節點。在計算最短路徑上。可以對無權圖調用BFS廣度優先遍歷算法，對有權圖調用Dijkstra算法[26-27]。

該算法使用一個隊列來存放每次遍歷的節點，使用visited數組記錄該節點是否訪問過。初始時所有節點都未被訪問過，灰色節點為即將訪問的節點，先從第一個結點v1開始進行入隊操作并將該節點visited置為1表示已經訪問過。由于v1為隊頭元素，所以v1出隊并且鄰節點全部為待訪問節點，直到最后隊列為空退出循環，此時所有節點均已訪問過。

而Dijkstra只能計算單元最短路而且權值必須為正，該算法是基于貪心的思想。對每個節點進行一次遍歷就可計算出該節點到其它節點的最短路徑，通過集合S存放已找出的最短路徑，U集合存放還未找出的最短路徑的節點。每次通過在U集合中找出最短路徑的點然后加入S集合中，同時U集合進行更新。循環到遍歷結束后，U集合為空就得到該節點到每個連通節點的最短路徑。GN算法的基本流程如下。

1)根據網絡圖結構采用有效的最短路徑算法，計算出所有節點間的最短路徑，得出網絡中每條邊的邊介數。

2)找出所有邊介數中的最大值，當邊介數最大值唯一時將該邊介數進行移除，當邊介數最大值不唯一時，可以隨機選擇一條邊斷開，也可以同時將所有邊介數最大值的邊斷開。

3)移除邊后，對網絡中剩余的邊依據步驟1思路重新進行邊介數的計算。

4)對步驟2、3進行循環，當為網絡中所有的邊被移除時算法進行終止。

對GN算法使用karate數據集進行社區劃分后，對每次迭代后的模塊度進行統計，得到了圖1表示了GN算法過程中邊數量與模塊度值的關系。

圖1 GN算法社區劃分Q值分布

可以看出，當迭代到23次時才開始出現了劃分，因為前面每一次迭代邊劃分可能出現正好劃分成獨立社區，社區之間的相連邊均被刪除的情況。當迭代至29次時出現了社區模塊度巔峰值，取該模塊度下的社區劃分情況即為GN算法對karate數據集的最佳劃分。

圖2為在Q值分布中選擇了最大模塊度時的社區劃分情況，即為GN算法發現的社區劃分。可以看出，由于GN算法是刪除最大邊介數，在移除邊的過程中，會優先移除孤立點的，這也導致劃分過程中產生了較多的孤立點，如3.6中一共有21個社區存在，其中19個社區都是孤立社區。

圖2 GN社區劃分結果

3.2 采用聚合思想的算法

GN算法是針對全局性的，是對整體網絡結構進行劃分，而在現實的網絡結構中，全局性網絡數據是很難實現的，通過對局部網絡的分析才是更有效的社區發現算法。所以Newman基于貪心思想提出了基于模塊度最大化的貪心算法FN算法，該算法將全局的最優化分解成了局部最優化問題，通過找出每個小塊的局部最優值，最后將所有的局部最優值整理一起，變成全局的近似最優值。

貪心算法意味著在解決問題時始終做出當前時刻的最佳選擇。也就是說，并不會去考慮整體的最優性，從某方面來說，它是對局部最優解的選擇。并不是所有的問題都可以通過貪心算法得到整體的最優解，局部還是整體的最優關鍵還是進行貪婪算法時進行的策略選擇。要確保選擇的貪婪策略必須沒有后遺癥，也就是說某一狀態一定只和當前的狀態有著聯系，而并不會影響到未來的狀態[18]。貪婪的選擇意味著可以通過一系列局部最優選擇，即貪婪的選擇來實現對所尋求問題的整體最佳解決方案。貪婪的選擇是自頂向下連續地進行迭代選擇。每次做出貪婪的選擇時，問題就會減少到一個較小的子問題。貪婪算法的基本思想是從問題的初始解決方案一步一步地進行，根據優化措施，每個步驟必須確保可以獲得局部最優解。每個步驟只考慮一個數據，但是該選擇要能夠滿足獲得局部最優解的條件。如果下一個數據和部分最優解決方案不再是可行的解決方案時，則在枚舉完所有數據之前將數據添加到部分解決方案中，或者無法再添加的時候進行算法終止。FN算法最開始初始化的時候，將網絡中的所有的節點都看成一個單獨的社區，然后對所有的兩兩有聯系的社區合并進行考慮，計算出每次社區合并會導致的模塊度增量ΔQ。由貪心算法的原則可知，每次劃分只對模塊度增量的最大值和最小值的兩兩社區進行社區合并，一直迭代到當所有的節點都合并成為一個社區。FN算法的具體步驟如下所述。

1)網絡結構初始化，刪除掉網絡結構中的所有連接邊，然后將每一個節點都看作是一個獨立的社區。

2)將網絡中存在的有連通關系的節點劃分為一個社區。對于還沒有加入的網絡連通邊都重新添加回網絡結構中，若在網絡邊加入后，對兩個社區之間進行了連接那么對兩個社區進行合并，然后計算新的網絡結構進行社區劃分后的模塊度增量。每次只選取合并模塊度增量中的最大值或者減量中的最小值的兩個社區。

3)一直對步驟2進行循環迭代，直到社區劃分的社區數量值為1時。

4)對所有社區劃分模塊度值進行遍歷，尋找選擇具有最大模塊度的社區作為網絡的最佳劃分。

在FN算法的計算過程中，要注意每次進行模塊度計算的時候，都必須要在完整的網絡拓撲結構上，也就意味著在拓撲結構上包含了網絡中所有的邊。對FN算法使用karate數據集進行運算后，記錄每次添加邊后的Q值，分布結果如圖3所示。

圖3 FN算法社區發現Q值分布

從圖3的Q值分布圖可以看出，最開始將所有點看作單獨的社區此時模塊度為0，到最后所有節點在一個社區模塊度為0。該算法在每次迭代對所有可能邊進行添加，根據模塊度的增量增加最大減少最小原則，從而達到了社區分布的收斂。圖3中的Q值巔峰值就是社區劃分得最好結果，由圖可知，此時邊數添加為53條，根據結果記錄得到添加邊1和0時，得到53條邊的最優結果。取出最優解進行數據可視化，得到圖4。

圖4 FN算法結果示意圖

從可視化圖中可以很好看出，每種顏色為一個社區的劃分，karate數據集經過FN算法分為四個社區，此時是FN算法的最優解。對比前面GN算法的運行結果，存在許多的孤立點，FN算法的運行結果明顯更加可靠，而且運行時間更低，FN算法的步驟理解以及算法的實現都比GN算法更容易。

4 提出的MICDA算法

在MICDA算法中，新加入了一個模塊度增量ΔQ的概念，在對模塊度進行初始化的時候應該滿足式(2)。

(2)

式中，eij表示i、j社區邊連接的比例，初始所有節點單獨一個社區時，所有社區不相連，得出初始模塊度為0。在對模塊度增量進行初始化的時候，元素數據應該滿足下列數學式(3)。

(3)

式中，ki，in表示的最新構建圖i節點在社區C的權重之和，∑tot表示與社區C相連節點的邊的總權重，ki表示了i節點的總權重值。該公式比較復雜，對公式進行簡化后得到式(4)。

(4)

ki表示節點i的度，kj表示節點j的度，m表示網絡中當前結構所有邊的數量。提出的MICDA算法1如下。

算法1：提出的MICDA算法

Step1：對所有節點進行數據初始化，將每個節點i置于單獨的社區i中。

Step2：第一節點開始進行選擇，找到該節點的所有鄰居節點，根據式(4，3)計算出當該節點加入每一個鄰居社區時的ΔQ，如果ΔQ取值大于0就將鄰居節點劃分到當前節點社區中，否則保持原社區不改變。

Step3：對step2進行循環，迭代直達當前節點所在社區為穩定值。

Step4：每個社區劃分后，構建一個新的圖結構，將在同一個社區的節點全部看作一個新節點。新節點內部節點與節點之間的權重，看作新節點自環產生的權值。新節點與鄰居節點的權值為內部所有節點對該鄰居節點權值。完成新圖的構建后，重復step2直到模塊度Q取值最大時終止。

算法1中對步驟2、步驟3的一個節點迭代過程如圖5所示，對步驟4中新圖結構的構建如圖6所示。

圖5為MICDA算法的迭代示意圖，最初五個節點是獨立的五個社區，在經過步驟2的完全迭代后，發現2節點屬于1節點所在社區。此時進行新圖的構建，將節點1和節點2壓縮為一個新節點1，這時圖中只有四個節點存在。繼續對步驟2進行迭代，以此發現了節點3、4、5都可以歸到新節點1中，進行了三次新圖的構建后，得到全圖只有一個社區1存在，節點1、2、3、4、5都屬于社區1中，此時不再有節點社區發生改變結束迭代。

圖5 MICDA迭代過程圖

圖6 MICDA算法過程示意圖

圖6更詳細的解釋了MICDA的新圖的構建和權值的重新計算，MICDA算法的一次迭代分為模塊度優化和社區聚合兩個大步驟。模塊度優化為找到當前節點的所有鄰居節點，將模塊度增量大于0節點加入當前節點社區，上圖節點優化后分為了四個顏色社區。社區聚合就是將所有相同顏色節點歸為一個新節點，如紅色節點全部看作16號新節點，新節點自環權值為所有紅色節點權值。從圖4.2可以看出整個算法中最重要的一步就是社區聚合，將節點融合成新節點，并通過初始邊關系計算新的節點與邊權值。該方法的偽代碼如算法2。

算法2 MICDA構建新圖

輸入：cluser節點社區數組

輸出：聚合后新節點組成的圖結構new_edge

function rebuildGraph()

int[n] change

change_size ← 0

boolean[n] vis

for i=0→n do

if vis[cluster[i]] then

continue

vis[cluster[i]] ← true

change[change_size++] ← cluster[i]

end for

int[] index ← new int[n];

for i=0→change_size do

index[change[i]] ← i

end for

int new_n ← change_size;

for i=0 → global_n do

global_cluster[i] ← new_global_cluster[i]

end for

top ← new_top

for i=0 → m do

edge[i]=new_edge[i]

end for

for i=0 → new_n do

node_weight[i] ← new_node_weight[i]

head[i] ← new_head[i]

end for

n ← new_n

init_cluster()

end function

通過算法1和式(4)可以實現MICDA算法。對karate數據集使用MICDA算法后，得到MICDA算法的模塊度隨著迭代次數的分布情況如圖7所示。

圖7 karate社區劃分結果

圖7為每次迭代后當前模塊度值，由于MICDA算法每次添加邊不止一條，所以不像GN和FN算法可以曲線波動大，MICDA結果更加簡潔易于理解，根據模塊度峰值取社區劃分最佳情況，進行數據可視化得到圖8。

圖8 MICDA社區劃分結果圖

5 仿真結果與分析

5.1 時間復雜度

當存在用不同方法的算法去解決一個相同的問題的時候會有時間復雜度的分析，因為不同的算法好壞是會影響整個程序的效率的，而進行算法分析的意義在于選取合適的算法以及對劣質算法進行一定改善。對于算法，時間復雜度是定性地描述運行時間的函數，一般用大O符號進行表述。

圖9 微博用戶數據集社區發現時間復雜度比較

圖9為基于標簽傳播的LPA算法和COPRA算法時間復雜度對比圖，兩個算法均是對微博用戶地區數據集進行社區發現。由上圖可以看出由于LPA是非重疊社區發現算法，因此COPRA的時間復雜度比LPA更高。根據之前第三章得到的LPA和COPRA迭代次數圖，LPA的收斂性明顯更快COPRA。因此LPA的時間復雜度性能更好，但作為社區發現，COPRA是對重疊社區發現更具有實際意義。

圖10 karate數據集社區發現時間復雜度對比

圖10對COPRA算法、GN算法、FN算法以及MICDA算法的算法時間復雜度對比圖，以上算法采用源數據均是karate數據集。由上圖可以看出，GN算法的時間復雜度最高，MICDA算法時間復雜度最低。MICDA算法的時間復雜度性能得到了大大的提升，不管是對比基于模塊度最大化的經典算法還是基于標簽傳播的經典算法。

5.2 模塊度Q

一個適用性高的算法應該能夠識別良好的社區結構[19]。人們常用的對良好社區結構劃分得度量標準是模塊度函數，模塊化是目前常用的對網絡劃分穩定性進行度量的方法。模塊度最早是由Newman提出的一個適用性高的算法應該能夠識別良好的社區結構。人們常用的對良好社區結構劃分得度量標準是模塊度函數，模塊化是目前常用的對網絡劃分穩定性進行度量的方法。模塊化計算的意義在于，連接網絡中兩個不同類型節點的邊緣比例的預期比率減去在相同社區結構下任意連接兩個節點的邊緣比例[20]。在對劃分社區后進行當前社區結構的模塊度計算，如果當前社區結構的模塊度值越高，表示了該算法在當前劃分情況下是最可取的。

在進行模塊度計算的過程中，由于大多數的網絡結構是未知的，不會需要使用網絡已知的社區結構進行對比，因此模塊度用來作為社區劃分的評價指標是適用最廣泛的。

圖11為基于模塊度的GN和FN算法與改進后的MICDA算法分別對karate數據集進行社區發現后，模塊度分布圖中出現的巔峰值。可以看出，三個算法的劃分都在0.3～0.7之間取值正常，而GN算法發現的社區結構是比較差的，而改進后的MICDA算法發現的社區結構是最良好的。

圖11 算法模塊度對比

6 結論

本文針對社交網絡的社區發現進行了深入研究，將模塊度引入到社區發現檢測算法中，提出了一種改進的社交網絡社區發現算法。其主要工作有：①運用凝聚思想，從微博社交網絡中的節點開始，按照社區劃分的標準自底向上的凝聚成一個大社區；②新引入了一個模塊度增量的概念；采用微博社交網絡用戶數據集和karate數據集上進行社區劃分，并與傳統的社區發現算法GN和FN進行對比分析。③提出的算法使得代碼更易于實現，時間性能更高；提出的新算法在時間復雜度大大降低，降低為12%左右。

下一步將對社交網絡中的重疊社區進行分析和研究。