管文蔚，王艷兵

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

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

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

1 多目標進化算法

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

多目標優(yōu)化問題可用公式(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個目標函數(shù)。約束條件共有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)

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

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

(3)

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

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

(4)

2 基于NSGA-II的多目標社區(qū)發(fā)現(xiàn)

2.1 目標函數(shù)

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

(5)

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

(6)

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

(7)

2.2 初始化

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

2.3 交叉

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

2.4 變異

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

(8)

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

2.5 算法描述

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

表1 基于NSGA-Ⅱ的社區(qū)發(fā)現(xiàn)算法流程

3 實驗結(jié)果及分析

3.1 參數(shù)設置

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

表2 基于NSGA-Ⅱ的社區(qū)發(fā)現(xiàn)算法參數(shù)設置

3.2 現(xiàn)實網(wǎng)絡舉例

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

圖1 真實社區(qū)結(jié)構(gòu)1(Zachary空手道俱樂部成員網(wǎng)絡)

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

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

首先，我們將對基于NSGA-II的社區(qū)發(fā)現(xiàn)算法所得PF

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

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

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

圖3 隨機選取Karate網(wǎng)絡PF中的解對應的社區(qū)劃分情況

4 結(jié)語

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