WSB-EA進化算法的符號網絡弱結構平衡分析

常新功，趙雅娟

（山西財經大學 信息管理學院，山西 太原 030006）

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

1 背景知識

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

1.1 弱結構平衡定理

符號網絡用數學符號G(V, E)表示，V表示網絡節點集合，E表示網絡邊的集合。其中任意一條邊，其符號為“+”或“–”。“+”代表節點i與節點j之間的邊是積極關系，“–”則代表消極關系。Heider指出如果網絡中任意一個三角形的符號乘積為正，則網絡是平衡的。如圖1所示，(a)和(b)是平衡三角，(c)和(d)是不平衡三角。在此基礎上Cartwright和Harary等提出判斷符號網絡是否平衡的一個充要條件——“如果一個網絡中的節點能夠被分割為兩個子集，每個子集內的所有邊均是正邊，子集間的邊均為負邊，這樣的網絡就是平衡的。”

然而對于大多數符號網絡而言，結構平衡定理的要求太過嚴苛。之后Davis放寬結構平衡理論的約束條件，提出了弱結構平衡理論。這一理論將圖1(d)三條邊都是負號這樣的三角結構也認為是平衡結構。因此產生了一個新的概念，K-平衡網絡。這一理論認為，一個符號網絡是弱平衡的，當且僅當可以將這一網絡中的節點分為k個子集，子集內部都是正邊，子集之間都是負邊。結構平衡定理是弱結構平衡定理中k為2的特殊情況。K-平衡網絡的結構如圖2所示，圖中集合內部連邊都是正邊，集合之間連邊都是負邊。

圖1 符號網絡中4種三角形結構[1]Fig. 1 Four triangle signed network structures[1]

圖2 弱結構平衡網絡Fig. 2 Weak balance network structure

1.2 弱結構平衡定理能量函數

根據弱結構平衡定理，計算符號網絡的弱不平衡度就是尋找一種集合劃分，使得集合內部之間的負邊數和集合外部之間的正邊數最少。例如，節點1和節點2之間的連邊為正，如果將這兩個節點分到同一個集合，這兩個節點就沒有對弱不平衡度做出“貢獻”，如果把它們分到不同的集合，就需要計算這兩個節點對弱不平衡度做的“貢獻”。同理，兩個節點之間的邊是負邊時，將其分到同一集合，也要計算這一部分的“貢獻”。因此計算弱不平衡度就是遍歷整個符號網絡，找到所有對弱不平衡度做出“貢獻”的節點對。由此提出弱結構平衡定理的能量函數：

在弱結構平衡定理中，一個無向符號網絡被分為k個子集。因此，網絡中每個節點都有一個所屬的子集編號，在式中用si來表示這一編號。δ(si, sj)的計算結果由si和sj決定，如果si和sj的值相同則計算結果為+1，否則為–1。

由此，求解符號網絡的弱結構平衡問題就轉變為最小化能量函數的優化問題。能量函數的最小值代表了導致符號網絡弱不平衡的最少邊的數目。若將這些邊的符號取反，可以將此網絡轉變為弱結構平衡網絡。如果能量函數值為0，說明此網絡已是弱結構平衡網絡。

1.3 進化算法

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

2 WSB-EA算法描述

2.1 WSB-EA算法主要流程

根據問題定義以及進化算法原理，本文將弱結構平衡定理的能量函數作為目標函數，在Meme-SB算法的基礎上，初始化種群，經過選擇、交叉、變異得到最優解。具體框架如算法1所示。

算法1 WSB-EA算法

輸入 鄰接矩陣J，種群規模P，迭代次數M；輸出 最優解的適應值，即網絡弱不平衡度。

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

3) a=0;

4) repeat

5) individual = Pop.getFittest();//計算得到種群最優個體

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

7) a=a+1;

8) until a=M //達到最大進化次數時停止

2.2 編碼

本文使用的編碼方式是整數編碼[13]。種群中的染色體由表示，其中n為符號網絡的節點個數，表示第i個節點所屬的子集編號。假設符號網絡中有k個子集，則的取值范圍是0 ～ k–1。例如第j個染色體可以表示成。

2.3 初始化

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

2.4 遺傳操作

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

算法2 evolvePopulation (individual)算法

輸入 原始種群Pop，最優個體individual，錦標賽規模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 選擇操作

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

2.4.2 交叉操作

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

圖3 單路交叉Fig. 3 Single cross

2.4.3 變異操作

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

2.5 符號網絡存儲

符號網絡在計算機中一般有3種存儲方式：鄰接矩陣、三元組和鏈表方式。鄰接矩陣是普遍使用的一種方式。然而對于大型符號網絡來說，鄰接矩陣達到105×105的數量級，存儲這樣的鄰接矩陣對內存要求太高。因此本文選擇鄰接鏈表[15]來存儲網絡信息。首先為每一個節點都創建一條鏈表，頭結點是節點本身，后面鏈接與這一節點有聯系的節點信息，包括節點編號以及邊的符號。例如，圖4中，這一鏈表存儲節點1的連邊信息。節點1與節點2的連邊為1，節點1與節點6的連邊為–1。雖然每條邊都存儲了兩次，但相對于鄰接矩陣的存儲方式，大大降低了內存占用。

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

2.6 增量計算

在一般的遺傳算法中，每一次的交叉和變異之后都需重新計算一次適應值，這樣重復操作使得算法的時間復雜度太高。基于此，本文在定理1的基礎上提出一種增量計算的方式，在重新計算適應值時，只計算個體中因基因改變使得適應值增減的部分。

定理1 假設個體ind在位置h處變異，sh由old變為new，則個體ind的新適應值h(ind)new為

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

上述推導表明，當個體ind在h位置變異后，新的適應值通過舊適應值加一個增量就可以得到，而這個增量只需要遍歷vh的鄰居節點就可以算出，這樣計算一個個體的適應值的時間復雜度從O(m)降為O(davg)，其中davg為平均度數。

基于定理1，計算新的適應值就可以簡便為計算改變子集編號的節點與其鄰居節點對適應值的“貢獻”。具體分為兩種情況：1)原本對適應值沒有“貢獻”的邊，在改變基因之后對適應值有“貢獻”；2)原本對適應值有“貢獻”的邊，在改變之后對適應值沒有“貢獻”。增量計算大大地降低了時間復雜度，在交叉算法中的增量計算只需循環若干次，而在變異算法中只需運行一次。

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

算法3 ncreaseFitness()算法

輸入 需要計算適應值的個體individual，基因改變位置id，舊基因old，新基因new；

輸出 增加的適應值increaseFitness。

1) increaseFitness=0；

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

3) 遍歷節點id的所有鄰居節點；

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(負鄰居)

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 復雜性分析

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

3 實驗結果與分析

3.1 參數設置

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

表1 參數設置Table 1 Parameter setting

3.2 小型符號網絡實驗結果

本文使用的小型數據集有4個：斯洛文尼亞政黨網絡(SPP)、Gahuku-Gama部落網絡(GGS)、社交圈網絡(SC)和yeast網絡(yeast)。

斯洛文尼亞政黨網絡：這是一個由斯洛文尼亞10個議會政黨之間的關系組成的網絡，1994年由一些研究政治的學者提出[16]。10個議會政黨的英文名字縮寫分別是SKD、ZLSD、SDSS、LDS、ZS-ESS、ZS、DS、SLS、SPS-SNS和SNS。這一網絡中有10個節點，45條連邊。

Gahuku-Gama部落網絡[17]：這一網絡中有16個節點，代表16個部落。邊數為59，代表部落之間的聯盟和對抗。

社交圈網絡：這一網絡是根據現實生活中人與人之間的關系得到的實際網絡，節點有28個，邊數為42，代表節點之間的朋友關系或敵人關系。

Yeast網絡：這是一個酵母菌的基因調控網絡[18]，該網絡包含690個節點和1 080條邊。由于這一網絡的節點個數較多，在實驗中將種群規模增加到500。

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

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

表2 對比實驗結果1Table 2 Comparison results 1

表3 對比實驗結果2Table 3 Comparison results 2 s

從表3的實驗結果可以看出，沒有增量計算的WSB-EA算法的運行時間大大超過了有增量計算的WSB-EA算法。在規模比較小的SPP、GGS、SC網絡上時間差距沒有太大，因為這3個網絡節點少，有無增量計算沒有太大差別。但是當節點個數增加，在yeast網絡上增量計算就體現出了優勢。這也驗證了本文提出的增量計算對與求解大型符號網絡的弱不平衡度有很大的幫助。

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

表4 4種小型符號網絡的弱不平衡度實驗結果Table 4 The experimental results of unbalanced degree of four small signed networks

3.3 大型符號網絡實驗結果

本文使用的大型數據集有兩個：Epinions網絡[7]和Slashdot網絡[7]。根據數據集的規模來修改迭代次數和種群規模這兩個參數。由于數據集中節點個數太多，以及內存的限制，種群規模只能設置為200，所以很大程度地增大迭代次數，設置為10萬次。

Epinions網絡：Epinions網絡是從Epinions獲取的，Epinions網站是一般消費者評論網站，成立于1999年。游客可以對各種物品進行評價，也可以通過閱讀各種物品的評價來幫助他們作出購買決策。該網絡有131 828個節點，841 372條邊。每條連邊表示節點之間的信任關系。此數據集是有向網絡，因此預處理數據時需將其改為無向網絡，即將節點之間關系沖突的連邊刪除，例如節點1認可節點2評論，但節點2不認可節點1的評論，在預處理數據時要刪除這樣的連邊。

Slashdot網絡：Slashdot網絡是從 Slashdot網站獲取的，Slashdot網站是一個資訊科技網站。它每天都會更新主頁的新聞數次，網站使用者可以對公布在該站的新聞發表意見。該網絡有81871個節點，545 671條邊。預處理的方法與處理Epinions數據集方法一樣。

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

表5 兩種大型符號網絡的弱不平衡度實驗結果Table 5 The experimental results of unbalanced degree of two large signed network

4 結束語

在符號網絡中，結構平衡是一個很重要的研究領域，然而現實世界中存在的大多數網絡都不是嚴格的結構平衡網絡。因此研究網絡的弱結構平衡性就顯得尤為重要。在前人的基礎上，本文提出了弱結構平衡定理的能量函數，利用進化算法的繁衍得到網絡的弱不平衡度。通過大量的對比實驗證明，本文提出的WSB-EA算法實驗效果不錯，且能更快得到最優解。然而，由于本文提出的算法是用來解決大型網絡的，當網絡節點太多的時候，想要找到最優解需要的時間太長，因此在未來的工作中可以繼續改進算法的進化能力，讓算法可以更快地找到最優解，及在后續工作中可以尋找WSB-EA算法的應用領域。例如，將晉商文化中的商幫當作節點，商幫之間的經濟往來當作聯系，將此組成晉商網絡，分析網絡中商幫之間的相互作用關系，以及如何達到一種穩定的發展態勢，將這些信息整合，為現代企業發展提供參考。