基于粒子群優(yōu)化算法的社交網(wǎng)絡(luò)結(jié)構(gòu)平衡的實現(xiàn)

李趙興，陳 莉，劉瓊海

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

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

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

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

1 網(wǎng)絡(luò)結(jié)構(gòu)平衡

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

圖1 平衡結(jié)構(gòu)示意圖

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

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

圖2 網(wǎng)絡(luò)結(jié)構(gòu)平衡條件

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

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

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

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

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

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

3.1 算法框架

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

圖3 算法工作流程圖

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

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

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

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

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

3.3 粒子的表示

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

圖4 粒子表示示意圖

由圖4 可知，粒子的位置采用整數(shù)排序，網(wǎng)絡(luò)中的每一個節(jié)點都采用一位數(shù)字來標(biāo)記，并按照標(biāo)記號進行社區(qū)分類。在進行分類時，具有相同標(biāo)記號的網(wǎng)絡(luò)節(jié)點會被分配到同一個社區(qū)中。通過這樣的編碼，在網(wǎng)絡(luò)劃分時，會按照網(wǎng)絡(luò)標(biāo)記號自動分配成多個社區(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)化算法應(yīng)用在社交網(wǎng)絡(luò)平衡中，并且重新定義粒子的狀態(tài)更新方程，如下：

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

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

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

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

4 實驗測試與分析

4.1 實驗設(shè)置

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

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

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

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

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

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

圖5 網(wǎng)絡(luò)AN1的平衡結(jié)構(gòu)圖

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

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

圖6 網(wǎng)絡(luò)AN2的平衡結(jié)構(gòu)圖

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

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

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

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

5 結(jié)束語

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