基于改進蟻群算法的社交網(wǎng)絡(luò)好友推薦算法

高良誠

隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，與現(xiàn)實社會相比，社交網(wǎng)絡(luò)以其時空方面的優(yōu)越性，在人們的工作和生活中發(fā)揮著越來越重要的作用。社交網(wǎng)絡(luò)用戶眾多，數(shù)據(jù)龐大，高效地讓用戶找到可能成為好友的其他用戶顯得十分重要，但用戶普遍對周邊信息缺乏有效過濾，在好友推薦方面存在信息投送不精準和信息利用率低等問題，如何設(shè)計出高效的好友推薦算法已成為當前重要研究課題[1-2]。

經(jīng)典的好友推薦算法主要有基于用戶屬性特征相似度和基于用戶間的拓撲結(jié)構(gòu)兩種，但存在推薦結(jié)果不準確或推薦范圍過窄等問題。鏈路預(yù)測算法在好友推薦算法中得到廣泛應(yīng)用[3-4]，其基本思想是將社交網(wǎng)絡(luò)中的用戶作為網(wǎng)絡(luò)中的節(jié)點，利用好友屬性，計算節(jié)點之間的相似度，據(jù)此形成新鏈路來進行好友推薦，但在鏈路預(yù)測時，只考慮單一的網(wǎng)絡(luò)結(jié)構(gòu)，導(dǎo)致推薦準確度不高。目前好友推薦算法普遍綜合多元化的用戶屬性，如用戶基本信息、社交關(guān)系、地理位置等，解決推薦精度低、信息過載等問題[5-9]。文獻[10]利用聚類算法對用戶進行聚類，通過根節(jié)點到葉節(jié)點的加權(quán)求和進行推薦，文獻[11]提出了一種基于圖聚類與蟻群算法的社交網(wǎng)絡(luò)聚類算法，有效地緩解稀疏性問題與冷啟動問題，但均未充分考慮用戶位置信息。本文提出一種社交網(wǎng)絡(luò)中基于用戶屬性和改進蟻群算法的好友推薦算法(Friend recommendation algorithm based on user attributes and ant colony optimization algorithm，UA-ACO)，綜合考慮用戶基本信息、社交關(guān)系、地理位置等用戶屬性和交互信息，計算用戶相似度，將其作為鏈路預(yù)測的依據(jù)，并通過改進蟻群算法搜索好友用戶，增加好友推薦算法的精準度。

1 系統(tǒng)模型及問題描述

本文設(shè)計了基于用戶屬性與用戶交互的相似性二維圖模型，綜合考慮用戶屬性和用戶交互，計算用戶間的相似度來進行鏈路預(yù)測，建立用戶之間連接。系統(tǒng)模型用G=(V，E，W)表示，其中V(G)={v1,v2,…vn}表示網(wǎng)絡(luò)節(jié)點集合，對應(yīng)為社交網(wǎng)絡(luò)的用戶；E(G)={e1,e2,…,en}表示網(wǎng)絡(luò)中邊的集合；W(G)={w1,w2,…,wn}，對應(yīng)邊的權(quán)值，對于任意一個邊e∈E(G)，對應(yīng)用戶相似性值。

根據(jù)用戶屬性和交互信息計算各個用戶與目標用戶之間的相似性值，基于用戶屬性和交互信息的相似性計算公式為：

(1)

其中：Au,v為用戶u和v間的用戶屬性關(guān)系值，計算式為

(2)

其中：GF為用戶u和v共同好友數(shù)，PR為用戶u和v共同居住地數(shù)，w1和w2為比例系數(shù)，Du,v為用戶u和v之間的距離，Davg為用戶間平均距離。根據(jù)用戶對評分項目的評論信息計算各個用戶與目標用戶之間的相似性值，基于皮爾遜相關(guān)系數(shù)(Pearson correlation coefficient, PCC)的相似性計算公式為：

simu,v=

(3)

2 基于Q學習和蟻群算法的好友推薦算法

2.1 Q-Learning算法

Q-Learning是一種強化學習算法[12]，通過與環(huán)境交互，構(gòu)建(狀態(tài)，行動)函數(shù)值，根據(jù)函數(shù)值選擇下一動作。在狀態(tài)s下，賦予動作a獎勵和懲罰信息，進而能夠選擇最優(yōu)動作。用Q(s,a)表示動作a獲得收益的期望，在時刻t根據(jù)狀態(tài)s選擇動作a，并獲得報酬rt，Q值計算公式如下：

Qt+1(s,a)=(1-δ)Qt(s,a)+δ(rt+1+γmaxQ(st+1,a))

(4)

其中，δ為學習因子，δ∈(0，1)，γ為折扣因子，γ∈(0，1)。

通過公式(4)看出，Q-Learning算法的Q值可以作為蟻群算法中的信息素，從而加快蟻群算法初期的收斂速度。

2.2 改進蟻群算法

蟻群算法模擬螞蟻群體覓食過程，在解決離散優(yōu)化問題方面，具有收斂速度快和求解精度高等特點[13]。其核心思想是在一個加權(quán)圖中，螞蟻釋放信息素，根據(jù)路徑轉(zhuǎn)移概率選擇下一節(jié)點，并通過信息素更新驅(qū)動螞蟻選擇最優(yōu)路徑，實現(xiàn)螞蟻間信息交換，最終在圖中找出最優(yōu)路徑。

2.2.1 路徑轉(zhuǎn)移概率

(5)

其中：μj為節(jié)點j的信息素濃度，初始值為Q學習算法的Q值；α為路徑上信息素影響因子；ηij為路徑選擇函數(shù)，ηij=simi,j；β為路徑選擇影響因子；Tabuk存放螞蟻k目前訪問過的節(jié)點。

2.2.2 信息素更新

當螞蟻經(jīng)過某節(jié)點時，需要更新該節(jié)點上的信息素。節(jié)點上路過螞蟻數(shù)量越多，信息素濃度越大，該節(jié)點被選擇為下一節(jié)點的概率越大。

μj為節(jié)點j的信息素濃度，信息素更新規(guī)則如下：

(6)

其中，δ為信息素揮發(fā)因子，γ為折扣因子，Δμj為信息素的增量，由式(7)計算。

(7)

(8)

其中：Q為Q-Learning算法生成的初始信息素，Cost(i,j)為螞蟻k從節(jié)點i到當前節(jié)點j的費用函數(shù)，由式(9)計算。

(9)

其中：tu為目標用戶，hosps(tu,j)為圖中從目標用戶節(jié)點到用戶j對應(yīng)節(jié)點的路徑長度。

式(8)表明，螞蟻到節(jié)點j所經(jīng)過路徑費用越小，則節(jié)點j的信息素增量越大，螞蟻選擇節(jié)點j的概率越大，因此，費用低的路徑被選擇的概率變大。

每次迭代結(jié)束后，更新所有節(jié)點的信息素，公式如下：

μj′=(1-ρ)μj

(10)

其中：ρ為信息系揮發(fā)因子。

2.2.3 信息素擴散

2.3 UA-ACO算法實現(xiàn)步驟

初始階段，每個節(jié)點的信息素為Q-Learning算法的Q值，螞蟻隨機地分布在圖中節(jié)點上。螞蟻根據(jù)路徑轉(zhuǎn)移概率選擇下一節(jié)點，并進行信息素更新和擴散。重復(fù)迭代，直到符合結(jié)束條件。將節(jié)點按信息素降序排列，選擇信息素高的節(jié)點。

算法步驟如下：

1.使用公式(1)計算用戶之間的相似性。

2.初始化并精簡網(wǎng)絡(luò)。根據(jù)給定相似度閾值，刪除不滿足要求的用戶和獨立節(jié)點集。

3.將蟻群算法的初始信息素設(shè)置為Q-Learning算法迭代產(chǎn)生的Q值。

4.初始化蟻群算法的迭代次數(shù)NC。

5.將源節(jié)點放到螞蟻禁忌表tabu中，將k只螞蟻隨機放置到圖中節(jié)點上。

6.螞蟻根據(jù)公式(5)計算路徑轉(zhuǎn)移概率，選擇概率值大的鄰居節(jié)點作為下一節(jié)點。

7.按公式(6)對螞蟻選擇的節(jié)點進行信息素更新，并將該節(jié)點放到禁忌表tabu中。

8.重復(fù)步驟6 和步驟7 直到路徑長度超過5。

9.按照公式(10)全局更新信息素。

10.按2.2.3方法進行信息素擴散。

11.重復(fù)步驟5～步驟10直到迭代次數(shù)超過NC，將節(jié)點信息素降序排列，選擇信息素濃度高的節(jié)點。

3 實驗與結(jié)果分析

本文采用人人網(wǎng)作為數(shù)據(jù)來源，實驗環(huán)境為PC機，PC機的配置為8GB內(nèi)存，i7 8550處理器，使用Matlab進行仿真。設(shè)置參數(shù)w1=0.8，w2=0.9，δ=0.8，γ=1.1，α=1，β=1.2，θ=0.1，信息系揮發(fā)因子ρ=0.2，螞蟻數(shù)量150，迭代次數(shù)NC為100。

準確率、召回率以及F1-measure 是好友推薦算法的重要指標。準確率是指推薦好友為真實好友數(shù)量與推薦好友數(shù)量的比例，召回率是推薦的真實好友數(shù)量與數(shù)據(jù)集中實際好友數(shù)量的比例，F(xiàn)1-measure是綜合衡量指標。本文對UA-ACO算法、基于用戶的協(xié)同過濾算法(User-CF)[14]以及基于近鄰的協(xié)同過濾算法(NBCF)[15]，在準確率、召回率以及 F1-measure指標方面進行比較與分析。

準確率的計算公式如下：

(11)

召回率的計算公式如下：

(12)

F1-measure的計算公式如下：

(13)

圖1為不同算法的準確率對比。由圖1可見，隨著推薦好友數(shù)的增加，幾種算法的準確率均出現(xiàn)下降，但UA-ACO融合Q-Learning和改進蟻群算法，加快了算法收斂速度，算法能更快地實現(xiàn)較高的準確率，且準確率下降幅度較小。

圖1 不同算法的準確率對比

圖2為不同算法的召回率對比。由圖2可見，隨著推薦好友數(shù)的增加，幾種算法召回率均增大，UA-ACO采用改進蟻群算法，把Q-Learning算法的Q值作為蟻群算法的初始信息素，算法收斂速度快，召回率增加更明顯。

圖2 不同算法的召回率對比

圖3為不同算法的F1-measure對比。由圖3可見，本文算法的F1-measure值指標較好。

圖3 不同算法的F1-measure值對比

4 結(jié)語

文章提出了一種基于改進蟻群算法的社交網(wǎng)絡(luò)好友推薦算法，綜合考慮用戶基本信息、社交關(guān)系、地理位置等用戶屬性，結(jié)合用戶交互關(guān)系，計算用戶間的相似度進行鏈路預(yù)測，建立社交網(wǎng)絡(luò)二維圖，設(shè)定相似度閾值，去除不符合要求的用戶節(jié)點，減小好友推薦算法時間代價，在此基礎(chǔ)上，采用改進蟻群算法，相似性值高的用戶被推薦的可能性增大。仿真實驗表明，該算法準確率和召回率性能較好。下一步將充分研究用戶對地理位置敏感的好友推薦需求。