一種基于非支配排序遺傳算法的社區發現算法

管文蔚，王艷兵

(徽商職業學院 電子信息系，安徽 合肥 230000)

在社區發現算法中，一般采用模塊度來衡量社區劃分結果的好壞程度[1]。模塊度函數是由Newman和Girvan提出的一種用于評估社區劃分的全局目標函數[2]。然而，由于受到模塊度分辨率的限制，通常社區劃分的結果是否最佳不能完全取決于模塊化結果[3]。為解決此問題，文獻[4]基于模塊度密度的概念，克服了模塊度分辨率極限問題。為了實現一次性得到不同分辨率下的社區發現結果，本文嘗試優化模塊度密度函數。擴展模塊度密度是發現算法ratio association[5]與ratio cut[6]的凸組合，需要在不同參數設置下進行大量實驗來克服分辨率限制問題。

對于擴展模塊度密度，由于文獻[4]中可調參數λ的加入，ratio association與ratio cut本身存在一定不足，各自分別趨向于發現大社區網絡和小社區網絡，這種特性很好地符合了多目標優化的定義。因此，這里將采用啟發式算法中的一種基于非支配排序遺傳算法嘗試解決基于復雜網絡中的社區發現問題，實現一次性得到多種不同分辨率的社區發現結果，以供決策者進行選擇。因此，如何在減少計算量的情況下，盡可能多地得到不同分辨率下的社區發現結果是本文研究的重點。

1 多目標進化算法

優化問題通常可以按照目標函數的個數來分類：如單目標優化問題(Single-Objective Optimization Problem)和多目標優化問題(Multi-objective Optimization Problem)。不同于單目標優化問題中僅有一個評測目標，多目標優化問題中包含多個目標函數。本文應用多目標優化算法解決社區發現問題，多目標優化問題通常具有相互矛盾的目標函數，并且多目標優化問題通常情況下是一系列互不支配的解，而沒有單一的全局最優解，稱為帕累托(Pareto)解。這一點和單目標優化問題不同。

多目標優化問題可用公式(1)進行描述：

minimizeF(x)=(f1(x),…,fi(x),…,fk(x))

subjecttogi(x)≤0,i=1,2,…,p

hj(x)=0,j=p+1,p+2,…,m

(1)

其中，x=(x1,x2,…,xn)∈Ω是定義域在Ω上的n維決策變量，fi(x)是第i個目標函數。約束條件共有m個，其中不等式約束條件設為gi(x)，共p個，等式約束條件設為hj(x)，共m-p個。

當且僅當以下條件成立時，向量u= (u1,…,un)，支配向量v= (v1,…,vn)，upv：

?i∈{1,2,…,k}∶fi(u)≤fi(v)∧?j∈{1,2,…,k}∶fj(u)

(2)

對于給定的多目標優化問題F(x)，Pareto最優解集P*定義為：

P*={x∈Ω|?x'∈Ω∶F(x')pF(x)}

(3)

對于F(x)和Pareto最優解集P*[7]，Pareto前沿(PF*)定義為：

PF*={F(x)|x∈P*}

(4)

2 基于NSGA-II的多目標社區發現

2.1 目標函數

在一個有|V|個節點和|E|條邊的無向圖G=(V,E)，鄰接矩陣為A。假定Vm和Vn為兩個不相交的子集，模塊度密度D定義為

(5)

之后，李珍萍等人擴展了模塊度密度的定義，在原有基礎上引入一個可調參數λ：

(6)

式(6)中，當λ= 1時，其特例為ratio association；當λ= 0時，其特例為ratio cut；當λ=0.5時，等價于模塊度密度D。優化ratio association的方法是將網絡劃分成若干小社區，而優化ratio cut的方法則是將網絡劃分成若干大社區[8]。對于擴展模塊度密度，可通過調節參數λ的值，分析不同分辨率下的網絡拓撲結構，克服分辨率限制問題。因此，我們可以簡單地將這兩個函數拆分開來，進行同時優化，就可以得到一組Pareto解，這樣我們的兩個目標函數可以設計為以下兩個公式：

(7)

2.2 初始化

由于訓練樣本本身沒有圖的結構，所以在初始化時首先建立一個最小生成樹(MST)，最小生成樹能包含所有的節點且圖中不存在回路。MST將相似度高的解連接在一起而相似度低的解則沒有連接。當在圖中移除兩個節點之間的邊時就會形成新的子圖，一個含有K個社區劃分的圖需要移除K-1條邊。在初始化過程中，每個個體首先移除一條邊，當種群個體數超過邊數時，接著隨機移除第二條邊，并以此類推。決定一條邊是否移除時主要考慮節點之間邊的權重，權重越大，移除的可能性就越大。這樣能保證得到一組相對高質量的初始解。

2.3 交叉

在交叉這一步中，采用均勻交叉算子來產生新的個體，這種交叉方式對父代沒有偏好且能夠繼承父代的結構特點但又與父代結構不同。首先，隨機產生一個長度為N取值范圍為{0,1}的標志mask來決定子代的基因型取決于哪個父代。當mask(i)為0時，子代的第i位基因型繼承父代a,否則繼承b。

2.4 變異

當隨機更改節點之間的連接時會導致算法效率不高，因為對于一個大小為N的數據集，隨機更改節點之間的連接時的搜索空間為NN，所以我們有必要有目的性地更改這些連接。在本文中，這里采用近鄰偏好變異方式來減小搜索空間。在近鄰偏好變異機制中，個體的第i個基因位gi根據節點i與其他節點之間的連接的權重大小排序來進行變異，而且變異后只允許與L-近鄰(L<

(8)

在一個大小為N的數據集中，對于兩個節點i和j，它們分別與各自的l1-近鄰和l2-近鄰相連，且l1>l2，特別是當與j相連的節點屬于它的L-近鄰之一時，那么節點i相對更容易變異。在近鄰偏好的變異策略中，一個與其l-近鄰相連的節點的變異概率定義為公式(8)。這樣，節點i就能獲得比節點j更高的變異率。

2.5 算法描述

基于NSGA-Ⅱ的社區算法描述見表1。

表1 基于NSGA-Ⅱ的社區發現算法流程

3 實驗結果及分析

3.1 參數設置

本文所提算法需要設置的參數如表2所示：

表2 基于NSGA-Ⅱ的社區發現算法參數設置

3.2 現實網絡舉例

這里將基于非支配排序遺傳算法的社區發現方法用于社會學家Zachary的空手道俱樂部社會關系數據集(稱為karate數據集)和USA大學生足球聯賽俱樂部社交網絡數據集(稱為football數據集)，接著利用標準互信息指標(簡稱NMI)進行測試，并展示了社區關系網絡發現結果。

圖1 真實社區結構1(Zachary空手道俱樂部成員網絡)

空手道俱樂部網絡是由社會學家Zachary用了兩年時間在大學空手道俱樂部中觀察34名俱樂部成員之間的社會關系網絡[9-10]。最后，一個社區變成了兩個社區，如圖1所示。這主要是因為空手道教練辭職后有部分隊員與教練一同離開，形成了新的社交關系網絡。

USA大學生足球聯賽俱樂部社交網絡數據集是Newman和Girvan兩人觀察的2000年秋 季USA大學生足球聯賽常規賽季 的比賽網絡數據[11-12]，根據賽區劃分將球隊分成115個節點，因此，網絡中每個節點表示一個球隊，兩個節點之 間進行的比賽由 網絡中的連接線表示。每個節點在常規賽季中平均要有11條連接線，包括7條賽區 內的連接和4條賽區間的連接。該社交網絡數據集中共有115個球隊和616場比賽，所有的球隊被劃分成12個賽區，也就是12個社區。

首先，我們將對基于NSGA-II的社區發現算法所得PF

(Pareto Frontier)圖進行分析，如圖2。由圖中可以看出，算法在兩組測試網絡上都能得到一組非支配解，每一個非支配解都對應了一個Dλ混合參數。值得說明的是，并不是所有的解都對應不同的混合參數，在PF圖中互為近鄰的解可能對應相同的混合參數。如此一來，一組PF解救對應了不同分辨率下的社區劃分。由于在多目標算法中，優化ratio association的算法和優化ratio cut的算法被同時考慮。因此，所得結果為優化這組函數的折中解，決策者可以根據自身需要，選擇不同分辨率下的社區劃分結果。

(a)算法在karate網絡所得PF (b)算法在football網絡所得PF

為了進一步證明本算法的有效性，這里隨機選取算法在karate網絡上所得解并給出其對應的社區劃分情況，如圖3。圖3(a)與(b)得到了與真實劃分一致的解，(c)中所得劃分得到了三個社區，其中將原有的一個大社區分為了兩個，(d)所得劃分與(c)類似，同樣是將大的社區劃分為兩個小社區。如此一來，我們可以根據決策者的需要選取合適的劃分，這也是采用多目標算法進行優化社區發現的最主要的優點。

圖3 隨機選取Karate網絡PF中的解對應的社區劃分情況

4 結語

本文提出了一種基于非支配排序遺傳算法的社區發現方法。在復雜網絡中，一個社區內不同節點間的連接比較緊密，而不同社區之間節點間的連接相對來說更加稀疏。所以，可以采取兩個不同文中所采用的目標函數的物理意義。基于這點考慮，就從多目標優化的角度來解決復雜網絡社區發現問題。本算法主要優勢如下：(1)采用多目標實現社區發現；(2)社區數目自適應；(3)決策者根據自身需要選取合適的社區數目，無需固定。并且實驗證明了采用基于NSGA-II算法進行社區發現的有效性。