徐振宇,張欣欣,許 力

1(福建師范大學(xué) 計(jì)算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院,福州 350117)

2(福建省網(wǎng)絡(luò)安全與密碼技術(shù)重點(diǎn)實(shí)驗(yàn)室,福州 350007)

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

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

圖1 移動(dòng)社會(huì)網(wǎng)絡(luò)圖

高影響力節(jié)點(diǎn)挖掘是移動(dòng)社會(huì)網(wǎng)絡(luò)分析中的重要內(nèi)容.通過從網(wǎng)絡(luò)中識別前k個(gè)高影響力節(jié)點(diǎn),使得在網(wǎng)絡(luò)中利用這k個(gè)節(jié)點(diǎn)產(chǎn)生的影響傳播范圍最大速度最快.影響力節(jié)點(diǎn)挖掘在控制輿情傳播、扼制病毒傳染等領(lǐng)域有著廣泛應(yīng)用.對于移動(dòng)運(yùn)營商,通過挖掘影響力節(jié)點(diǎn)能夠以較少的代價(jià)得到高效的信息傳播能力從而獲得更高的效益.近年來大量學(xué)者從不同角度提出了不同算法進(jìn)行影響力分析,影響力節(jié)點(diǎn)的挖掘依然是熱門研究方向.由于真實(shí)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量巨大、節(jié)點(diǎn)間關(guān)系復(fù)雜且節(jié)點(diǎn)屬性繁多,移動(dòng)社會(huì)網(wǎng)絡(luò)中的最大化影響力節(jié)點(diǎn)挖掘仍然面臨著巨大的挑戰(zhàn).目前,大多的節(jié)點(diǎn)影響力計(jì)算方法可以分為基于網(wǎng)絡(luò)拓?fù)涮匦缘膯l(fā)式算法和基于傳播的貪心算法.

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

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

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

1 全局信任模型概述

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

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

(2)節(jié)點(diǎn)全局信任度計(jì)算階段.利用Beta 信譽(yù)模型,在節(jié)點(diǎn)的局部信任度的基礎(chǔ)上得到節(jié)點(diǎn)的全局信任度.

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

2 全局信任模型設(shè)計(jì)

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

本文中,網(wǎng)絡(luò)由G=(V,E) 組成,其中V是指網(wǎng)絡(luò)中的節(jié)點(diǎn)集,E是指節(jié)點(diǎn)的邊集.模型設(shè)計(jì)中Xv1表示節(jié)點(diǎn)v1的屬性列表,Nv1表示節(jié)點(diǎn)v1的鄰居節(jié)點(diǎn)列表.

2.1 局部信任度計(jì)算

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

(1)屬性信任

Baek 等[24]發(fā)現(xiàn)當(dāng)兩個(gè)人之間相似的特征更多時(shí),會(huì)使得雙方在一起交流更加舒服并有進(jìn)一步接觸的趨勢.Golbeck[25]發(fā)現(xiàn)用戶大多信任具有相似屬性的其他人.因此可以通過用用戶間屬性相似度來計(jì)算他們的信任度.我們通過Pearson 相關(guān)系數(shù)[26]來計(jì)算兩節(jié)點(diǎn)間的屬性序列相似度:

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

(2)共同好友相似信任

Lo 等[27]提出當(dāng)兩用戶都對第3 個(gè)用戶有良好的關(guān)系,則這兩個(gè)用戶就可能建立起良好的關(guān)系.因此,我們通過共同好友的相似度來計(jì)算節(jié)點(diǎn)間的信任值.該模型中利用Jaccard 系數(shù)[28]來計(jì)算兩用戶之間的共同好友相似度:

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

最后,節(jié)點(diǎn)的初始信任度通過屬性信任與共同好友相似信任結(jié)合計(jì)算:

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

2.2 利用Beta 信譽(yù)模型進(jìn)行全局信任度計(jì)算

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

Beta 信譽(yù)模型是一種結(jié)合用戶對目標(biāo)給出的反饋來計(jì)算用戶信譽(yù)值的基于Beta 分布的概率密度函數(shù)[29].該模型被用來表述無線通信節(jié)點(diǎn)之間網(wǎng)絡(luò)安全模型,而移動(dòng)社會(huì)網(wǎng)絡(luò)是社會(huì)網(wǎng)絡(luò)和移動(dòng)通信網(wǎng)絡(luò)結(jié)合形成的交叉網(wǎng)絡(luò)所以在本文的背景下也同樣適用.如果令rT和sT分別表示目標(biāo)實(shí)體T的正面評價(jià)和負(fù)面評價(jià)的個(gè)數(shù),則實(shí)體T的信譽(yù)值函數(shù)可以表示為:

那么信譽(yù)值的期望為:

此時(shí),實(shí)體信譽(yù)值的大小可以用其信譽(yù)值的期望來表示.在移動(dòng)社會(huì)網(wǎng)絡(luò)中,度更大的節(jié)點(diǎn)能夠?qū)⒆约旱男畔鞑サ礁嗟墓?jié)點(diǎn)上,則其在整個(gè)網(wǎng)絡(luò)中具有更高的信譽(yù)度,根據(jù)式(4)和式(7)我們得到下列公式.我們基于節(jié)點(diǎn)局部信任度的計(jì)算得出節(jié)點(diǎn)在網(wǎng)絡(luò)中的全局信任度:

其中,D為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)總和,dv1為節(jié)點(diǎn)v1的度數(shù),以dv1和網(wǎng)絡(luò)中總節(jié)點(diǎn)數(shù)的比值作為節(jié)點(diǎn)v1在整個(gè)網(wǎng)絡(luò)中的信譽(yù)度,并將節(jié)點(diǎn)與鄰居節(jié)點(diǎn)的信任度總和Tv1與信譽(yù)度相乘得到節(jié)點(diǎn)的全局信任度.

3 實(shí)驗(yàn)與結(jié)果分析

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

表1 數(shù)據(jù)集

圖2 3980.circles 網(wǎng)絡(luò)

圖3 348.circles 網(wǎng)絡(luò)

圖6 107.circles 網(wǎng)絡(luò)

圖4 0.circles 網(wǎng)絡(luò)

圖5 1684.circles 網(wǎng)絡(luò)

實(shí)驗(yàn)利用SI 傳染病模型來模擬現(xiàn)實(shí)中傳播的影響,并選取度中心性(DC),介數(shù)中心性(BC),PageRank算法(PR)以及緊密度中心性(CC)[30]4 個(gè)標(biāo)志性算法與本文提出的方案進(jìn)行實(shí)驗(yàn)對比,表2-表6中列出了每個(gè)算法所選取的前10 節(jié)點(diǎn).

表2 3980.circles 中前10 個(gè)影響力節(jié)點(diǎn)

表3 348.circles 中前10 個(gè)影響力節(jié)點(diǎn)

表4 0.circles 中前10 個(gè)影響力節(jié)點(diǎn)

表5 1684.circles 中前10 個(gè)影響力節(jié)點(diǎn)

表6 107.circles 中前10 個(gè)影響力節(jié)點(diǎn)

表7展示了各個(gè)算法與GTM 得到的前10 個(gè)影響力節(jié)點(diǎn)的交集情況.NDC、NBC、NPR、NCC和NGTM分別代表各個(gè)算法以及GTM 得到的前10 影響力節(jié)點(diǎn)集,例如在3980.circles 網(wǎng)絡(luò)中: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}.從表中可以發(fā)現(xiàn)GTM與DC 具有高度相似性,跟CC的重合度也較高.在前3 個(gè)網(wǎng)絡(luò)中GTM和PR 也具有不錯(cuò)的相似度,整體上跟BC的結(jié)果較為不同.由于各個(gè)算法尋找影響力節(jié)點(diǎn)的出發(fā)角度不同,所以GTM 在結(jié)果上與個(gè)別算法存在差異性,但是從表中可以發(fā)現(xiàn)GTM的整體精確度是在可接受范圍內(nèi).

表7 影響力節(jié)點(diǎn)選取對比

本文算法時(shí)間復(fù)雜度如下:

(1)在計(jì)算局部信任度時(shí)復(fù)雜度為O (n×m).

(2)在計(jì)算全局信任度時(shí)復(fù)雜度為O (n).

(3)在選擇最大影響力節(jié)點(diǎn)時(shí)復(fù)雜度為O (k).

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

表8 時(shí)間復(fù)雜度對比

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

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

圖7 3980.circles 傳播率對比圖

圖8 338.circles 傳播率對比圖

圖9 0.circles 傳播率對比圖

圖10 1684.circles 傳播率對比

圖11 107.circles 傳播率對比圖

4 總結(jié)

用戶影響力分析依然是移動(dòng)社會(huì)網(wǎng)絡(luò)領(lǐng)域中的一個(gè)重要研究方向,不僅涉及網(wǎng)絡(luò)自身的拓?fù)湫再|(zhì)還與社會(huì)屬性息息相關(guān).本文考慮了節(jié)點(diǎn)間信任度的影響,建立全局信任模型計(jì)算節(jié)點(diǎn)的局部信任度,并利用Beta信譽(yù)模型從局部信任度得到節(jié)點(diǎn)的全局信任度,根據(jù)全局信任度大小評估節(jié)點(diǎn)在網(wǎng)絡(luò)中的影響力大小.本文從局部的角度出發(fā)計(jì)算節(jié)點(diǎn)在本地網(wǎng)絡(luò)中的信任度大小從而減少了計(jì)算開銷,并在局部信任度的基礎(chǔ)上考慮了節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中的信譽(yù)值,將兩者相結(jié)合得到節(jié)點(diǎn)在網(wǎng)絡(luò)中的全局信任度大小.方案既保證了算法的較低時(shí)間復(fù)雜度也保證了能得到節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中的信任度的大小.本文在真實(shí)的網(wǎng)絡(luò)數(shù)據(jù)集上對該模型與經(jīng)典影響力算法進(jìn)行實(shí)驗(yàn)對比,結(jié)果表明,本文提出的全局信任模型不僅具有更低的時(shí)間復(fù)雜度,并且在保證節(jié)點(diǎn)高可信度與合理精確度的同時(shí)也具有良好的影響傳播能力.