基于灰狼優(yōu)化算法的社交網(wǎng)絡影響力識別算法

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

0 引 言

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

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

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

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

1 模塊度社區(qū)檢測算法

1.1 節(jié)點相似性

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

(1)

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

1.2 社區(qū)模塊度

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

(2)

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

(3)

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

1.3 基于廣義模塊度的社區(qū)檢測技術

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

(4)

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

(5)

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

(6)

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

(7)

(8)

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

(9)

1.4 基于廣義模塊度的社區(qū)劃分算法

(10)

社區(qū)劃分算法的具體步驟如下：

Step1社交網(wǎng)絡建模為無向、無權重的網(wǎng)絡G。

(11)

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

2 社交網(wǎng)絡分析

2.1 社交網(wǎng)絡模型

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

2.2 社交網(wǎng)絡的中心度量指標

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

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

(12)

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

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

(13)

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

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

DC(x)=dig(x)

(14)

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

2.3 社交影響力的目標函數(shù)

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

(15)

3 灰狼優(yōu)化算法的增強

3.1 灰狼優(yōu)化算法

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

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

(16)

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

(17)

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

A=|2a·rand1-a|

(18)

C=2·rand2

(19)

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

(20)

式中：iter表示最大迭代次數(shù)。

圖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算法在攻擊獵物的過程中，每只狼根據(jù)它的當前位置和獵物的位置更新下一次迭代的位置。在搜索獵物階段，α狼、β狼和δ狼彼此遠離來擴大搜索范圍，在攻擊獵物階段，α狼、β狼和δ狼開始收斂。

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

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

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

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

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

算法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]的隨機數(shù)rand；

6.ifrand

//Mp設為0.1

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

//刪除部分最優(yōu)用戶

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]內的隨機數(shù)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算法的實現(xiàn)。算法3所示為本文所設計的EnGWO算法流程。

算法3增強的灰狼優(yōu)化算法。

1.初始化灰狼種群Xi；

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

3.初始化參數(shù)；

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

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

6.分配三個最優(yōu)解Xα、Xβ、Xδ；

7.fortfrom 1 toITERmax

8.foreach 灰狼 agent

9.更新灰狼的位置；

//式(21)

10.end for

11.更新a,A,C；

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

13.更新最優(yōu)灰狼Xα、Xβ、Xδ；

14.t++；

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

16.更新Xα的適應度；

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

18.end for

4 實 驗

4.1 實驗數(shù)據(jù)集

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

4.2 社區(qū)檢測算法的性能

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

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

4.3 性能評價指標和參數(shù)設置

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

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

精度的計算式為：

召回率的計算式為：

F1-score的計算式為：

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

4.4 社交影響力分析實驗

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

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

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

續(xù)表3

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

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

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

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

5 結 語

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