李趙興，陳 莉，劉瓊海

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

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

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

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

1 網(wǎng)絡結構平衡

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

圖1 平衡結構示意圖

結構平衡定義和基本理論已經(jīng)被系統(tǒng)研究，其在社會心理學、國際關系以及互聯(lián)網(wǎng)絡等領域受到廣泛關注。

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

圖2 網(wǎng)絡結構平衡條件

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

2 粒子群優(yōu)化算法

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

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

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

3 基于粒子群優(yōu)化的網(wǎng)絡結構平衡

3.1 算法框架

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

圖3 算法工作流程圖

3.2 粒子適應度函數(shù)

文中利用適應度函數(shù)來度量粒子對生存環(huán)境的活躍度，并用適應度函數(shù)來評價社交網(wǎng)絡的平衡度。

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

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

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

3.3 粒子的表示

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

圖4 粒子表示示意圖

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

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

3.4 粒子的狀態(tài)更新規(guī)則

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

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

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

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

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

4 實驗測試與分析

4.1 實驗設置

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

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

表1 真實網(wǎng)絡數(shù)據(jù)屬性統(tǒng)計表

4.2 模擬數(shù)據(jù)測試

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

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

圖5 網(wǎng)絡AN1的平衡結構圖

實驗中發(fā)現(xiàn)，在對AN1 和AN2 網(wǎng)絡進行測試時，文中算法PSOSB 和對比算法MemeSB 均得到相同的結果，且算法穩(wěn)定。

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

圖6 網(wǎng)絡AN2的平衡結構圖

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

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

圖7 在AN1和AN1網(wǎng)絡上的算法穩(wěn)定性對比實驗

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

5 結束語

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