移動社會網絡中基于全局信任模型的用戶影響力計算①

徐振宇,張欣欣,許 力

1(福建師范大學 計算機與網絡空間安全學院,福州 350117)

2(福建省網絡安全與密碼技術重點實驗室,福州 350007)

社交網絡(social networks,SNs)是一種人與人之間的關系與互動的結合[1].社交網絡把網絡中的每個節點看作參與這個網絡中人的抽象,每個人之間的關系則抽象成節點之間的連邊,網絡中每個人的行為不同且具有不同的屬性特征.在線社交網絡的起點是電子郵件的出現,早期的電子郵件解決了遠程的郵件傳輸問題,人們用電子郵件交換信息所構成的關系網絡就是在線社交網絡的最早形式.

隨著互聯網技術和無線技術的迅猛發展,移動社會網絡(mobile social networks,MSNs)應運而生[2].如圖1,移動社會網絡是從在線社交網絡演化而來的一種用戶驅動的移動通信網絡.這種網絡具有更加顯著的泛在性和移動性,其中包括節點(用戶)的社交連接[3].同時,移動社會網絡也具有移動通信網絡和在線社交網絡的一些基本屬性,Dong 等[4]發現移動社交網絡具有典型的無尺度網絡和小世界網絡屬性.Pietil?nen 等[5]發現移動社會網絡中人們表現出空間上復雜的移動性以及各個用戶具有復雜的個人屬性.移動社會網絡的發展給人們的日常生活帶來很多便利的服務,例如基于位置的可穿戴設備,醫療保健以及移動社會網絡服務等.

圖1 移動社會網絡圖

高影響力節點挖掘是移動社會網絡分析中的重要內容.通過從網絡中識別前k個高影響力節點,使得在網絡中利用這k個節點產生的影響傳播范圍最大速度最快.影響力節點挖掘在控制輿情傳播、扼制病毒傳染等領域有著廣泛應用.對于移動運營商,通過挖掘影響力節點能夠以較少的代價得到高效的信息傳播能力從而獲得更高的效益.近年來大量學者從不同角度提出了不同算法進行影響力分析,影響力節點的挖掘依然是熱門研究方向.由于真實網絡中節點數量巨大、節點間關系復雜且節點屬性繁多,移動社會網絡中的最大化影響力節點挖掘仍然面臨著巨大的挑戰.目前,大多的節點影響力計算方法可以分為基于網絡拓撲特性的啟發式算法和基于傳播的貪心算法.

啟發式算法通過考慮網絡的拓撲結構來衡量網絡中節點的重要性,并把重要性高的節點作為高影響力節點.Freeman[6]首先提出用度中心性(degree centrality,DC)衡量網絡中節點的重要性,按照節點的度中心性大小衡量節點的影響力強度.以圖中的最短路徑經過一個節點的次數表現了該節點與其他節點的互動程度這一觀點提出了介數中心性(betweenness centrality,BC)[7]這一指標來評價節點在網絡中的影響力強度.PageRank (PR)算法[8]屬于特征向量中心性的一種變體.節點的影響指標定義為PR 值,如果一個網頁被很多其他網頁鏈接到的話這個網頁的PR 值會相對較高,也就是更加重要.陸曉野等[9]從社區的角度提出基于節點頻度中心度的挖掘算法.張憲立等[10]在PageRank基礎上提出反向PageRank 算法并與度中心性結合得到一種混合的啟發式算法(heuristic algorithm of mixed PageRank and degree,MPRD).Kitsak 等[11]提出了核心度(coreness)作為評價節點在網絡中影響力的指標,利用k-核分解[12]計算在網絡中各個節點的影響力.Morone 等[13]基于滲透理論提出了集體影響(collective influence,CI)這一網絡拓撲指標,利用滲透模型找出被破壞就會使整個網絡崩潰的節點,把這些節點集作為影響力前k節點.宋甲秀等[14]在集體影響的基礎上提出了局部集體影響算法(local collective influence rank algorithm,LCIR)使得影響力的傳播更加穩定.康玲等[15]對網絡中的節點根據緊密度情況重新排序,并繪制網絡的區域密度曲線,在密度圖中波谷點兩側選取一定比例的節點作為影響力節點.楊樹新等[16]考慮局部方法的適宜度量層級與網絡拓撲的差異性,提出一種新的基于3 級鄰居的節點影響力度量法(three-level influence measurement,TIM).

基于傳播的貪心算法通過貪心策略近似的追求最優解:初始設置空的影響力節點集,并不斷向節點集中添加當前網絡中最具影響力的節點.Kempe 等[17]證明影響力最大化問題是NP-hard 問題,并提出原始貪心策略用于求影響力前k節點.使用基于子模塊函數的分析框架證明了原始貪心策略所獲得的解決方案對于幾種類型的模型而言,在最優值的63%之內.Leskovec等[18]提出CELF (cost-effective lazy-forward)方法根據影響力擴散的子模態特性來避免影響范圍的冗余計算從而提高了貪心算法的計算效率.Kim 等[19]基于IC 模型提出一種獨立路徑算法(independent path algorithm,IPA)來近似計算節點的影響力傳播能力.Kianian 等[20]在IPA的基礎上考慮到兩條影響路徑的相關性并與啟發式算法結合提出一種高效的啟發式獨立路徑算法(heuristic independent path algorithm,HIPA).李國良等[21]針對多社交網絡中影響力傳播問題,使用節點間具有最大傳播概率的路徑來近似衡量節點間的傳播概率.

上述方法雖然在影響力最大化研究上做出了重要貢獻,但是實際社會網絡中信息傳播并不完全基于網絡的拓撲特性,它們未考慮到信任對于用戶間交互的重要性.Asim 等[22]根據多種信任度計算方法提出了一種社會網絡信任模型(SNTrust model)揭示了在本地網絡中節點的影響力和信任度是存在著聯系的.例如:若兩個人之間具有更高的相似度,則相互之間的信任度越高,也越有利于兩者間信息的交換.因此,可以用信任度來評價節點在其相鄰節點中的影響力,并且節點的偏好以及節點間的信任關系在很長一段時間內是一種較為穩定狀態,只有當外界環境發生重大變化時才會改變,所以靜態網絡中節點的信任度可以用于刻畫這個網絡一段時間內網絡中節點的狀態以及節點間的關系.然而,盡管某一用戶節點在其鄰居節點中信任度高,但是并不能證明它就是整個網絡中的高影響力節點.為了解決這些問題,我們提出一種基于鄰居節點間信任度和Beta 信譽模型[23]的全局信任模型(global trust model,GTM) 用于計算網絡中節點的影響力.利用SI 模型,在真實網絡數據集中與啟發式算法所挖掘的影響力節點集合和其傳播效果進行比較,證明了本文所提出模型在保證精確性和傳播能力的同時,還具有更低的時間復雜度.

1 全局信任模型概述

為解決影響力最大化選擇前k節點問題,本文提出了一種基于鄰居節點間信任度和Beta 信譽模型的影響力節點挖掘全局信任模型.該模型分為3 部分:節點局部信任度的計算,節點全局信任度計算,影響力節點選擇.

(1)節點局部信任度計算階段.計算節點與鄰居節點間的屬性信任度和共同好友相似信任度,結合一起得到節點在鄰居節點中的局部信任度.

(2)節點全局信任度計算階段.利用Beta 信譽模型,在節點的局部信任度的基礎上得到節點的全局信任度.

(3)影響力節點選取階段.通過對節點的全局信任度大小排序,選取全局信任度最大的前k節點,把這些節點作為影響力前k節點.

2 全局信任模型設計

在本節我們提出一種新的信任模型設計方式.首先從局部的角度計算節點的初始信任值,再從全局的角度對節點的信任值進行再計算得到節點的全局信任值,最后選取其中的前k節點作為最大影響力節點.

本文中,網絡由G=(V,E) 組成,其中V是指網絡中的節點集,E是指節點的邊集.模型設計中Xv1表示節點v1的屬性列表,Nv1表示節點v1的鄰居節點列表.

2.1 局部信任度計算

在計算局部信任度中,我們考慮兩個因素來計算:屬性信任,共同好友相似信任.

(1)屬性信任

Baek 等[24]發現當兩個人之間相似的特征更多時,會使得雙方在一起交流更加舒服并有進一步接觸的趨勢.Golbeck[25]發現用戶大多信任具有相似屬性的其他人.因此可以通過用用戶間屬性相似度來計算他們的信任度.我們通過Pearson 相關系數[26]來計算兩節點間的屬性序列相似度:

其中,Xv1和Yv2分別為節點v1和v2的屬性序列,ρXv1,Yv2表示節點v1和v2之間的屬性信任相似度.

(2)共同好友相似信任

Lo 等[27]提出當兩用戶都對第3 個用戶有良好的關系,則這兩個用戶就可能建立起良好的關系.因此,我們通過共同好友的相似度來計算節點間的信任值.該模型中利用Jaccard 系數[28]來計算兩用戶之間的共同好友相似度:

其中,Nv1為節點v1的鄰居節點集合,Nv2是節點v2的鄰居節點集合,J(Nv1,Nv2) 表示節點v1和v2之間的共同好友相似信任度.

最后,節點的初始信任度通過屬性信任與共同好友相似信任結合計算:

其中,Tv1v2是節點v1和v2之 間的信任度,α為屬性信任占的比例,β為共同好友相似信任的占比,α和β都選取0.5.Tv1為節點v1與其鄰居節點信任度的總和,n是節點v1的鄰居節點數,以節點v1與其鄰居節點信任度總和的均值作為其局部信任度LTv1.

2.2 利用Beta 信譽模型進行全局信任度計算

盡管節點的局部信任度可以反映出其在本地網絡中的影響力大小,但并不能代表它在整個網絡中的重要性程度.目前大多的信任模型通過計算節點在本地網絡中與相連鄰居節點集的信任度大小來評價節點的影響力,但是這種方法可能會導致由于節點的鄰居節點較少使得盡管節點在本地網絡中的信任度很高,但是在整個網絡中卻并沒有相應的影響力.針對這一問題,我們利用Beta 信譽模型來解決.

Beta 信譽模型是一種結合用戶對目標給出的反饋來計算用戶信譽值的基于Beta 分布的概率密度函數[29].該模型被用來表述無線通信節點之間網絡安全模型,而移動社會網絡是社會網絡和移動通信網絡結合形成的交叉網絡所以在本文的背景下也同樣適用.如果令rT和sT分別表示目標實體T的正面評價和負面評價的個數,則實體T的信譽值函數可以表示為:

那么信譽值的期望為:

此時,實體信譽值的大小可以用其信譽值的期望來表示.在移動社會網絡中,度更大的節點能夠將自己的信息傳播到更多的節點上,則其在整個網絡中具有更高的信譽度,根據式(4)和式(7)我們得到下列公式.我們基于節點局部信任度的計算得出節點在網絡中的全局信任度:

其中,D為網絡中的節點數總和,dv1為節點v1的度數,以dv1和網絡中總節點數的比值作為節點v1在整個網絡中的信譽度,并將節點與鄰居節點的信任度總和Tv1與信譽度相乘得到節點的全局信任度.

3 實驗與結果分析

實驗數據集來源是斯坦福大學Facebook 網絡(http://snap.stanford.edu/data/ego-Facebook.html),對本文提出的模型進行實驗分析,并與傳統的選取影響力節點算法進行實驗對比評估模型的精確度與影響力最大化效果.實驗環境為MacBook Pro (16-inch,2019),2.6 GHz hexa-core Intel Core i7 處理器,16 GB 2 667 MHz DDR4 內存以及Intel UHD Graphics 630 1536 MB 圖形卡.數據集包括節點的部分屬性以及節點間的社交關系,考慮到數據集中節點屬性數量并不一致,我們選擇整個數據集其中的5 個子網進行實驗,并且每個子網中各個節點的屬性數量相等,表1展示了數據集的相關信息,圖2-圖6展示了5 個網絡的拓撲結構.

表1 數據集

圖2 3980.circles 網絡

圖3 348.circles 網絡

圖6 107.circles 網絡

圖4 0.circles 網絡

圖5 1684.circles 網絡

實驗利用SI 傳染病模型來模擬現實中傳播的影響,并選取度中心性(DC),介數中心性(BC),PageRank算法(PR)以及緊密度中心性(CC)[30]4 個標志性算法與本文提出的方案進行實驗對比,表2-表6中列出了每個算法所選取的前10 節點.

表2 3980.circles 中前10 個影響力節點

表3 348.circles 中前10 個影響力節點

表4 0.circles 中前10 個影響力節點

表5 1684.circles 中前10 個影響力節點

表6 107.circles 中前10 個影響力節點

表7展示了各個算法與GTM 得到的前10 個影響力節點的交集情況.NDC、NBC、NPR、NCC和NGTM分別代表各個算法以及GTM 得到的前10 影響力節點集,例如在3980.circles 網絡中:NDC={4030,4023,3998,3982,4014,3997,4031,4021,3994,4004}、NBC={4023,4030,3998,4031,4014,4027,4002,4017,4038,4020}、NGTM={4030,4023,3998,3982,3997,4021,4014,4009,3994,4031}.從表中可以發現GTM與DC 具有高度相似性,跟CC的重合度也較高.在前3 個網絡中GTM和PR 也具有不錯的相似度,整體上跟BC的結果較為不同.由于各個算法尋找影響力節點的出發角度不同,所以GTM 在結果上與個別算法存在差異性,但是從表中可以發現GTM的整體精確度是在可接受范圍內.

表7 影響力節點選取對比

本文算法時間復雜度如下:

(1)在計算局部信任度時復雜度為O (n×m).

(2)在計算全局信任度時復雜度為O (n).

(3)在選擇最大影響力節點時復雜度為O (k).

表8列出GTM與另外4 個算法的時間復雜度對比,從表中可以看出GTM 相比其他算法具有更低的時間復雜度.

表8 時間復雜度對比

SI 模型[31]是經典的傳染病傳播模型,用來模擬那些感染后不能治愈的疾病在網絡中的傳播情況.在SI模型中,人群數量的總和不變,把人群劃分為易感染者(susceptible,S)和感染者(infected,I)兩類,其中S 用來表示還未被感染的人,I 用來表示已被感染的人.我們選取每個算法所得的前5 個最大影響力節點作為初始影響力節點,將其狀態設置為I,根據這些算法選出來的影響力節點在網絡中的影響傳播能力進行比較可以發現,我們方案的節點在網絡中具有不錯的傳播能力.

考慮到真實網絡中人們的交互依賴于相互間的信任度,人們對信任度較大的人所提出的意見會更容易接納,也更有力于信息的傳播,而信任度較小的人意見并不能被很好地傳播.即若一個節點局部信任度較大可以很好地將信息傳播給鄰居節點,而信任度較小的節點只能夠接受信息而不能夠傳播信息.所以我們選取網絡中節點局部信任度的均值作為兩節點間是否有信息傳播的閾值γ.當信息從v1向v2傳 播時,若v1的局部信任度大于 γ則v2接受信息,信息傳遞成功.圖7-圖11展示了在5 個網絡中每個算法的傳播率.圖7可以看出DC 跟GTM 具有最大的傳播率;圖8中發現,GTM相比其他算法的初始傳播速度要更快,BC 算法盡管傳播速度上最慢,但是在傳播范圍上最大;圖9觀察到GTM的傳播速度在最初處于領先位置之后趨于中流水平;圖10中GTM 跟DC 具有同樣的傳播率并且都明顯優于別的算法,其中BC的傳播率最低;圖11看到GTM 在傳播的初期具有最快的傳播效率,盡管之后傳播速度低于BC和CC,但在最終的傳播范圍上都相同.綜上所述,我們可以發現GTM 在5 個網絡的傳播率都有著良好且穩定的效果.

圖7 3980.circles 傳播率對比圖

圖8 338.circles 傳播率對比圖

圖9 0.circles 傳播率對比圖

圖10 1684.circles 傳播率對比

圖11 107.circles 傳播率對比圖

4 總結

用戶影響力分析依然是移動社會網絡領域中的一個重要研究方向,不僅涉及網絡自身的拓撲性質還與社會屬性息息相關.本文考慮了節點間信任度的影響,建立全局信任模型計算節點的局部信任度,并利用Beta信譽模型從局部信任度得到節點的全局信任度,根據全局信任度大小評估節點在網絡中的影響力大小.本文從局部的角度出發計算節點在本地網絡中的信任度大小從而減少了計算開銷,并在局部信任度的基礎上考慮了節點在整個網絡中的信譽值,將兩者相結合得到節點在網絡中的全局信任度大小.方案既保證了算法的較低時間復雜度也保證了能得到節點在整個網絡中的信任度的大小.本文在真實的網絡數據集上對該模型與經典影響力算法進行實驗對比,結果表明,本文提出的全局信任模型不僅具有更低的時間復雜度,并且在保證節點高可信度與合理精確度的同時也具有良好的影響傳播能力.