一種Device-to-Device移動社交網絡中的熱點文件預測方法

張霄宏,侯海杰,任建吉

(河南理工大學 計算機學院,河南 焦作 454000)

1 引 言

社交網絡是提供一個在人群中分享興趣、愛好、狀態和活動等信息的在線平臺,一般說來移動社交網有基于Web的社交網絡和基于Device-to-Device(D2D)方式的移動社交網絡.基于web的社交網絡主要在傳統的社交網基礎上,通過增加無線移動設備訪問Internet的功能,實現對移動社交網絡技術的支持;基于Device-to-Device(D2D)方式的移動社交網絡主要基于移動用戶彼此之間的偶遇而自發式建立.因此基于D2D方式的移動社交網絡和基于Web的社交網絡的信息分享還是有很大不同的,主要表現在一下幾點:

1)傳播媒介不同.基于Web的社交網絡主要通過互聯網來進行信息的傳播,而基于D2D移動社交網絡以WLAN熱點形式來傳輸數據的,無需WiFI外部聯網環境.

2)用戶的朋友圈的規模不同.基于Web的社交網絡由于通過互聯網傳播信息,所以用戶可以擁有較為龐大的朋友圈,可以和認識的人分享信息也可以和陌生人分享信息,而基于D2D的移動社交網絡由于是基于偶遇的,所以只有倆個人在現實生活中相遇才能相互分享信息,因此基于D2D的移動社交網絡的朋友圈的規模比基于Web的要小很多;

3)用戶行為方式不同.基于Web的社交網絡的用戶行為包括轉發、評論、點贊等,而基于D2D移動社交網絡的用戶行為只有分享文件.

基于Web社交網絡的熱點資源還具有傳播廣泛、傳播周期短、實時性高、更新速度快等特點.而基于D2D移動社交網絡的熱點資源的特點是傳播廣泛,傳播周期較長,實時性不高,更新速度較快.

本文主要研究基于D2D移動社交網絡的文件分享特征.如何準確地預測一個文件能否成為熱點文件是本文研究的重點.為解決這個問題,本文首先分析了文件傳播過程中各個因素熱點文件的影響,然后對這些屬性進行量化,并配合有監督的機器學習方法建立了熱點文件預測模型.在選擇影響熱點文件的因素時,不僅考慮了文件的傳播屬性,而且還考慮了用戶對文件的影響力,計算熱度值,根據熱度值預測熱點文件.

本文的研究意義有以下幾點:第一,被分享的熱點文件往往能反映用戶的喜好,所以我們的研究可以運用到文件推薦中;第二,通過對熱點文件的分析,可以深刻了解影響熱點文件各個因素的重要性,從而可以應用到營銷或熱點提取中;第三,對熱點文件進行準確預測之后,服務商可以提前在服務器中緩存將要成為熱點的文件,減少重復流量.

本文的組織結構如下,第1節引言;第2節介紹相關工作以及數據的來源及相關信息;第3節進行文件的特征分析;第4節描述熱點文件的預測模型;第5節是實驗結果和分析;第6節是結語.

2 背 景

2.1 相關工作

近年來,越來越多的人開始研究對熱點的預測,尤其是對微博[2-4]的研究.李洋等人[5]指出微博信息傳播預測相關工作主要從以信息為中心、以用戶為中心以及以信息和用戶為中心這三個角度進行研究;趙龍文等人[6]從以用戶為中心的角度出發,提出基于意見領袖參與行為的微博話題熱度預測模型,以意見領袖的影響力及其參與行為等指標,研究微博熱點話題的發展趨勢和特征,分析并驗證了模型對不同話題類型的適用性,針對話題演化過程的階段性變動特征,對模型進行了改進和完善,提出了基于動態系數的多元線性回歸預測模型;黃蕉平[7]從以信息為中心角度出發,提出了新聞的八個維度指標,通過多元線性回歸模型和聚類分析算法來預測負面熱點新聞;Jinyoung Han[8]從以信息和用戶為中心出發,提出pin的傳播主要受pin的自身屬性影響,而不是用戶的特征,但是作者并未給出熱度預測模型.張旸等人[9]使用機器學習的分類算法,并通過微博上的不同重要性進行分析,提出了基于特征加權的預測模型,來預測微博是否被轉發.陳江等人[10]提出融合熱點話題的微博轉發預測方法,對背景熱點話題內容和傳播趨勢對用戶轉發行為的影響進行量化分析,提出融合背景熱點信息的轉發興趣、轉發活躍度、行為模式等特征,并基于分類算法建立了面向熱點話題相關微博的轉發預測模型.

本文從以信息和用戶為中心,結合用戶影響力和文件分享的相關指標,并對文件的熱度進行量化,用機器學習的方法訓練得到預測模型,通過該模型可以預測文件的熱度值,從而判斷該文件能否成為熱點.

2.2 數據來源及相關信息

本文采用的數據是由Xender公司提供,為一個月的數據,經過數據清洗之后,共2.09E+10條分享文件的記錄.本文采用20臺計算機組成的集群進行數據處理,每臺計算機配置24個核,32GB的內存和2TB的存儲空間.集群上部署了Spark計算框架.

利用該集群首先分析文件的分享情況,并將分析結果繪成洛倫茲圖展示在圖1中.在該圖中,橫軸代表文件個數的累計百分比,縱軸代表文件分享次數的累計百分比.由圖1可知,近30%的文件轉發次數占轉發總數的近70%,這一結果說明了研究熱點文件并對熱點文件進行預測的必要性.服務商可以通過預測的結果提前在服務器中緩存可能成為熱點文件的數據,從而可以大大提高用戶體驗.本文認為分享次數大于10000的文件為熱點文件,清洗后的數據集中有50000余個這樣的文件.10000只是定義的一個參數,也可以定義成其他參數,對熱點文件預測的方法沒有影響.

3 熱點文件分析

影響熱點文件的因素有文件的重要性、文件的敏感性、用戶的參與度與用戶的影響力.

圖1 文件分享情況Fig.1 File sharing

3.1 文件重要性

由于數據源中不包括用戶傳輸的文件內容,本文在定義文件重要性時主要參考文件的類型和大小.圖2是熱點文件的大小和類型分布(圖中文件大小的單位為MB),需要說明一點的是Xender允許分享的最大文件是2GB.我們可以看出熱點文件的大小在100MB以內,這說明用戶更加傾向于分享規模不是特別大的文件,其原因可能是分享過大的文件需要花費較長時間,而且大文件比較占用移動端設備的存儲空間.

圖2 熱點文件大小和類型Fig.2 Sizes and types of hot files

熱點文件中約有85%的文件是APP,其次是audio,即音頻文件,約占9%.當今社會APP相當流行,一些功能比較齊全且比較實用的APP非常容易成為熱點文件.用戶除了向身邊的朋友分享自己認為實用的APP外,對自己喜愛的歌曲等音頻文件也向朋友們分享,這比較符合當今的生活方式,尤其是當各大網站的歌曲收費以后,audio的分享會增多.

定義1.文件重要性:影響文件能否成為熱點的一個重要因素,由文件的大小和類型決定,可根據式(1)計算.

(1)

基于此,文件重要性可由式(1)計算.在該式中,Imp為文件的重要性,SizeRatio為某個文件的大小在所有文件大小中所占的比例,TypeRatio為該文件類型在所有文件類型中所占的比例.根據該式,計算了熱點文件和非熱點文件的重要性,計算結果如圖3所示.

從圖3上下兩子圖的對比中可以看出來80%的熱點文件的文件重要性在0.3以上,而80%的非熱點文件的文件重要性則在0.3以下.因此,文件的重要性可以作為影響一個文件是否能成為熱點文件的一個重要指標.

3.2 文件敏感性

從文件傳播的角度分析,成為熱點文件的方式有三種:第一種是短期爆發式傳播,在很短的時間就成為熱點;第二種是文件的傳播持續性比較強,每天都有一定的傳播量,過了一段時間成為熱點;第三種是兩者兼顧成為熱點.在本文工作中,我們將分析文件的短期傳播情況和持續傳播情況.為便于描述,本文定義了文件的短期分享率和文件的傳播持續性.

圖3 熱點文件和非熱點文件的重要性Fig.3 Importance of hot files and ordinary files

與很多基于Internet的信息共享方式不同,在本文所述的D2D環境中用戶之間只有在近距離接觸時才能進行文件共享.因此,互聯網環境中一個文件可能在短短的數小時或者數天之內就成為熱點不同,D2D環境中的一個文件要成為熱點往往要經歷更長的時間.已獲得的實驗數據記錄了文件在一個月內的傳播情況,本文選擇記錄第一周傳播情況的數據來計算短期分享率.

定義2.短期分享率:描述文件在較短一段時間內的傳播情況,可根據式(2)進行計算.

(2)

Short_share(fi)為文件fi的短期分享率,share(fi,first)為文件fi在第一周的分享次數;share(fj,first)為第j個文件在第一周被分享的次數,Ftotal為文件總數.

定義3.文件的傳播持續性:反映文件在將來繼續傳播的可能性,可根據式(3)計算.

(3)

Con(fi)表示文件的分享持續性,share(fi,Second)為文件fi在第二周文件被分享的次數.本文假設所有的文件都是從第一周開始被分享的,經過統計分析,熱點文件的短期分享率90%都在1.0E-5以上,而非熱點文件的短期分享率在(1.0E-9,1.0E-8)區間的文件數占總文件數的97.5%,由此可見,文件的短期分享率是影響文件成為熱點文件的一個比較重要的因素.

通過對文件得傳播持續性分析,99%的熱點文件的傳播持續性都在0.2以上,而非熱點文件的傳播持續性有80%的都在0.2以下,雖然有20%的非熱點文件的傳播持續性大于0.2,但是仍然可以說明文件傳播持續性對文件成為熱點文件起到一定的影響.

定義4.文件敏感性:反映文件成為熱點文件的可能性,可根據式(4)進行計算.

Sus(fi)=Shortshare(fi)+0.5*Con(fi)

(4)

在該式中,Sus(fi)表示文件fi的敏感性.文件的敏感性與文件的短期分享率和傳播持續性相關.圖5記錄了熱點文件和非熱點文件的敏感性分布.熱點文件中有90%的文件敏感性大于0.2,而非熱點文件中這樣的文件只有10%左右.因此,文件的敏感性是決定一個文件能否成為熱點的一個非常重要的因素.

圖4 熱點文件和非熱點文件的敏感性Fig.4 Susceptibility of hot file and ordinary file

3.3 用戶影響力

用戶總是基于自己的興趣、喜好及需求分享文件,對一個文件能否成為熱點文件有重要影響,因此需要研究用戶對文件傳播的影響力.本文將參考文獻[13]中新浪微博用戶影響力的計算方法,來評估D2D移動社交網絡中用戶的影響力.在本文中,用戶對某個文件傳播的影響力由用戶活躍度、用戶覆蓋度和用戶分享文件受歡迎程度三個因素決定.

定義5.用戶活躍度:反映用戶參與文件共享的積極程度,由用戶分享文件和接收文件的總次數來決定.

Acti=count(fsend)+count(frec)

(5)

活躍度可根據式(5)計算.在該式中,Acti代表某用戶的活躍度,fsend為該用戶分享的文件,count(fsend)為該用戶分享文件的總次數;frec、count(frec)為該用戶接收的文件和接收文件的總次數,用戶的活躍度可以反映用戶的在線時長.分析表明,在線時間越長的用戶,影響力越大.

定義6.用戶覆蓋度:反映用戶分享的文件被接受的程度,可由式(6)計算.

在式(6)中,Cov代表某用戶的覆蓋度,fsend_i和n分別表示該用戶分享的第i個文件和其分享的文件總數;Rece(fsend_i)表示文件fsend_i的所有接收者,count(Rece(fsendi))表示接收此文件的用戶數.用戶覆蓋度代表該用戶有幾個朋友和其朋友圈子的大小.用戶的朋友越多,圈子越大,影響力越大.

(6)

定義7.用戶傳播力度:反映用戶分享的文件受歡迎的程度,可由式(7)表示.

(7)

在式(7),Com表示某用戶傳播力度,share(fsend_i)表示fsend_i被分享的次數.Com的值等于該用戶所分享的所有文件在整個Xender平臺上被分享的總次數,代表該用戶所分享文件的受歡迎程度.用戶所分享的文件越受歡迎,用戶的影響力就越大.

結合以上定義,某個文件受到的用戶影響力可根據式(8)進行計算.

(8)

Inf(fi)表示參與傳播文件fi的所有用戶對該文件的影響力.在該式中, Actij、Covj和Comj分別表示參與傳播該文件的第j個用戶的活躍度、覆蓋度和傳播力度,m為參與傳播該文件的用戶數.圖4為參與熱點文件傳播的用戶影響力和參與非熱點文件傳播的用戶影響力分布,前者60%都分布在0.01以上,而后者將近有99%的都分布在0.001以下,可見用戶對文件能否成為熱點文件的影響是比較明顯的.

圖5 熱點文件和非熱點文件用戶影響力Fig.5 User influence of hot files and ordinary files

3.4 用戶參與力

定義8.用戶參與力:反映用戶對某個文件的分享和接收情況,可根據式(9)計算.

(9)

Par(fi)是文件的公眾參與力,Rece(fi)為公眾接收文件fi的用戶數量,Rece(fj)為公眾接收文件fj的用戶總數量,share(fi)為公眾分享文件fi的用戶數量,share(fj)為公眾分享文件fj的用戶總數量,total為D2D環境中共享的文件總數.圖6展示了熱點文件和非熱點文件的公眾參與力.90%以上的熱點文件的用戶參與力在0.2以上,而非熱點文件的用戶參與力大部分集中在(1E-4,1E-2)的區間中.因此,用戶參與力也可作為衡量熱點文件的一個重要的因素.

圖6 熱點文件和非熱點文件的用戶參與力Fig.6 User participation of hot files and ordinary files

4 熱點文件預測方法

通過上一節的分析發現文件重要性、文件敏感性、用戶影響力和用戶參與力四個因素對一個文件能否成為熱點有重要影響.本節將以這四個因素為基礎,利用多元線性回歸方法建立熱點文件的預測模型.

多元線性回歸分析模型[7]表示一種現象(因變量表示)與另外多種因素(自變量表示)的依存關系,多種因素共同對一種現象的分布與發展產生影響,用來估算因變量與多個自變量之間的線性相關度.多元線性回歸模型的一般表達式為:

Yi=β0+β1X1+β2X2+…+βnXn+εi

(10)

其中參數Yi是因變量,參數Xi是自變量,自變量Xi與因變量Yi有直接或間接的線性關系.β0、β1、β2、βn、εi都是與自變量無關的未知參數.其中β0為常數項,β1、β2…βn相應為自變量X1、X2…Xn的系數,表示對因變量的影響度,εi為對整體多元線性回歸函數的隨機干擾項.本文中影響熱點文件的因素有四個,符合多元線性回歸模型的特點.

本文選取文件重要性Imp、文件敏感性Sus、用戶影響力Inf以及公眾參與力Par文件作為因變量,選取文件熱度作為自變量.當某個文件的熱度達到特定值后,就成為熱點.文件熱度定義如下:

定義9.文件熱度:反映文件的傳播熱度,記為HDegree,其值可根據式(11)計算.

HDegree=lnshare(f)

(11)

多元線性回歸模型在應用時要求各自變量之間盡可能的獨立,自變量之間不存在多重共線性的問題,否則就會影響結果的可信度和一致性.由前面對四個因素的定義和分析可知,用于多元線性回歸模型的四個自變量都是相互獨立的,且不存在多重共線性的問題,所以滿足多元線性回歸模型的要求.

經過以上分析,文件熱度的多元線性回歸模型可表示為式(12).

HDegree=β0+β1Imp+β2Sus+

β3Inf+β4Par

(12)

5 實 驗

通過分析文件分享情況,發現分享次數不超過10次的文件占文件總數的90%左右,文件分享情況服從長尾分布.受此分布影響,如果對所有文件直接做回歸分析,那么將難以保證預測模型的準確度.為避免這種情況發生,把文件分享次數大于10000的數據集作為訓練集,共包括5112條記錄;把所有熱點文件和20%的非熱點文件作為測試集,共28117462條記錄.

通過在訓練集上的學習,HDegree可根據式(13)進行計算.

HDegree=8.007+2.317Imp+1.973Sus+0.040Inf+0.118Par

(13)

回歸系數表明對一個文件能否成為熱點文件影響最大的是文件重要性,其次是文件敏感性和公眾參與力,最后是用戶影響力,這也驗證了文獻[8]中的觀點:要成為熱點,影響最大的是內容本身,用戶影響次之.

本文將分享次數大于10000次的文件稱為熱點文件,其對應的HDegree值為9.21.因此,只有熱度不小于9.21的文件才能稱為熱點文件.根據本文模型預測的結果記錄在表1所示的混淆矩陣中.依據該表計算得到預測模型的準確率為90.82%.

根據表1計算本文預測模型的命中率為91.26%,與文獻[7]出的預測模型的命中率85%相比,本文模型的命中率提高了6.26%.

表1 預測結果Table 1 Prediction results

本文對熱點文件預測的精度進行了檢驗.根據檢驗結果,本文模型預測的文件熱度值與真實值的均方誤差為0.6715.

圖7 熱點文件預測結果Fig.7 Prediction results of hot file

根據這一結果,將實驗中熱點文件的真實熱度值與預測值的絕對差值大于0.6715的數據視為預測失敗.圖7為熱點文件的預測結果,熱點文件的熱度值精度為71.28%,精度較高,達到了較高的預測精度.

6 結 語

本文主要研究致力于文件共享的D2D移動社交網絡中熱點文件的預測問題,并以用戶和信息為中心,量化分析了影響一個文件成為熱點的各個因素,并利用機器學習方法設計了熱點文件預測模型.實驗表明,該預測模型能成功預測大約91.26%的熱點文件.本文的研究也有一定的局限性,這也是未來工作的方向.第一,我們認為所有的文件都是從第一周開始分享,但是有些文件是從第二周、第三周,甚至從第四周開始分享,這對我們的模型有一定的影響,將來的工作可以針對這個問題作出一些改進方法.第二,本文采用的機器學習方法是多元線性回歸,下一步將嘗試其他機器學習的方法,支持向量機[12]等.

：

[1] Hu Hai-yang,Li Zhong-jin,Hu Hua.Coo-perative content distribution in mobile social networks[J].Chinese Journal of Computers,2013,36(3):613-625.

[2] Kwak H,Lee C,Park H,et al.What is twitter,a social network or a news media?[C].International Conference on World Wide Web,

2010:591-600.

[3] Ding Zhao-yun,Jia Yan,Zhou Bin.Survey of data mining for microblogs[J].Jour-nal of Computer Research and Develop-ment,2014,51(4):691-706.

[4] Lou T,Tang J,Hopcroft J,et al.Lear-ning to predict reciprocity and triadic c-losure in social networks[J].Acm Tran-sactions on Knowledge Discovery from Data,2013,7(2):5.

[5] Li Yang,Chen Yi-heng,Liu Ting.Survey on pre-dicting information propagation in micr-oblogs[J].Ruan Jian Xue Bao/Journal of Software,2016,27(2):247-263.

[6] Zhao Long-wen,Gong Rong-tao,Chen Ming-yan.Hotness prediction research of microblog topics based on t-he participation of opinion leaders[J].Journal of Intelligence,2013，32(12):42-46.

[7] Huang Jiao-ping.Based on microbl-ogging early forecast and analyze negative hot news[D].South China University of Technology,2013.

[8] Han J,Choi D,Chun B G,et al.Coll-ecting,organizing,and sharing pins in pinterest:interest-driv-en or social-driven?[J].Acm Sigm-etrics Performance Evaluation Rev-iew,2014,42(1):15-27.

[9] Zhang Yang,Lu Rong,Yang Qing.Predi-cting retweeting in microblogs[J].Journal of Chinese Information Processing,2012,26(4):109-114.

[10] Chen Jiang,Liu Wei,Chao Wen-han.Microblog forwarding prediction based on hot topics[J].Journal of Chinese Information Processing,2015,29(6):150-158.

[11] Ahmed H,Ismail M A,Hyder M F,et al.Performance comparison of spark clusters configured conventionally and a cloud service ☆[J].Procedia Computer Science,2016,82:99-106.

[12] Wang X,Huang F,Cheng Y.Computational performance optimization of support vector machine based on support vectors[J].Neurocomputing,2016,211:66-71.

[13] Sina micro-blog user influence fo-rmula[EB/OL].http://data.weibo.com/mydata/minidata/personal,2016.

附中文參考文獻：

[1] 胡海洋,李忠金,胡 華,等.面向移動社交網絡的協作式內容分發機制[J].計算機學報,2013,36(3):613-625.

[3] 丁兆云,賈 焰,周 斌.微博數據挖掘研究綜述[J].計算機研究與發展,2014,51(4):691-706.

[5] 李 洋,陳毅恒,劉 挺.微博信息傳播預測研究綜述[J].軟件學報,2016,27(2):247-263.

[6] 趙龍文,公榮濤,陳明艷,等.基于意見領袖參與行為的微博話題熱度預測研究[J].情報雜志,2013，32(12):42-46.

[7] 黃蕉平.基于微博的負面熱點新聞早期預測分析[D].華南理工大學,2013.

[9] 張 旸,路 榮,楊 青.微博客中轉發行為的預測研究[J].中文信息學報,2012,26(4):109-114.

[10] 陳 江,劉 瑋,巢文涵,等.融合熱點話題的微博轉發預測研究[J].中文信息學報,2015,29(6):150-158.

[13] 新浪微博影響力計算公式[EB/OL].http://data.weibo.com/mydata/minidata/personal，2016.