基于灰狼優化算法的社交網絡影響力識別算法

李淑霞 楊俊成(河南工業職業技術學院電子信息工程學院 河南 南陽 473000)

0 引 言

隨著社交網絡的蓬勃發展，社交網絡中用戶的影響逐漸受到人們的關注，目前與社交影響力有關的研究方向主要有發現意見領袖和影響力傳播[1]。通過用戶之間的社交活動可觀察出社交影響力的強弱，具體表現為影響力大的用戶能夠使其他用戶的行為和思想發生改變。當前，影響力分析在推薦系統[2]、鏈路預測[3]、市場營銷[4]和突發事件檢測[5]等領域發揮了重要的作用。

社交網絡包含復雜的網絡結構，這為用戶的影響力分析增加了難度。在目前常用的影響力分析方法中，一般將社交網絡分為若干的社區，然后分別識別每個社區內影響力高的用戶[6-7]。文獻[8]提出OLMiner算法從大規模社交網絡檢測出意見領袖，該研究解決了社交用戶的影響力重疊問題，通過縮小候選解數量降低算法的計算復雜度。文獻[9]提出基于擴展獨立級聯模型，并融入網絡結構特征、個體屬性和行為特征的意見領袖挖掘模型，該模型利用懶惰向前(Lazy forward,LF)算法挖掘網絡中影響力較大的個體。該模型考慮了信息傳播中交互特征的問題，但是其計算成本較大。文獻[10]提出一種基于上下文感知和用戶影響力的好友推薦算法，首先根據通信數據計算用戶間的通信社交信任度，再利用用戶之間的地理位置數據計算位置信任度，根據兩方面的數據得到用戶間的綜合社交影響力。文獻[11]結合MapReduce編程計算模型和PageRank模型，提出一種基于MapReduce并行化計算模型的微博用戶影響力排名優化算法。

目前大量的研究結果顯示，社交網絡可分為社區形式，每個社區內均包含影響力大的意見領袖[12]，因此許多專家將識別每個社區的影響力作為主要的研究工作。文獻[13]利用Louvain算法劃分社交網絡的社區結構，再通過語義分析檢測每個社區的高影響力用戶，該算法在真實數據集上完成了驗證，取得了理想的結果。受文獻[13]啟發，本文設計了社區檢測和影響力分析算法。

傳統的社區檢測算法主要通過兩個節點的共同鄰居節點來估計節點間的相似性，再通過模塊度評價社區結構的強度。但該方法對連接密集型網絡的性能不佳，同時模塊度僅僅基于節點間的連接而定義，忽略了鄰居節點間的連接。本文同時考慮了鄰居節點和非鄰居節點來決定兩者的相似性，有助于提高社區檢測的準確性。此外，在社區用戶的影響力識別算法中，利用灰狼優化算法尋找影響力高的用戶，為傳統灰狼優化算法設計了兩個變異算子，從而防止灰狼優化算法發生局部收斂。

1 模塊度社區檢測算法

1.1 節點相似性

如果兩個節點間存在許多相同的屬性，那么這兩個節點的相似性高。設G=(V,E)為無向圖，其中V為圖的節點集合，E為邊集合。如果兩個節點a,b∈V具有多個相同鄰居節點，那么認為a的b之間相似性較高。因此可通過統計節點a和b之間相同的鄰居數量來度量兩者的相似性，定義為：

(1)

式中：Γa、Γb分別表示a、b的鄰居節點集。該度量方法僅對存在直接連接的情況有效，在真實網絡中存在大量無連接的情況，所以該方法無法準確地解決社區檢測問題。

1.2 社區模塊度

模塊度是一種常用的社區結構度量指標，該指標統計相同社區內每對節點的連接數量，通過和閾值比較決定社區的結構。設G=(V,E)表示無向網絡，網絡包含n=|V|個頂點和m條邊。將網絡表示為鄰接矩陣A=(aij)，其元素aij=1表示節點vi和vj之間存在連接；aij=0表示節點vi和vj之間沒有連接。設NC為G的社區數量，G的模塊度定義為：

(2)

式中：di和dj分別為節點vi和vj的度；δ()表示克羅內克函數，如果節點ci和cj屬于同一個社區；δ(ci,cj)等于1，否則為0。將式(2)改寫為：

(3)

式中：Is為簇s的邊數量；ds為s內節點的度之和。式(3)可以直觀反映實際連接數量和期望連接數量之間的差異。

1.3 基于廣義模塊度的社區檢測技術

目前主要通過兩個節點的共同鄰居估計節點間的相似性，而本文考慮了鄰居節點和非鄰居節點來決定兩者的相似性。如果節點x和節點y連接，且x和另一個節點z也連接，那么y也應該和z連接。本文的相似性度量檢查網絡中的所有節點來評估兩個節點間的關系，節點vi和節點vj間的連接定義為：

(4)

設sim為相似性指標，如果節點vi和節點vj連接，然后尋找和vi、vj均連接的另一個節點vk，可獲得節點vi和vj之間連接評分的計算式：

(5)

式中：n為網絡的節點數量，如果adj(vi,vj)=1，且adj(vi,vk)=adj(vi,vk)，那么Di,j的最小值為2。最終節點vi和vj之間的相似性定義為：

(6)

如果Di,j的最小值為2，那么sim(vi,vj)的最大值為1。當兩個節點的鄰居和非鄰居均相同，此時兩個節點之間sim為最大值。sim的最小值為1/(n-1)。sim的取值范圍為[1/(n-1),1]，n值越高，則sim值越小，表示節點間越不相似。sim相似性具有對稱性，即sim(vi,vj)=sim(vj,vi)。兩個節點的共同鄰居越多，則認為它們的相似性越高。

(7)

(8)

綜上，將式(7)改寫為：

(9)

1.4 基于廣義模塊度的社區劃分算法

(10)

社區劃分算法的具體步驟如下：

Step1社交網絡建模為無向、無權重的網絡G。

(11)

Step6重復上述步驟，直至模塊度的增量為0或者為負值。

2 社交網絡分析

2.1 社交網絡模型

在意見領袖的模型中社交網絡建模為有向圖，設G={V,E}為社交網絡，其中V為用戶集，E為邊集，E表示了用戶間的關系，用戶關系依賴于用戶的興趣、行為、社區、工作環境等屬性。

2.2 社交網絡的中心度量指標

采用三個中心度量指標計算用戶影響力的目標函數。

(1) 介數中心。根據節點在網絡中的最短路徑計算其介數中心性(Betweenness Centrality,BC)，該指標反映了目標節點作為傳播橋梁的貢獻度。BC定義為：

(12)

式中：c(i,j)(x)表示經過x的最短路徑i→j總數量；c(i,j)表示i和j之間最短路徑i→j總數量。

(2) 緊密中心性(closeness centrality,CC)。CC反映了某個節點到達其他節點的難易程度，定義為節點到達網絡所有其他節點的最短距離之和，其計算式為：

(13)

式中：d(x,y)為節點x和節點y間的最短距離。

(3) 度中心性度中心性(Degree Centrality,DC)。根據網絡直接連接的概念定義節點的度中心性DC，定義為和節點x關聯的所有直接連接之和，其計算式為：

DC(x)=dig(x)

(14)

式中：dig(x)表示節點x的度。

2.3 社交影響力的目標函數

本文基于BC、CC和DC定義了目標函數Ob：

(15)

3 灰狼優化算法的增強

3.1 灰狼優化算法

灰狼優化算法(GWO)共有4種不同領導力的狼：α狼、β狼、δ狼和ω狼，α狼、β狼和δ狼分別為最優解、次優解、第三優解，ω狼為候選解。狼群圍補獵物的過程表示為以下的數學模型：

D=|C·Xp-X(t)|

(16)

X(t+1)=|Xp(t)-A·D|

(17)

式中：Xp和X分別表示第t次迭代獵物和灰狼的位置。A和C為系數向量，分別定義為：

A=|2a·rand1-a|

(18)

C=2·rand2

(19)

式中：rand1和rand2均為[0,1]之間的隨機量。a的模在迭代過程中從2線性下降至0，其計算式為：

(20)

式中：iter表示最大迭代次數。

圖1所示是二維的位置向量和灰狼的下一個可能位置，圖中(X,Y)為灰狼agent的位置，(X*,Y*)為獵物的位置。

捕獵過程中α狼、β狼和δ狼更新位置的方法為：

(21)

X1=Xα-A1·(Dα),Dα=|C1·Xα-X|

(22)

X2=Xβ-A2·(Dβ),Dβ=|C2·Xβ-X|

(23)

X3=Xδ-A3·(Dδ),Dδ=|C3·Xδ-X|

(24)

式中：X1、X2和X3分別為α狼、β狼和δ狼的位置。

GWO算法在攻擊獵物的過程中，每只狼根據它的當前位置和獵物的位置更新下一次迭代的位置。在搜索獵物階段，α狼、β狼和δ狼彼此遠離來擴大搜索范圍，在攻擊獵物階段，α狼、β狼和δ狼開始收斂。

3.2 增強的灰狼優化算法(EnGWO)

本文對灰狼優化算法進行了增強處理，記為EnGWO。EnGWO包括初始化階段、目標函數評價階段、轉換函數階段和變異階段。

(1) 初始化階段。初始化階段采用隨機初始化機制，生成n個狼(稱為agent)。每個agent表示一個可能解，灰狼搜索的目標是搜索聲譽最高的目標用戶，將社交網絡的用戶位置組織成如下二維矩陣形式：

(2) 評價指標。GWO的適應度函數為式(15)。

(3) 精英算子和變異算子。為了增強GWO的全局搜索能力。設計了一個精英算子和一個變異算子見算法1和算法2。精英算子的目標是保留高聲望的用戶，同時隨機刪除一部分高聲望用戶，參考許多遺傳算法的研究文獻，將變異算子的Mp設為0.1，從而平衡收斂速度和變異效果。變異算子的目標是引入一部分聲望較低的用戶，避免發生局部收斂的情況。

算法1精英算子

輸入：Xα。

//原解

輸出：Xα。

//處理后的解

1.fit=計算Xα的適應度；

2.分配向量pos來保存Xα已訪問的top-N位置；

3.分配變量Xmut=Xα；

4.fori=1 tolenth_of(pos)

//遍歷當前的top-N特征

5.生成[0,1]的隨機數rand；

6.ifrand

//Mp設為0.1

7.Xmu[pos[i]]=0；

//刪除部分最優用戶

8.fitmu←Xmu1的適應度；

//計算新的適應度

9.iffitmu

10.fit=fitmu；

11.Xα=Xmu1；

12.end for

13.end for

14.end for

算法2變異算子

輸入：Xα。

//原解

輸出：Xα。

//處理后的解

1.分配向量zer保存N個未被訪問的隨機用戶；

2.分配變量Xmut2；

3.forj=1 tolenth_of(zer)；

//遍歷N個未被訪問的用戶

4.生成[0,1]內的隨機數rand；

5.if(rand

6.Xmu2[zer[j]]=1

7.fitmu←Xmu2的適應度；

8.if(fitmu

9.fit=fitmu；

10.Xα=Xmu2；

11.end if

12.end if

13.end for

(4) EnGWO算法的實現。算法3所示為本文所設計的EnGWO算法流程。

算法3增強的灰狼優化算法。

1.初始化灰狼種群Xi；

2.每個灰狼表示為一個向量；

3.初始化參數；

4.分配迭代變量t=0；

5.計算每個灰狼的適應度fit；

6.分配三個最優解Xα、Xβ、Xδ；

7.fortfrom 1 toITERmax

8.foreach 灰狼 agent

9.更新灰狼的位置；

//式(21)

10.end for

11.更新a,A,C；

12.計算每個灰狼的適應度；

13.更新最優灰狼Xα、Xβ、Xδ；

14.t++；

15.對Xα運用精英算子和變異算子；

16.更新Xα的適應度；

17.檢查是否滿足收斂條件；

18.end for

4 實 驗

4.1 實驗數據集

采用真實數據集Slashdot[14]驗證本文算法的有效性，Slashdot是與技術相關的新聞網站，允許用戶對于每個條目進行“好友”和“敵人”的標注。該數據集共有13 182個節點、28個社區和34 621條邊，每條邊表示了用戶之間的好友關系，網絡的密度為5.198 1。大約76.7%的用戶之間存在好友關系，其他用戶之間為對手關系。Slashdot數據集中一些用戶之間沒有好友或者對手關系，通過幾何平均數方法計算全部節點的度，補全缺失的社交連接。

4.2 社區檢測算法的性能

本文設計了無監督的社區檢測算法以滿足社交網絡影響力分析的要求，首先驗證本文社區檢測算法的有效性。選擇兩種算法與本文算法進行比較，Louvain算法是一個常用的經典社區檢測算法，基于模塊度實現，但該算法需要預先指定社區數量。ESMCD算法[15]在計算模塊度的過程中采用部分標注信息，提高社區檢測的性能。本文社區檢測算法對相似性進行了補充，以提高模塊度評估的性能，所以選擇這兩個基于模塊度的社區檢測算法作為對比方法。

本文實驗硬件環境為PC，i7處理器的主頻為3.2 GHz，16 GB內存，操作系統為Windows 10，使用Python語言編程實現本文算法。表1所示是三個社區檢測算法的實驗結果，每種算法分別獨立地運行100次，三種算法的平均模塊度分別為0.852 2、0.712 1和0.724 1，三種算法各有優劣，但是Louvain算法和ESMCD算法均需要社交網絡的先驗信息，而本文算法是一種無監督的自適應檢測算法，無需任何先驗信息。

4.3 性能評價指標和參數設置

本文采用準確率、精度、召回率和F1-score作為社交網絡影響力識別的性能評價指標。準確率的計算式為：

式中：TP、TN、FP和FN分別表示判斷為正向的正確率、判斷為負向的正確率、把負向判斷成正向的誤報率和把正向判斷成負向的漏報率。

精度的計算式為：

召回率的計算式為：

F1-score的計算式為：

通過一組預處理實驗尋找合適的灰狼優化算法參數，最終選定表2所示的值作為灰狼優化算法對于Slashdot數據集的相關參數。

4.4 社交影響力分析實驗

選擇以下三種社交影響力識別算法作為對比方法：OLRS[16]是一種意見領袖識別算法，該算法并不包含社區劃分處理，且無需社交網絡的拓撲信息，選擇該算法可以觀察本文算法對社交網絡結構的利用效果；MOL[17]是一種高效率的大數據意見領袖挖掘算法，該算法中通過隨機化機制提高算法的挖掘效率，選擇該算法可以觀察本文算法對社交網絡全局意見領袖的識別效果；SAIIN[18]是一種基于迭代和語義分析的意見領袖挖掘算法，本文算法則是基于迭代和網絡結構的影響力分析算法，選擇該算法可以比較網絡結構和語義分析對影響力識別的性能差異。

(1) 局部社交影響力實驗。采用四種社交影響力識別算法檢測每個社區的意見領袖，結果如表3所示，表中的粗體表示正確識別的每個社區意見領袖。MOL算法對第6、26社區識別的社交領袖出現偏差，OLRS算法對第7、8、10、13、21、22、26和28社區識別的社交領袖出現偏差，OLRS算法對第13、15、17、20、24和28社區識別的社交領袖出現偏差。本文算法所檢測的28個社區的意見領袖均正確。

表3 局部社交影響力的實驗結果

續表3

(2) 全局社交影響力實驗。采用四種社交影響力識別算法檢測Slashdot數據集的全局影響力，表4中第2列是top-10影響力的節點編號。MOL算法所檢測的top-10影響力節點較為準確，但是影響力的排名存在偏差。OLRS算法所檢測的top-10影響力節點存在偏差。本文算法所檢測的top-10影響力節點較為準確，并且影響力的排名也較為準確。

表4 全局社交影響力的實驗結果

在社交網絡中往往存在多個社交影響力較大的用戶，因此通過本文算法檢測每個社區top-50的高影響力節點。通過準確率、精度、召回率和F1-score評價四種算法的社交影響力總體識別性能，結果如圖2所示。OLRS算法檢測少量社交領袖的性能較好，但是該算法并未考慮影響力排序，導致對非社交領袖的識別能力不足。MOL算法和SAIIN算法的準確率、精度、召回率和F1-score的性能均較為理想，足以提供高質量的影響力分析效果。本文算法采用增強的灰狼優化算法也實現了理想的識別準確率，并且略優于MOL算法和SAIIN算法。

圖2 社區top-50影響力的平均識別性能

5 結 語

本文設計了無監督的社區劃分算法，通過社區劃分減小社交影響力識別的復雜度。此外，本文利用灰狼優化算法參數少、收斂速度快的優點尋找影響力大的用戶，通過引入兩個變異算子增強種群的多樣性，減小局部收斂的概率。目前本文算法僅支持靜態社交網絡的影響力識別問題，無法用于動態社交網絡。另外，社交網絡中包含粉絲數量、關注數量、用戶語義和用戶登錄次數等大量的上下文信息，這些信息對用戶影響力的判斷具有巨大的潛在價值。未來將研究社交網絡中的非拓撲結構信息對社交影響力的貢獻，進一步提高算法的性能和實用價值。