一種基于非支配排序遺傳算法的社區(qū)發(fā)現(xiàn)算法

管文蔚，王艷兵

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

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

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

1 多目標(biāo)進(jìn)化算法

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

多目標(biāo)優(yōu)化問(wèn)題可用公式(1)進(jìn)行描述：

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個(gè)目標(biāo)函數(shù)。約束條件共有m個(gè)，其中不等式約束條件設(shè)為gi(x)，共p個(gè)，等式約束條件設(shè)為hj(x)，共m-p個(gè)。

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

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

(2)

對(duì)于給定的多目標(biāo)優(yōu)化問(wèn)題F(x)，Pareto最優(yōu)解集P*定義為：

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

(3)

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

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

(4)

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

2.1 目標(biāo)函數(shù)

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

(5)

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

(6)

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

(7)

2.2 初始化

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

2.3 交叉

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

2.4 變異

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

(8)

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

2.5 算法描述

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

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

3 實(shí)驗(yàn)結(jié)果及分析

3.1 參數(shù)設(shè)置

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

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

3.2 現(xiàn)實(shí)網(wǎng)絡(luò)舉例

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

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

空手道俱樂(lè)部網(wǎng)絡(luò)是由社會(huì)學(xué)家Zachary用了兩年時(shí)間在大學(xué)空手道俱樂(lè)部中觀察34名俱樂(lè)部成員之間的社會(huì)關(guān)系網(wǎng)絡(luò)[9-10]。最后，一個(gè)社區(qū)變成了兩個(gè)社區(qū)，如圖1所示。這主要是因?yàn)榭帐值澜叹氜o職后有部分隊(duì)員與教練一同離開(kāi)，形成了新的社交關(guān)系網(wǎng)絡(luò)。

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

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

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

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

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

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

4 結(jié)語(yǔ)

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