WSB-EA進(jìn)化算法的符號(hào)網(wǎng)絡(luò)弱結(jié)構(gòu)平衡分析

常新功，趙雅娟

（山西財(cái)經(jīng)大學(xué) 信息管理學(xué)院，山西 太原 030006）

符號(hào)網(wǎng)絡(luò)[1-2]是指具有正邊或負(fù)邊的網(wǎng)絡(luò)，其中正邊表示積極的、正面的意義，負(fù)邊表示消極的、負(fù)面的意義。在現(xiàn)實(shí)生活中，可以將很多網(wǎng)絡(luò)抽象為符號(hào)網(wǎng)絡(luò)。例如，國際關(guān)系網(wǎng)[3]中合作和敵對(duì)的關(guān)系、社交網(wǎng)絡(luò)[4]中朋友和敵人關(guān)系、生物網(wǎng)絡(luò)[5]中促進(jìn)和抑制作用等。1946年Heider[6]提出三角形關(guān)系中正關(guān)系與負(fù)關(guān)系的相互作用模式，將符號(hào)網(wǎng)絡(luò)帶入大家的視線。隨著符號(hào)網(wǎng)絡(luò)的興起，網(wǎng)絡(luò)的全局平衡性引起眾多學(xué)者的關(guān)注。根據(jù)計(jì)算得到的全局平衡性可以有效地進(jìn)行個(gè)性化推薦、態(tài)度預(yù)測(cè)等。一般全局平衡性用不平衡度來衡量，不平衡度是指一個(gè)網(wǎng)絡(luò)從不平衡到平衡的距離，若將這些引起不平衡的邊的符號(hào)取反，網(wǎng)絡(luò)就變?yōu)槠胶饩W(wǎng)絡(luò)。然而對(duì)于大多數(shù)符號(hào)網(wǎng)絡(luò)而言，結(jié)構(gòu)平衡定理太過嚴(yán)苛。Leskovec等[7]也證實(shí)了弱結(jié)構(gòu)平衡定理更適合真實(shí)網(wǎng)絡(luò)。因此本文從弱結(jié)構(gòu)平衡定理出發(fā)，來研究網(wǎng)絡(luò)的弱不平衡性。孫一翔[8]提出Meme-SB算法，將結(jié)構(gòu)平衡定理的能量函數(shù)作為適應(yīng)值函數(shù)，利用混合遺傳算法求得真實(shí)符號(hào)網(wǎng)絡(luò)的不平衡度。在Meme-SB算法基礎(chǔ)上，本文提出了WSB-EA算法，將研究范圍擴(kuò)展到符號(hào)網(wǎng)絡(luò)的弱不平衡性。即將弱結(jié)構(gòu)平衡定理的能量函數(shù)當(dāng)作適應(yīng)值函數(shù)，利用進(jìn)化算法原理，初始化種群，選擇、交叉、變異，最終得到網(wǎng)絡(luò)的弱不平衡度。4個(gè)小型數(shù)據(jù)集的實(shí)驗(yàn)表明，WSB-EA算法比其他算法能夠更快收斂得到最優(yōu)解。在實(shí)驗(yàn)最后部分計(jì)算得到兩大符號(hào)網(wǎng)絡(luò)Epinions和Slashdot的弱不平衡度。

1 背景知識(shí)

從20世紀(jì)40年代，Heider提出三角形關(guān)系中正關(guān)系與負(fù)關(guān)系的相互作用模式，到Cartwright等[9]用圖論語言描述這一理論將其推廣到整個(gè)網(wǎng)絡(luò)。越來越多的研究者對(duì)符號(hào)網(wǎng)絡(luò)的結(jié)構(gòu)和演化問題感興趣，致力于研究社會(huì)群體的派系結(jié)構(gòu)和發(fā)展過程。然而，有很大一部分真實(shí)網(wǎng)絡(luò)并不符合Heider提出的結(jié)構(gòu)平衡理論，由此Davis[10]放寬結(jié)構(gòu)平衡理論的約束條件，提出弱結(jié)構(gòu)平衡理論。

1.1 弱結(jié)構(gòu)平衡定理

符號(hào)網(wǎng)絡(luò)用數(shù)學(xué)符號(hào)G(V, E)表示，V表示網(wǎng)絡(luò)節(jié)點(diǎn)集合，E表示網(wǎng)絡(luò)邊的集合。其中任意一條邊，其符號(hào)為“+”或“–”?！?”代表節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的邊是積極關(guān)系，“–”則代表消極關(guān)系。Heider指出如果網(wǎng)絡(luò)中任意一個(gè)三角形的符號(hào)乘積為正，則網(wǎng)絡(luò)是平衡的。如圖1所示，(a)和(b)是平衡三角，(c)和(d)是不平衡三角。在此基礎(chǔ)上Cartwright和Harary等提出判斷符號(hào)網(wǎng)絡(luò)是否平衡的一個(gè)充要條件——“如果一個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)能夠被分割為兩個(gè)子集，每個(gè)子集內(nèi)的所有邊均是正邊，子集間的邊均為負(fù)邊，這樣的網(wǎng)絡(luò)就是平衡的?！?/p>

然而對(duì)于大多數(shù)符號(hào)網(wǎng)絡(luò)而言，結(jié)構(gòu)平衡定理的要求太過嚴(yán)苛。之后Davis放寬結(jié)構(gòu)平衡理論的約束條件，提出了弱結(jié)構(gòu)平衡理論。這一理論將圖1(d)三條邊都是負(fù)號(hào)這樣的三角結(jié)構(gòu)也認(rèn)為是平衡結(jié)構(gòu)。因此產(chǎn)生了一個(gè)新的概念，K-平衡網(wǎng)絡(luò)。這一理論認(rèn)為，一個(gè)符號(hào)網(wǎng)絡(luò)是弱平衡的，當(dāng)且僅當(dāng)可以將這一網(wǎng)絡(luò)中的節(jié)點(diǎn)分為k個(gè)子集，子集內(nèi)部都是正邊，子集之間都是負(fù)邊。結(jié)構(gòu)平衡定理是弱結(jié)構(gòu)平衡定理中k為2的特殊情況。K-平衡網(wǎng)絡(luò)的結(jié)構(gòu)如圖2所示，圖中集合內(nèi)部連邊都是正邊，集合之間連邊都是負(fù)邊。

圖1 符號(hào)網(wǎng)絡(luò)中4種三角形結(jié)構(gòu)[1]Fig. 1 Four triangle signed network structures[1]

圖2 弱結(jié)構(gòu)平衡網(wǎng)絡(luò)Fig. 2 Weak balance network structure

1.2 弱結(jié)構(gòu)平衡定理能量函數(shù)

根據(jù)弱結(jié)構(gòu)平衡定理，計(jì)算符號(hào)網(wǎng)絡(luò)的弱不平衡度就是尋找一種集合劃分，使得集合內(nèi)部之間的負(fù)邊數(shù)和集合外部之間的正邊數(shù)最少。例如，節(jié)點(diǎn)1和節(jié)點(diǎn)2之間的連邊為正，如果將這兩個(gè)節(jié)點(diǎn)分到同一個(gè)集合，這兩個(gè)節(jié)點(diǎn)就沒有對(duì)弱不平衡度做出“貢獻(xiàn)”，如果把它們分到不同的集合，就需要計(jì)算這兩個(gè)節(jié)點(diǎn)對(duì)弱不平衡度做的“貢獻(xiàn)”。同理，兩個(gè)節(jié)點(diǎn)之間的邊是負(fù)邊時(shí)，將其分到同一集合，也要計(jì)算這一部分的“貢獻(xiàn)”。因此計(jì)算弱不平衡度就是遍歷整個(gè)符號(hào)網(wǎng)絡(luò)，找到所有對(duì)弱不平衡度做出“貢獻(xiàn)”的節(jié)點(diǎn)對(duì)。由此提出弱結(jié)構(gòu)平衡定理的能量函數(shù)：

在弱結(jié)構(gòu)平衡定理中，一個(gè)無向符號(hào)網(wǎng)絡(luò)被分為k個(gè)子集。因此，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都有一個(gè)所屬的子集編號(hào)，在式中用si來表示這一編號(hào)。δ(si, sj)的計(jì)算結(jié)果由si和sj決定，如果si和sj的值相同則計(jì)算結(jié)果為+1，否則為–1。

由此，求解符號(hào)網(wǎng)絡(luò)的弱結(jié)構(gòu)平衡問題就轉(zhuǎn)變?yōu)樽钚』芰亢瘮?shù)的優(yōu)化問題。能量函數(shù)的最小值代表了導(dǎo)致符號(hào)網(wǎng)絡(luò)弱不平衡的最少邊的數(shù)目。若將這些邊的符號(hào)取反，可以將此網(wǎng)絡(luò)轉(zhuǎn)變?yōu)槿踅Y(jié)構(gòu)平衡網(wǎng)絡(luò)。如果能量函數(shù)值為0，說明此網(wǎng)絡(luò)已是弱結(jié)構(gòu)平衡網(wǎng)絡(luò)。

1.3 進(jìn)化算法

進(jìn)化算法[11-12]或稱演化算法(evolutionary algorithms, EAS)，是一個(gè)算法簇，它們產(chǎn)生的靈感都來自于大自然的生物進(jìn)化，但它有很多的變化，有不同的遺傳基因表達(dá)方式，不同的交叉和變異算子，特殊算子的引用，以及不同的再生和選擇方法。與傳統(tǒng)的基于微積分的方法和窮舉法等優(yōu)化算法相比，進(jìn)化計(jì)算是一種成熟的具有高魯棒性和廣泛適用性的全局優(yōu)化方法，具有自組織、自適應(yīng)、自學(xué)習(xí)的特性，能夠不受問題性質(zhì)的限制，有效地處理傳統(tǒng)優(yōu)化算法難以解決的復(fù)雜問題。

2 WSB-EA算法描述

2.1 WSB-EA算法主要流程

根據(jù)問題定義以及進(jìn)化算法原理，本文將弱結(jié)構(gòu)平衡定理的能量函數(shù)作為目標(biāo)函數(shù)，在Meme-SB算法的基礎(chǔ)上，初始化種群，經(jīng)過選擇、交叉、變異得到最優(yōu)解。具體框架如算法1所示。

算法1 WSB-EA算法

輸入 鄰接矩陣J，種群規(guī)模P，迭代次數(shù)M；輸出 最優(yōu)解的適應(yīng)值，即網(wǎng)絡(luò)弱不平衡度。

2) Pop←Population(P, true); //初始化種群

3) a=0;

4) repeat

5) individual = Pop.getFittest();//計(jì)算得到種群最優(yōu)個(gè)體

6) Pop←evolvePopulation(Pop, individual); //種群進(jìn)化，選擇、交叉、變異操作

7) a=a+1;

8) until a=M //達(dá)到最大進(jìn)化次數(shù)時(shí)停止

2.2 編碼

本文使用的編碼方式是整數(shù)編碼[13]。種群中的染色體由表示，其中n為符號(hào)網(wǎng)絡(luò)的節(jié)點(diǎn)個(gè)數(shù)，表示第i個(gè)節(jié)點(diǎn)所屬的子集編號(hào)。假設(shè)符號(hào)網(wǎng)絡(luò)中有k個(gè)子集，則的取值范圍是0 ～ k–1。例如第j個(gè)染色體可以表示成。

2.3 初始化

一般進(jìn)化算法中的初始化方法都是隨機(jī)產(chǎn)生每條染色體，但這樣的初始化方式效率不高。如果初始化的染色體對(duì)應(yīng)的適應(yīng)值很低，要經(jīng)過很多次迭代才能得到最優(yōu)解，收斂速度太慢。因此本文使用一種簡(jiǎn)單的啟發(fā)式方法，保證在初始化時(shí)每一個(gè)節(jié)點(diǎn)與它的鄰居節(jié)點(diǎn)對(duì)能量函數(shù)沒有“貢獻(xiàn)”。即在初始化之后，隨機(jī)選擇一個(gè)節(jié)點(diǎn)，如果此節(jié)點(diǎn)與它的鄰居節(jié)點(diǎn)對(duì)能量函數(shù)沒有“貢獻(xiàn)”，則不改變這一節(jié)點(diǎn)的取值，否則將其改為它的正鄰居節(jié)點(diǎn)所屬的子集編號(hào)。這樣的操作重復(fù)n次，并且保證每次選擇的節(jié)點(diǎn)是之前沒有選擇過的。

2.4 遺傳操作

本文的遺傳操作過程如算法2所示。遺傳過程分為3步：首先將上一代種群中的優(yōu)秀個(gè)體保存到新一代種群中，這個(gè)過程稱為精英保留；接下來利用錦標(biāo)賽方式選取父代染色體，經(jīng)過單路交叉；單點(diǎn)變異得到新一代種群。

算法2 evolvePopulation (individual)算法

輸入 原始種群Pop，最優(yōu)個(gè)體individual，錦標(biāo)賽規(guī)模tournamentSize，交叉概率uniformRate，變異概率mutationRate；

輸出 新一代種群newPop。

1) newPop.saveIndividua(0, individual); //精英保留

2) for( j=0; j＜ Pop.size(); j++)

3) indiv1 =tournamentSelection(Pop); //選擇父本1

4) indiv2 = tournamentSelection(Pop);

5) newIndiv=crossover(indiv1, indiv2); //交叉算法

6) newPop.saveIndividua ( j, newIndiv);

7) for( j=0; j＜ Pop.size(); j++)

8) mutate(newPop.getIndividual( j)); //變異算法

2.4.1 選擇操作

在進(jìn)化算法中輪盤賭是最常用也是最簡(jiǎn)單的選擇算子。但對(duì)于本文而言，輪盤賭不利于保持種群多樣性。為了解決這一問題，本文選用錦標(biāo)賽方法選取優(yōu)秀個(gè)體進(jìn)行繁衍。首先確定錦標(biāo)賽規(guī)模t，隨機(jī)從種群中選擇出t個(gè)個(gè)體，計(jì)算這些個(gè)體的適應(yīng)值，將適應(yīng)值最小的個(gè)體作為父代進(jìn)行繁衍。

2.4.2 交叉操作

一般在進(jìn)化算法中經(jīng)常使用的兩點(diǎn)交叉算子很有可能會(huì)破壞父代染色體中優(yōu)秀的基因結(jié)構(gòu)，因此為了保存父代染色體中的優(yōu)秀基因結(jié)構(gòu)，本文選擇單路交叉方式[14]作為交叉算子。首先通過錦標(biāo)賽選擇算法選擇兩個(gè)優(yōu)秀父代A、B。隨機(jī)產(chǎn)生一個(gè)0 ～ k–1的整數(shù)m，記錄A中所有m所在的位置，然后將B對(duì)應(yīng)位置的基因值改為m。例如，圖3中，每一條染色體有15個(gè)基因，選擇兩條父代染色體，隨機(jī)產(chǎn)生一個(gè)數(shù)2，將B中對(duì)應(yīng)位置的取值都改為2。

圖3 單路交叉Fig. 3 Single cross

2.4.3 變異操作

本文的變異算子是單點(diǎn)變異。從父代種群中隨機(jī)選擇一條染色體，然后從這一染色體中隨機(jī)選取一個(gè)基因，對(duì)其重新賦值，但要保證變異之后染色體的能量函數(shù)值沒有增加。這樣的操作要循環(huán)n次，因此變異也可以看作一種局部搜索，將染色體變異為它的鄰居染色體，試圖找到局部最優(yōu)的染色體。

2.5 符號(hào)網(wǎng)絡(luò)存儲(chǔ)

符號(hào)網(wǎng)絡(luò)在計(jì)算機(jī)中一般有3種存儲(chǔ)方式：鄰接矩陣、三元組和鏈表方式。鄰接矩陣是普遍使用的一種方式。然而對(duì)于大型符號(hào)網(wǎng)絡(luò)來說，鄰接矩陣達(dá)到105×105的數(shù)量級(jí)，存儲(chǔ)這樣的鄰接矩陣對(duì)內(nèi)存要求太高。因此本文選擇鄰接鏈表[15]來存儲(chǔ)網(wǎng)絡(luò)信息。首先為每一個(gè)節(jié)點(diǎn)都創(chuàng)建一條鏈表，頭結(jié)點(diǎn)是節(jié)點(diǎn)本身，后面鏈接與這一節(jié)點(diǎn)有聯(lián)系的節(jié)點(diǎn)信息，包括節(jié)點(diǎn)編號(hào)以及邊的符號(hào)。例如，圖4中，這一鏈表存儲(chǔ)節(jié)點(diǎn)1的連邊信息。節(jié)點(diǎn)1與節(jié)點(diǎn)2的連邊為1，節(jié)點(diǎn)1與節(jié)點(diǎn)6的連邊為–1。雖然每條邊都存儲(chǔ)了兩次，但相對(duì)于鄰接矩陣的存儲(chǔ)方式，大大降低了內(nèi)存占用。

圖4 二維鏈表示例Fig. 4 Two-dimension link structure

2.6 增量計(jì)算

在一般的遺傳算法中，每一次的交叉和變異之后都需重新計(jì)算一次適應(yīng)值，這樣重復(fù)操作使得算法的時(shí)間復(fù)雜度太高?；诖耍疚脑诙ɡ?的基礎(chǔ)上提出一種增量計(jì)算的方式，在重新計(jì)算適應(yīng)值時(shí)，只計(jì)算個(gè)體中因基因改變使得適應(yīng)值增減的部分。

定理1 假設(shè)個(gè)體ind在位置h處變異，sh由old變?yōu)閚ew，則個(gè)體ind的新適應(yīng)值h(ind)new為

由于式(2)等號(hào)右側(cè)第2部分在變異前后不變，所以

上述推導(dǎo)表明，當(dāng)個(gè)體ind在h位置變異后，新的適應(yīng)值通過舊適應(yīng)值加一個(gè)增量就可以得到，而這個(gè)增量只需要遍歷vh的鄰居節(jié)點(diǎn)就可以算出，這樣計(jì)算一個(gè)個(gè)體的適應(yīng)值的時(shí)間復(fù)雜度從O(m)降為O(davg)，其中davg為平均度數(shù)。

基于定理1，計(jì)算新的適應(yīng)值就可以簡(jiǎn)便為計(jì)算改變子集編號(hào)的節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)對(duì)適應(yīng)值的“貢獻(xiàn)”。具體分為兩種情況：1)原本對(duì)適應(yīng)值沒有“貢獻(xiàn)”的邊，在改變基因之后對(duì)適應(yīng)值有“貢獻(xiàn)”；2)原本對(duì)適應(yīng)值有“貢獻(xiàn)”的邊，在改變之后對(duì)適應(yīng)值沒有“貢獻(xiàn)”。增量計(jì)算大大地降低了時(shí)間復(fù)雜度，在交叉算法中的增量計(jì)算只需循環(huán)若干次，而在變異算法中只需運(yùn)行一次。

算法具體操作如算法3所示。算法第1行將increaseFitness設(shè)置為0，第2行是將c賦值為被改變基因所對(duì)應(yīng)的節(jié)點(diǎn)的鏈表頭結(jié)點(diǎn)，為了找到這個(gè)節(jié)點(diǎn)的所有鄰居，之后遍歷整個(gè)鏈表。算法第4 ～ 8行是在判斷鄰居為正鄰居之后，再次判斷如果鄰居的基因與舊基因相同，但與新基因不同時(shí)，increaseFitness加2；如果鄰居的基因與舊基因不同，但與新基因相同時(shí)，increaseFitness減2。算法第9 ～ 13行是在判斷鄰居為負(fù)鄰居之后，再次判斷如果鄰居的基因與舊基因相同，但與新基因不同時(shí)，increaseFitness減2；如果鄰居的基因與舊基因不同，但與新基因相同時(shí)，increaseFitness加2。

算法3 ncreaseFitness()算法

輸入 需要計(jì)算適應(yīng)值的個(gè)體individual，基因改變位置id，舊基因old，新基因new；

輸出 增加的適應(yīng)值increaseFitness。

1) increaseFitness=0；

2) c =Data.node[id].first;

3) 遍歷節(jié)點(diǎn)id的所有鄰居節(jié)點(diǎn)；

4) if (正鄰居)

5) if(getGene(c.data)==old&&getGene(c.data)!=new)

6) increaseFitness= increaseFitness+2；

7) else if(getGene(c.data)!=old&&getGene(c.data)==new)

8) increaseFitness= increaseFitness-2；

9) else if(負(fù)鄰居)

10) if(getGene(c.data)==old&&getGene (c.data)!=new)

11) increaseFitness= increaseFitness-2；

12) else if(getGene(c.data)!=old&&getGene(c.data) == new)

13) increaseFitness= increaseFitness+2；

2.7 復(fù)雜性分析

在整個(gè)算法中，時(shí)間復(fù)雜度最高的是遺傳操作這一部分，因此只分析這一部分的時(shí)間復(fù)雜度。首先定義幾個(gè)基礎(chǔ)概念，節(jié)點(diǎn)個(gè)數(shù)n、邊個(gè)數(shù)m、種群規(guī)模M、錦標(biāo)賽規(guī)模t以及迭代次數(shù)G。選擇父本的時(shí)間復(fù)雜度是O(t)。交叉算法所花費(fèi)的時(shí)間復(fù)雜度是O(n)。變異算子的時(shí)間復(fù)雜度是O(1)。計(jì)算適應(yīng)值的時(shí)間復(fù)雜度分兩種情況，若不用增量計(jì)算，計(jì)算適應(yīng)值時(shí)要遍歷整個(gè)網(wǎng)絡(luò)的所有邊，此時(shí)的時(shí)間復(fù)雜度是O(m)。如果使用增量計(jì)算的方式，在計(jì)算適應(yīng)值時(shí)只需遍歷網(wǎng)絡(luò)中的若干條邊。假設(shè)改變的是節(jié)點(diǎn)i的子集編號(hào)，而節(jié)點(diǎn)i的度數(shù)為di，則需遍歷di條邊。在網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的度數(shù)是不相等的，因此用平均度davg來代表某一個(gè)節(jié)點(diǎn)的度最合理。所以此時(shí)的時(shí)間復(fù)雜度是O(davg)?？傮w算法的時(shí)間復(fù)雜度是O(MG(n+m))。

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

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

表1列出了WSB-EA算法中使用到的所有參數(shù)及其取值。算法的運(yùn)行環(huán)境是Intel(R)Core(TM)i3-2330m，運(yùn)行內(nèi)存4 GB，操作系統(tǒng)Windows7旗艦版，使用的軟件是eclipse4.5。

表1 參數(shù)設(shè)置Table 1 Parameter setting

3.2 小型符號(hào)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

本文使用的小型數(shù)據(jù)集有4個(gè)：斯洛文尼亞政黨網(wǎng)絡(luò)(SPP)、Gahuku-Gama部落網(wǎng)絡(luò)(GGS)、社交圈網(wǎng)絡(luò)(SC)和yeast網(wǎng)絡(luò)(yeast)。

斯洛文尼亞政黨網(wǎng)絡(luò)：這是一個(gè)由斯洛文尼亞10個(gè)議會(huì)政黨之間的關(guān)系組成的網(wǎng)絡(luò)，1994年由一些研究政治的學(xué)者提出[16]。10個(gè)議會(huì)政黨的英文名字縮寫分別是SKD、ZLSD、SDSS、LDS、ZS-ESS、ZS、DS、SLS、SPS-SNS和SNS。這一網(wǎng)絡(luò)中有10個(gè)節(jié)點(diǎn)，45條連邊。

Gahuku-Gama部落網(wǎng)絡(luò)[17]：這一網(wǎng)絡(luò)中有16個(gè)節(jié)點(diǎn)，代表16個(gè)部落。邊數(shù)為59，代表部落之間的聯(lián)盟和對(duì)抗。

社交圈網(wǎng)絡(luò)：這一網(wǎng)絡(luò)是根據(jù)現(xiàn)實(shí)生活中人與人之間的關(guān)系得到的實(shí)際網(wǎng)絡(luò)，節(jié)點(diǎn)有28個(gè)，邊數(shù)為42，代表節(jié)點(diǎn)之間的朋友關(guān)系或敵人關(guān)系。

Yeast網(wǎng)絡(luò)：這是一個(gè)酵母菌的基因調(diào)控網(wǎng)絡(luò)[18]，該網(wǎng)絡(luò)包含690個(gè)節(jié)點(diǎn)和1 080條邊。由于這一網(wǎng)絡(luò)的節(jié)點(diǎn)個(gè)數(shù)較多，在實(shí)驗(yàn)中將種群規(guī)模增加到500。

為了驗(yàn)證WSB-EA算法的準(zhǔn)確性以及健壯性，在這4個(gè)數(shù)據(jù)集上與孫一翔提出的Meme-SB算法和沒有使用增量計(jì)算的WSB-EA算法的實(shí)驗(yàn)結(jié)果作對(duì)比分析。每一個(gè)數(shù)據(jù)集都做30次實(shí)驗(yàn)，記錄求得最小適應(yīng)值時(shí)的迭代次數(shù)和時(shí)間。實(shí)驗(yàn)結(jié)果如表2所示。同時(shí)，為了驗(yàn)證增量計(jì)算對(duì)算法的貢獻(xiàn)，將WSB-EA算法與沒有使用增量計(jì)算的WSB-EA算法進(jìn)行時(shí)間比較，即得到迭代相同的次數(shù)所用的時(shí)間。結(jié)果如表3所示。

從表2可知，無論是只有10個(gè)節(jié)點(diǎn)的SPP網(wǎng)絡(luò)還是有690個(gè)節(jié)點(diǎn)的yeast網(wǎng)絡(luò)，在求得相同適應(yīng)值的情況下，WSB-EA算法的迭代次數(shù)較少，也就說明WSB-EA算法能更快收斂到最優(yōu)解。這也證明了，本文使用的錦標(biāo)賽選擇、單路交叉、單點(diǎn)變異和局部搜索這些遺傳操作，不僅保證了算法的正確性，還加快了尋找最優(yōu)解的速度。

表2 對(duì)比實(shí)驗(yàn)結(jié)果1Table 2 Comparison results 1

表3 對(duì)比實(shí)驗(yàn)結(jié)果2Table 3 Comparison results 2 s

從表3的實(shí)驗(yàn)結(jié)果可以看出，沒有增量計(jì)算的WSB-EA算法的運(yùn)行時(shí)間大大超過了有增量計(jì)算的WSB-EA算法。在規(guī)模比較小的SPP、GGS、SC網(wǎng)絡(luò)上時(shí)間差距沒有太大，因?yàn)檫@3個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)少，有無增量計(jì)算沒有太大差別。但是當(dāng)節(jié)點(diǎn)個(gè)數(shù)增加，在yeast網(wǎng)絡(luò)上增量計(jì)算就體現(xiàn)出了優(yōu)勢(shì)。這也驗(yàn)證了本文提出的增量計(jì)算對(duì)與求解大型符號(hào)網(wǎng)絡(luò)的弱不平衡度有很大的幫助。

接下來使用WSB-EA算法求得4個(gè)網(wǎng)絡(luò)的弱不平衡度。在實(shí)驗(yàn)開始前無法獲得k的取值，因此只能在實(shí)驗(yàn)之初先測(cè)試k的取值，即先取不同的k值，看哪一個(gè)k值在算法運(yùn)行時(shí)的收斂效果好。做法是選取k值從3 ～ 20，每一個(gè)k值都做10次實(shí)驗(yàn)，迭代次數(shù)設(shè)置為50。比較最后適應(yīng)值，適應(yīng)值最小的k值就是最適合的k的取值。確定每一個(gè)網(wǎng)絡(luò)的k的取值之后，對(duì)每個(gè)網(wǎng)絡(luò)作30次實(shí)驗(yàn)，求解這個(gè)網(wǎng)絡(luò)的弱不平衡性，實(shí)驗(yàn)結(jié)果如表4所示。由表2和表4中的適應(yīng)值這一列可以看出，弱不平衡度值更小，也就說明，弱不平衡定理更適合真實(shí)符號(hào)網(wǎng)絡(luò)，更具有現(xiàn)實(shí)意義。由表4中k的取值這一列可知，k的取值都不大，所以對(duì)于一個(gè)網(wǎng)絡(luò)而言，在處于弱結(jié)構(gòu)平衡時(shí)不會(huì)被劃分成太多的陣營。

表4 4種小型符號(hào)網(wǎng)絡(luò)的弱不平衡度實(shí)驗(yàn)結(jié)果Table 4 The experimental results of unbalanced degree of four small signed networks

3.3 大型符號(hào)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

本文使用的大型數(shù)據(jù)集有兩個(gè)：Epinions網(wǎng)絡(luò)[7]和Slashdot網(wǎng)絡(luò)[7]。根據(jù)數(shù)據(jù)集的規(guī)模來修改迭代次數(shù)和種群規(guī)模這兩個(gè)參數(shù)。由于數(shù)據(jù)集中節(jié)點(diǎn)個(gè)數(shù)太多，以及內(nèi)存的限制，種群規(guī)模只能設(shè)置為200，所以很大程度地增大迭代次數(shù)，設(shè)置為10萬次。

Epinions網(wǎng)絡(luò)：Epinions網(wǎng)絡(luò)是從Epinions獲取的，Epinions網(wǎng)站是一般消費(fèi)者評(píng)論網(wǎng)站，成立于1999年。游客可以對(duì)各種物品進(jìn)行評(píng)價(jià)，也可以通過閱讀各種物品的評(píng)價(jià)來幫助他們作出購買決策。該網(wǎng)絡(luò)有131 828個(gè)節(jié)點(diǎn)，841 372條邊。每條連邊表示節(jié)點(diǎn)之間的信任關(guān)系。此數(shù)據(jù)集是有向網(wǎng)絡(luò)，因此預(yù)處理數(shù)據(jù)時(shí)需將其改為無向網(wǎng)絡(luò)，即將節(jié)點(diǎn)之間關(guān)系沖突的連邊刪除，例如節(jié)點(diǎn)1認(rèn)可節(jié)點(diǎn)2評(píng)論，但節(jié)點(diǎn)2不認(rèn)可節(jié)點(diǎn)1的評(píng)論，在預(yù)處理數(shù)據(jù)時(shí)要?jiǎng)h除這樣的連邊。

Slashdot網(wǎng)絡(luò)：Slashdot網(wǎng)絡(luò)是從 Slashdot網(wǎng)站獲取的，Slashdot網(wǎng)站是一個(gè)資訊科技網(wǎng)站。它每天都會(huì)更新主頁的新聞數(shù)次，網(wǎng)站使用者可以對(duì)公布在該站的新聞發(fā)表意見。該網(wǎng)絡(luò)有81871個(gè)節(jié)點(diǎn)，545 671條邊。預(yù)處理的方法與處理Epinions數(shù)據(jù)集方法一樣。

在大型符號(hào)網(wǎng)絡(luò)上，將WSB-EA算法與HRTSB算法的實(shí)驗(yàn)結(jié)果進(jìn)行比較。對(duì)于每一個(gè)數(shù)據(jù)集做30次實(shí)驗(yàn)，求解網(wǎng)絡(luò)的弱不平衡度，實(shí)驗(yàn)結(jié)果如表5所示。表5中前3列由WSB-EA算法計(jì)算得出，最后一列數(shù)據(jù)由HRT-SB算法[19]得出。由表5可知，對(duì)于大型符號(hào)網(wǎng)絡(luò)而言，即使節(jié)點(diǎn)個(gè)數(shù)有10萬這么多，k的取值仍然不大。也就是說，無論這個(gè)網(wǎng)絡(luò)有多大規(guī)模，劃分的陣營個(gè)數(shù)都不會(huì)太多。由弱不平衡比可知，每一個(gè)網(wǎng)絡(luò)中不平衡的邊占很少一部分，整個(gè)網(wǎng)絡(luò)是處于弱結(jié)構(gòu)平衡的。由弱不平衡度和不平衡度這兩列數(shù)據(jù)可以看出，弱不平衡度的值是遠(yuǎn)遠(yuǎn)小于不平衡度的值的，也說明了弱結(jié)構(gòu)平衡定理相對(duì)于結(jié)構(gòu)平衡定理來說，更適合研究符號(hào)網(wǎng)絡(luò)的結(jié)構(gòu)性質(zhì)。

表5 兩種大型符號(hào)網(wǎng)絡(luò)的弱不平衡度實(shí)驗(yàn)結(jié)果Table 5 The experimental results of unbalanced degree of two large signed network

4 結(jié)束語

在符號(hào)網(wǎng)絡(luò)中，結(jié)構(gòu)平衡是一個(gè)很重要的研究領(lǐng)域，然而現(xiàn)實(shí)世界中存在的大多數(shù)網(wǎng)絡(luò)都不是嚴(yán)格的結(jié)構(gòu)平衡網(wǎng)絡(luò)。因此研究網(wǎng)絡(luò)的弱結(jié)構(gòu)平衡性就顯得尤為重要。在前人的基礎(chǔ)上，本文提出了弱結(jié)構(gòu)平衡定理的能量函數(shù)，利用進(jìn)化算法的繁衍得到網(wǎng)絡(luò)的弱不平衡度。通過大量的對(duì)比實(shí)驗(yàn)證明，本文提出的WSB-EA算法實(shí)驗(yàn)效果不錯(cuò)，且能更快得到最優(yōu)解。然而，由于本文提出的算法是用來解決大型網(wǎng)絡(luò)的，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)太多的時(shí)候，想要找到最優(yōu)解需要的時(shí)間太長(zhǎng)，因此在未來的工作中可以繼續(xù)改進(jìn)算法的進(jìn)化能力，讓算法可以更快地找到最優(yōu)解，及在后續(xù)工作中可以尋找WSB-EA算法的應(yīng)用領(lǐng)域。例如，將晉商文化中的商幫當(dāng)作節(jié)點(diǎn)，商幫之間的經(jīng)濟(jì)往來當(dāng)作聯(lián)系，將此組成晉商網(wǎng)絡(luò)，分析網(wǎng)絡(luò)中商幫之間的相互作用關(guān)系，以及如何達(dá)到一種穩(wěn)定的發(fā)展態(tài)勢(shì)，將這些信息整合，為現(xiàn)代企業(yè)發(fā)展提供參考。