基于粒子群優化算法的社交網絡結構平衡的實現

李趙興，陳 莉，劉瓊海

（1.榆林學院信息工程學院，陜西西安 719000；2.西北大學信息技術學院，陜西西安 710071；3.黃委晉陜蒙監督局，陜西榆林 719000）

社交網絡的興起改變了人們的日常生活方式，人們可以借助社交媒體方便地表達自己的觀點和情感，并通過社交平臺建立廣泛的社交關系。對社交網絡展開相關研究，不僅可以挖掘社交網絡中的人群結構特征，還可以分析和預測網絡上的信息傳播流向以及信息傳播可能造成的后果，因此，對社交網絡的研究具有重要的理論研究意義和實際應用價值[1]。

研究社交網絡特性的一種有效途徑是將社交網絡建模成由節點和邊組成的復雜網絡形式，其中節點表示網絡的組成成員，邊表示成員之間的社交關系，通過分析和挖掘復雜網絡的基本特性來達到認知社交網絡以及輔助決策支持的目的。由于社交關系通常存在友好和敵對兩種情況，因此很多社交網絡都被建模成由正邊和負邊表示的復雜符號網絡形式，其中正邊表示友好關系，負邊表示敵對關系。復雜網絡具有很多重要的特征[2-3]，例如小世界特性、無標度特性等。近年來，復雜網絡又一重要特性即社區結構特性[4-5]，被學者發現。

文中針對社交網絡的平衡結構問題[6-7]展開了研究，將平衡結構問題建模為能量最小化優化問題，提出了一種高效的離散粒子群優化算法，用以解決建模的優化問題。結合社交網絡的拓撲結構信息，文中重新定義了粒子的離散表示，構建了基于離散表示的粒子更新方程。與現有的網絡結構平衡求解方法相比，提出的算法不僅可以實現網絡的結構平衡，還可以挖掘網絡的社團結構，而且可以自動得到最佳的社團結構。所提算法的有效性在真實符號網絡數據上得到了驗證。

1 網絡結構平衡

結構平衡是包括社會網絡在內的網絡研究的重要內容。對于圖1 所示的3 個節點構成的網絡，根據結構平衡理論，圖1（a）和圖1（b）被認為是平衡結構，而圖1（c）和圖1（d）是非平衡結構。圖中的“+”代表喜歡、友好等“正”關系，而“-”則表示不喜歡、敵對等“負”關系。

圖1 平衡結構示意圖

結構平衡定義和基本理論已經被系統研究，其在社會心理學、國際關系以及互聯網絡等領域受到廣泛關注。

對于任意一個復雜網絡，若該網絡的節點可以分成X 和Y 兩個子集，且X 和Y 滿足圖2 所示的關系，則稱該網絡是結構平衡的[8]。

圖2 網絡結構平衡條件

大量研究表明，上述的結構平衡條件過于嚴格，多數網絡可以被分成多于兩個的子集，且這些子集也可以滿足X 和Y 的特性。對于現實中的社交網絡，很少網絡是結構平衡的，大多數網絡需要改變網絡中某些邊的屬性或者增加/減少網絡的邊數來實現結構平衡[9]。

2 粒子群優化算法

粒子群算法[10]模仿鳥類覓食的行為，通過對比周圍鳥類的飛行速度來不斷調整自己的飛行狀態，從而得到最優路徑[11]。

如果一個粒子群有m個粒子，粒子被抽象為沒有質量和體積的微粒，第i個粒子在m維空間中的位置可以用向量表示，飛行速度表示為向量=(vi1,vi2,…,vim)，則每個粒子更新自身狀態的規則可以表示為：

每個粒子都有一個被優化函數決定的適應值，并且知道目前為止發現的最好位置=(xpi1,xpi2,…,xpim)，即通常說的粒子個體引導者，即該粒子可以找到的最佳飛行方向；此外，每個粒子還知道周圍最優粒子發現的最好位置=(xgi1,xgi2,…,xgim)。c1和c2均為加速度系數，r1和r2為服從均勻分布U（0,1）的隨機數。粒子群優化是不斷優化的算法，每個粒子根據式（1）、式（2）不斷調整自己的飛行軌跡，以得到最優解逼近[12-13]。

3 基于粒子群優化的網絡結構平衡

3.1 算法框架

文中提出的離散粒子群優化算法通過最小化網絡能量函數來尋找網絡中存在的不平衡邊，然后改變不平衡邊從而實現網絡的結構平衡。提出算法的工作流程圖，如圖3 所示。

圖3 算法工作流程圖

3.2 粒子適應度函數

文中利用適應度函數來度量粒子對生存環境的活躍度，并用適應度函數來評價社交網絡的平衡度。

文獻[14]提出了一種度量網絡平衡程度的能量函數H(s)，其定義如下：

其中，aij∈{±1}是網絡鄰接矩陣的元素，si和sj分別表示節點i和節點j的符號。若節點i和節點j屬于朋友，則si·sj=1，否則si·sj=-1。

若一個網絡是結構平衡的，則其對應的能量函數值H(s)=0，且能量函數越小代表該網絡越趨近結構平衡。文中利用粒子群優化算法來最小化能量函數，從而尋找具有最小能量函數值時對應的網絡社區結構，繼而通過改變非平衡的邊使網絡結構達到平衡。

3.3 粒子的表示

首先對復雜網絡中的點進行編碼，然后采用粒子群優化算法對編碼的網絡進行優化。由于提出的算法要最小化H(s)，因此針對結構平衡問題，文中采用基于字符串的方式對網絡節點進行編碼，這種編碼可以很好地對網絡節點進行描述，而且解密也比較簡單。文中針對網絡進行了粒子的重新編碼，如圖4 所示。

圖4 粒子表示示意圖

由圖4 可知，粒子的位置采用整數排序，網絡中的每一個節點都采用一位數字來標記，并按照標記號進行社區分類。在進行分類時，具有相同標記號的網絡節點會被分配到同一個社區中。通過這樣的編碼，在網絡劃分時，會按照網絡標記號自動分配成多個社區。

在進行解碼時，若節點i和節點j屬于同一個社區，則si·sj=1，若節點i和節點j屬于不同的社區，則si·sj=-1。

3.4 粒子的狀態更新規則

從粒子的表示方式可以看出，粒子的位置是整數編碼的，因此傳統的粒子狀態更新方程（1）和（2）已經不再適用文中問題的求解。將粒子群優化算法應用在社交網絡平衡中，并且重新定義粒子的狀態更新方程，如下：

其中，ω為慣性權值常數，符號⊕表示異或操作。

函數χ(y)是一個壓縮系數，其作用是確保PSO算法的收斂性，需將其轉換為0 到1 之間的數，該壓縮系數與位置向量根據式（4）操作。函數ζ(y)定義為：

式（5）中的?操作是粒子實時狀態變化，符號異操作和或操作可以得到不同的粒子狀態，該異或操作的使用會影響算法識別社區的能力，同時也會影響該算法的收斂速度。

針對一個復雜網絡，一般兩個節點在同一個社區的可能性小，而兩個節點不在同一個社團的幾率較大，針對該問題，文中定義的?操作如下：

4 實驗測試與分析

4.1 實驗設置

為了測試所提算法的性能，下面將對算法進行模擬網絡和真實社交網絡數據的實驗測試。將所提算法命名為PSOSB，算法用到的參數設置如下：慣性系數ω設置為經典值0.729，粒子群學習因子c1和c2均設置為1.494，粒子群種群大小pop和算法迭代次數gmax均設置為100。文中采用的對比算法為文獻[15]提出的基于買賣提優化結構平衡算法MemeSB，該算法的交叉概率和變異概率分別設置為0.8和0.2，其種群大小和算法迭代次數均設置為100。

實驗中用到的模擬網絡數據為文獻中用到的兩個網絡AN1 和AN2[16]，該網絡由28 個節點組成，分成了3 個社區，且該網絡是結構平衡的。該實驗主要驗證AN1網絡和AN2網絡，4個網絡的屬性如表1所示。

表1 真實網絡數據屬性統計表

4.2 模擬數據測試

由于文中算法和對比算法都是迭代算法，因此在實驗中分別對文中算法和對比算法獨立運行30次。

PSOSB 算法和MemeSB 算法30 次獨立運行后得到的能量函數H(s)的值均為0，這表明兩種算法均找到了網絡的平衡結構。圖5 和6 分別展示了AN1 網絡和AN2網絡的網絡平衡結構圖。從圖5和6可以看出，AN1 網絡和AN2 網絡都被分成了3 個社區，且每個社區內部的節點都是正邊連接的，社區之間的節點均為負邊連接，這完全符合網絡結構平衡的定義。

圖5 網絡AN1的平衡結構圖

實驗中發現，在對AN1 和AN2 網絡進行測試時，文中算法PSOSB 和對比算法MemeSB 均得到相同的結果，且算法穩定。

在AN1 和AN2 網絡上，文中算法和對比算法的實驗結果一樣，這是因為這兩個網絡的規模太小，兩種算法均能很容易找到問題的最優解。雖然在AN1和AN2 網絡上兩種算法得到了相同的實驗結果，但是文中算法比對比算法具有更快的收斂速度，文中算法PSOSB 在AN1 和AN2 網絡上的實驗性能要明顯優于MemeSB 算法。

圖6 網絡AN2的平衡結構圖

文中算法是基于粒子群優化的，在粒子群優化算法中，全局最優個體引導整個種群快速向問題的最優解逼近。另外，文中算法在設計上充分利用了網絡的結構信息，所設計的粒子狀態更新方程能夠加速粒子的全局尋優速度。雖然對比算法加入了局部搜索策略，但是該策略是基于貪婪算法的，貪婪算法容易使算法陷入局部最優，而且貪婪算法的計算代價很高。

由于PSOSB 算法和MemeSB 算法都是隨機搜索算法，即算法每次獨立運行的結果都不相同，因此有必要討論算法的穩定性。圖7 展示了PSOSB 算法和MemeSB 算法在AN1 網絡數據和AN2 網絡數據上30次獨立運行得到的統計結果盒圖展示。

圖7 在AN1和AN1網絡上的算法穩定性對比實驗

盒圖反映的是算法多次運行得到結果的統計分布情況，盒圖的長短反映了算法的穩定情況。對于一個較為穩定的算法而言，盒圖長度相對較短。從圖7 可以看出，PSOSB 算法30 運行的盒圖長度比MemeSB 短，這說明PSOSB 相對于MemeSB 更穩定；且從盒圖的數據分布情況也可以看出，在AN1網絡和AN2 網絡上，文中算法優化得到的最小能量函數值比對比算法小，實驗再次證明了所提算法的有效性。

5 結束語

對社交網絡的平衡結構展開研究具有重要的意義。為了實現社交網絡的結構平衡，文中從優化的角度出發，首先將網絡結構平衡問題轉換成優化問題，其次提出了一種基于粒子群優化的求解結構平衡問題的算法。提出的算法不僅可以實現網絡的結構平衡，還可以挖掘網絡中隱藏的社區結構。算法的有效性在模擬數據和真實網絡數據上得到了驗證。下一步工作將研究設計高效的局部學習策略，以提高算法的全局搜索能力；另一方面，將研究和實現算法的并行化以實現算法對大數據網絡的處理，特別是動態的復雜網絡結構平衡是未來值得繼續研究的方向。