一種社交網(wǎng)絡中朋友推薦算法的研究

摘? 要：針對云計算環(huán)境下的社交網(wǎng)絡中朋友推薦中可能存在大量冗余，無效信息等缺點，提出了基于猴群算法的朋友社區(qū)推薦方案，該方案利用爬蟲程序獲得的新浪微博好友數(shù)據(jù)集，對用戶所在的社區(qū)進行劃分，并進一步使用猴群算法對社區(qū)中的朋友鏈接關(guān)系進行了劃分。仿真實驗中將該算法與基于用戶綜合相似度的推薦算法在查準率，查全率和F1指標方面進行對比，結(jié)果顯示，文章提出的算法都展現(xiàn)出了較好的效果。

關(guān)鍵詞：云計算;社交網(wǎng)絡;朋友推薦

中圖分類號：TP393.09;TP391.3 文獻標識碼：A? 文章編號：2096-4706（2021）02-0093-03

Abstract：In view of the shortcomings of redundancy and invalid information in the recommendation of friends in social networks in cloud computing environment，a friend community recommendation scheme based on monkey algorithm is proposed. In this scheme，the users community is divided by using the data set of Sina Weibo friends obtained by crawler program，and the link relationship of friends in the community is further divided by using monkey algorithm. In the simulation experiment，the algorithm is compared with the recommendation algorithm based on user comprehensive similarity in terms of precision，recall and F1 index. The results show that the algorithm proposed in this paper shows good results.

Keywords：cloud computing;social network;friend recommendation

0? 引? 言

伴隨著云計算、移動互聯(lián)技術(shù)的不斷發(fā)展，社交網(wǎng)絡已經(jīng)成了工作、生活中重要的組成部分。越來越多的人利用不同的社交軟件建立屬于自己的社交網(wǎng)絡，而在社交網(wǎng)絡中朋友是必不可少的重要組成部分，因此如何得到可靠的朋友成了社交網(wǎng)絡研究中的一個重要的方向。其中，朋友推薦方案的設(shè)計，不同的學者從不同的方向進行了研究。文獻[1]在朋友推薦方面提出了一種用戶興趣標簽匹配的方案，其中心思想是通過Word2Vec對訓練庫中的關(guān)鍵詞進行訓練，通過獲得的關(guān)鍵詞的向量，獲得一個詞向量的空間，最后通過余弦相似度的算法得到關(guān)鍵詞之間的相似度并進行驗證，結(jié)果說明該方案具有非常好的可靠性;文獻[2]提出了社交圈檢測算法，進而定義用戶間的社交圈相似性，并使用YouTube數(shù)據(jù)驗證了該文假設(shè)，使用Facebook自我網(wǎng)絡數(shù)據(jù)驗證了社交圈檢測方法的有效性;文獻[3]提出了一個新的在線社交網(wǎng)絡朋友推薦方法，為用戶提供了既快速又準確的朋友推薦，結(jié)果顯示能夠顯著增加在線社交網(wǎng)絡朋友推薦的準確性;文獻[4]則從圖論的角度出發(fā)，使用基于混合圖模型的隨機游走算法，為用戶提供個性化的朋友推薦，并通過參數(shù)的調(diào)節(jié)獲得圖中的網(wǎng)絡權(quán)重，實驗表明該算法能夠提高在線社交網(wǎng)絡朋友推薦的準確性;文獻[5]在社交網(wǎng)絡中提出了基于協(xié)同過濾的推薦方法，仿真結(jié)果表明該方法能夠有效推斷用戶行為。

以上學者從不同的方向進行了研究，取得了一定的研究成果。本文提出了一種基于猴群算法的朋友社區(qū)推薦方案，該方案從朋友社區(qū)的角度出發(fā)，提高了朋友推薦的效率。仿真實驗中，將本文算法具有較好的推薦效果。

1? 社交網(wǎng)絡概念

社交網(wǎng)絡是一種新的基于互聯(lián)網(wǎng)的網(wǎng)絡結(jié)構(gòu)，它通常是由結(jié)點和若干條邊組成。這種網(wǎng)絡結(jié)構(gòu)表達了社交網(wǎng)絡中的很多關(guān)聯(lián)關(guān)系。通常使用結(jié)點表示一個用戶或者一個團隊，而關(guān)聯(lián)關(guān)系代表了兩個用戶或者團體之間存在的某種關(guān)系。而社交網(wǎng)絡中的結(jié)點會隨著新結(jié)點的加入或者新的關(guān)聯(lián)關(guān)系而發(fā)生變化。而通常所說的社交網(wǎng)絡分析主要是使用一定的技術(shù)手段對網(wǎng)絡進行分析，它能夠根據(jù)用戶的興趣愛好不斷形成新的關(guān)系，從而使得社交網(wǎng)絡的規(guī)模逐漸變大。

2? 猴群算法

猴群算法[6]是Zhao和Tang在2018年提出的一種仿生類智能優(yōu)化算法，該算法主要模擬大自然中的猴群爬山的過程。該算法是一種簡單而有效的隨機性全局優(yōu)化算法，具有參數(shù)少、尋優(yōu)能力強、能有效解決復雜問題等優(yōu)點，逐漸成為進化計算研究領(lǐng)域中的常用算法。

該算法通常分為3個部分：

（1）爬過程。所謂爬過程是指每只猴子個體在當前的可行解范圍內(nèi)通過逐步爬行進行迭代，從而不斷尋找優(yōu)化問題的目標函數(shù)值的過程，具體的過程為：

步驟1：隨機生成向量ΔXi=（Δxi1，Δxi2，…，Δxin），i=1，2，…，M，分量Δxij以均等的概率取a，其中，j=1，2，…，n，a（a>0）為猴群每次爬的步長。

步驟2：計算，其中，j=1，2，…，n，a（a>0），向量fi′（Xi）=（fi1′（Xi），fi2′（Xi），…，fin′（Xi））為目標函數(shù)的所在位置的偽梯度。

步驟3：設(shè)Yi=Xi+a·sign（fin′（Xi）），其中，j=1，2，…，n，sign為符號函數(shù)

步驟4：當向量Yi=（yi1，yi2，…，yin）在[xmin，xmax]范圍內(nèi)，并且f（Yi）

（2）望過程。望過程主要是指猴子個體在經(jīng)歷了爬的過程之后達到了在各自范圍內(nèi)的最高峰。通過望動作向各個方向進行觀望，在各自的視野范圍查看是否存在比當前位置所在山峰的更高的山峰。如果存在就轉(zhuǎn)到更高的位置，否則就繼續(xù)進行爬行，具體過程為：

步驟1：在猴子可以觀察的范圍內(nèi)，隨機產(chǎn)生實數(shù)范圍為（xij-b，xij+b），隨機產(chǎn)生實數(shù)yij，設(shè)定Yi=（yi1，yi2，…，yin），那么Y=（Y1，Y2，…，YM），其中，b為觀察范圍內(nèi)的長度。

步驟2：當向量Yi=（yi1，yi2，…，yin）在變量范圍內(nèi)，并且f（Yi）

（3）跳過程。跳過程是為了能夠進入一個新的領(lǐng)域而進行的一個動作，即在當前的局部解內(nèi)無法獲得最優(yōu)解，然后重新進行搜索，將當前所有猴子的各自位置向著每只猴子朝向重心位置的方向進入到新的領(lǐng)域進行搜索，具體的操作為：

步驟1：在猴子跳的限定區(qū)間[c，d]中生成一個實數(shù)θ。

3? 基于改進的猴群算法的社區(qū)朋友推薦

隨著社交網(wǎng)絡范圍的不斷增大，有些無法在社交網(wǎng)絡進行注冊認識的好朋友，通過相同的興趣，共同的愛好會構(gòu)成潛在的關(guān)系，因此文章提出了一種改進的社區(qū)朋友推薦算法。首先，選用利用爬蟲程序獲得的新浪微博好友數(shù)據(jù)集，根據(jù)選定種子節(jié)點的好友列表中逐漸獲得新用戶的信息，但是對于活躍度低的用戶進行剔除，有助于算法整體性能提高，保證了參與算法的有效性，其次對用戶所在的社區(qū)進行劃分，主要過程是能夠根據(jù)不同用戶之間存在的鏈接關(guān)系進行劃分，在劃分過程中引入仿生學的猴群算法，利用猴群具有的良好的算法性能，并在此基礎(chǔ)上進行改進，將改進后的猴群算法與社區(qū)劃分進行結(jié)合，同時將社區(qū)網(wǎng)絡中的評價函數(shù)值與猴群算法的適應度進行一一對應。即每一個猴群算法中的個體都會對應社區(qū)網(wǎng)絡中的一種劃分的方法，這樣最后獲得猴群算法的最優(yōu)解的個體就是最優(yōu)社交的劃分方案。將猴群算法中的每一個個體的適應度值與不同社區(qū)中的多用戶進行所對應的，多用戶分布在不同的社區(qū)中，然后得到目標用戶所在的社區(qū)的用戶相似度，而在社區(qū)網(wǎng)絡中用戶之間的不同的相似度代表了網(wǎng)絡中的權(quán)重，因此用戶之間的相似度則采用綜合相似度進行計算。根據(jù)社交網(wǎng)絡中生成的對應矩陣，用戶的特征向量表明了用戶與用戶之間的鏈接關(guān)系，使用特征向量中的余弦相似度獲得用戶之間的鏈接信息關(guān)系的相似度，繼而計算出每一個用戶的屬性向量，根據(jù)這種屬性的余弦相似度得到不同用戶的個人信息相似度數(shù)值，最后通過對于用戶信息相似度進行綜合排序，將相似度最高的用戶推薦給好友。

4? 仿真實驗

為了進一步說明本文算法的效果，本文選擇了硬件環(huán)境是CPU為i5，內(nèi)存為4 GB DDR3，硬盤為1 TB，軟件環(huán)境為Matlab，操作系統(tǒng)為Windows 10，用戶數(shù)據(jù)庫來自微博的數(shù)據(jù)用戶作為研究對象。將本文算法與基于用戶綜合相似度的推薦算法在查準率，查全率和F1指標中三個指標作為參考進行對比。

4.1? 查準率

查準率是指查看結(jié)果的準確程度。其值等于目標用戶推薦出的正確好友數(shù)量與目標用戶推薦出的所有好友數(shù)量的比值。圖1顯示了兩種算法下的查準率結(jié)果。

圖1中顯示了基于用戶綜合相似度的推薦算法和本文算法的對比效果，從圖中發(fā)現(xiàn)隨著推薦人數(shù)的增加，兩種算法對應的曲線都呈現(xiàn)下降趨勢。這主要是因為伴隨著推薦人數(shù)逐漸增多，在原有的基礎(chǔ)上引入了不同的用戶，導致了用戶之間的相似度呈現(xiàn)出下降趨勢，不確定因素的用戶數(shù)量上升，因此導致查準率有所降低?？紤]到實際情況中的推薦用戶存在的多個潛在好友的情況，為了研究成果具有針對性，避免造成不必要的負面推薦影響，本文設(shè)定平均推薦為20人，當推薦人數(shù)為1的時候，本文算法的查準率明顯優(yōu)于基于用戶綜合相似度推薦算法，雖然隨著推薦人數(shù)的逐漸增多，查準率都有所下降，但本文算法依然具有優(yōu)勢，這說明了本文算法的效果。

4.2? 查全率

查全率是指查看結(jié)果是否全面的程度。其值等于目標用戶推薦出的正確好友數(shù)量與目標用戶好友數(shù)量的比值。圖2顯示了兩種算法下的查全率的結(jié)果。

圖2中顯示了基于用戶綜合相似度的推薦算法與本文算法的對比結(jié)果，從圖中得到隨著推薦人數(shù)不斷增加，兩種算法對應的曲線都呈現(xiàn)上升的趨勢，這是因為隨著推薦人數(shù)的不斷增加，搜索到的用戶信息更加的全面，隨著推薦人數(shù)不斷的上升，本文算法在整個曲線的總體上的查全率值始終優(yōu)于基于用戶綜合相似度的推薦算法，當人數(shù)在達到16人后，兩種算法的差距正在逐漸減少，但是相比之下，本文算法依然具有一定的優(yōu)勢，這也說明了本文算法在社交網(wǎng)絡的朋友推薦方面確實具有良好的效果，由于采用了猴群算法，使得在社區(qū)朋友推薦方面具有明顯的提升，提高了查詢廣度，擴大了交友的范圍，提升了尋找的效率。進一步說明了本文算法的效果。

4.3? F1指標

F1指標主要用來權(quán)衡查準率和查全率之間的權(quán)重關(guān)系，這是因為衡量一個良好的朋友推薦系統(tǒng)要兼顧準確率和查全率，其值等于查準率和查全率的積與兩者和的比值。圖3顯示了兩種算法下F1指標結(jié)果。

圖3中顯示了基于用戶綜合相似度的推薦算法與本文算法的對比效果，從整體上看，隨著平均推薦人數(shù)的增長，本文算法、基于用戶綜合相似度的推薦算法在F1方面都呈現(xiàn)先上升后下降的平穩(wěn)趨勢。當推薦的人數(shù)數(shù)量較少的時候，本文提出算法的Fl平均為0.251，而基于用戶綜合相似度推薦的F1為0.212。當推薦人數(shù)為12的時候，兩種算法都達到了最大值，本文提出算法的Fl為0.453，而基于用戶綜合相似度推薦的F1為0.421，當推薦人數(shù)大于12的時候，由本文算法和基于用戶綜合相似度推薦算法可知，本文算法得到的F1值為0.262，基于用戶相似度的推薦算法的F1值為0.247。由此可見，本文算法取得了更好的推薦效果。這主要是因為F1指標需要考慮查準率和查全率兩個指標，由于這兩個指標評價本身存在一定的同斥性，因此會導致出現(xiàn)先升后降的趨勢，但從整體上看，本文算法在綜合指標上還是優(yōu)于基于用戶綜合相似度的推薦算法，這說明了算法具有較好的穩(wěn)定性，說明了采用猴群算法的社交網(wǎng)絡推薦確實能夠提高效率，對用戶綜合信息形似度的排序，選擇相似度最高的用戶當作猴群個體進行求解得到推薦的好友，提高了算法推薦效率。

5? 結(jié)? 論

針對社交網(wǎng)絡中可能存在用戶信息推薦不準確的問題，提出了一種基于云計算下的社交網(wǎng)絡朋友推薦算法，在該算法中主要闡述了基于猴群算法的朋友社區(qū)推薦方案，仿真實驗數(shù)據(jù)說明該算法在社交網(wǎng)絡中具有較好的效果，下一步研究方向朝著用戶隱私安全進行考慮。

參考文獻：

[1] 程宏兵，王珂，李兵，等.一種高效的社交網(wǎng)絡朋友推薦方案 [J].計算機科學，2018，45（S1）：433-436+452.

[2] 馬秀麟，衷克定，劉立超.從大數(shù)據(jù)挖掘的視角分析學生評教的有效性 [J].中國電化教育，2014（10）：78-84.

[3] 王玙，高琳.基于社交圈的在線社交網(wǎng)絡朋友推薦算法 [J].計算機學報，2014，37（4）：801-808.

[4] 俞琰，邱廣華，陳愛萍.基于混合圖的在線社交網(wǎng)絡朋友推薦算法 [J].現(xiàn)代圖書情報技術(shù)，2011（11）：54-59.

[5] 劉航.關(guān)于用戶蹤跡融合協(xié)同過濾推薦的仿真研究 [J].計算機仿真，2020，37（7）：422-425+454.

[6] ZHAO R， TANG W. Monkey? Algorithm? for? Global Numerical Optimization [J]. Journal of Uncertain Systems，2008，2（3）：164-175.

作者簡介：陳暄（1979.03—），男，漢族，安徽祁門人，教師，副教授，碩士，研究方向：云計算、社交網(wǎng)絡。