一種基于復(fù)合網(wǎng)的面向微博關(guān)注的推薦算法

摘 要：針對(duì)在線社交網(wǎng)絡(luò)朋友推薦問題，嘗試?yán)妹枋龆喾N關(guān)系的多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)構(gòu)建社交網(wǎng)絡(luò)的復(fù)合網(wǎng)，引入連接度來表示對(duì)已連接朋友的喜愛程度，從而為用戶提供個(gè)性化推薦。本文以微博中為用戶推薦關(guān)注為例。

關(guān)鍵詞：多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)；連接度；個(gè)性化推薦；微博關(guān)注

中圖分類號(hào)：TP301.6

近年來，國(guó)內(nèi)微博快速發(fā)展，微博中蘊(yùn)含大量的信息，而對(duì)某一用戶而言，大部分信息是他并不感興趣的，同時(shí)不同用戶對(duì)不同的信息感興趣，個(gè)性化推薦可以部分解決社交網(wǎng)絡(luò)信息量過載，信息對(duì)用戶的冗余問題。因此，更加精確地為用戶推薦感興趣的信息成為微博運(yùn)營(yíng)商提升用戶體驗(yàn)的重要方式，個(gè)性化推薦算法發(fā)揮了舉足輕重的作用。

1 相關(guān)工作[1]

對(duì)于社交網(wǎng)絡(luò)的設(shè)計(jì)者來說，面對(duì)大量在線用戶、數(shù)據(jù)的稀疏性[2]以及他們的多樣化，如何幫助用戶發(fā)現(xiàn)新的感興趣的朋友是一個(gè)大的挑戰(zhàn)。流行的推薦算法基于假設(shè)：兩個(gè)用戶的相似度越高，則他們成為朋友的可能性越大。目前有三種主要的方法用于描述用戶的相似度：基于用戶的屬性特征、基于網(wǎng)絡(luò)結(jié)構(gòu)的局部特征和基于網(wǎng)絡(luò)結(jié)構(gòu)的全局特性。

（1）基于用戶的屬性特征進(jìn)行朋友推薦的思想：根據(jù)的用戶年齡、性別、學(xué)校、住址等注冊(cè)信息來計(jì)算用戶的相似度，注冊(cè)信息的內(nèi)容越相似，成為朋友的可能性就越大。

（2）基于網(wǎng)絡(luò)結(jié)構(gòu)的局部特征的方法利用用戶朋友網(wǎng)絡(luò)結(jié)構(gòu)的局部結(jié)構(gòu)信息。利用多種局部相似性測(cè)量指標(biāo)，如共同鄰居，Jaccard，Adamic/Adar等。

（3）基于網(wǎng)絡(luò)結(jié)構(gòu)的全局特性偵測(cè)朋友網(wǎng)絡(luò)中的所有路徑結(jié)構(gòu)，其中Google網(wǎng)頁排序算法PageRank的拓展應(yīng)用重啟動(dòng)隨機(jī)游走算法（Random Walk With Restart，RWR）。RWR算法是一個(gè)基于圖的隨機(jī)游走馬爾科夫鏈模型。

相比于上述方法，本文拓展了單個(gè)朋友網(wǎng)絡(luò)關(guān)系，基于多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)，融合了多種關(guān)系，引入連接度來描述用戶的相似度，提出了一種面向微博的基于多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)的推薦算法。

2 基于多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)的微博關(guān)注推薦算法

算法首先構(gòu)建以用戶為頂點(diǎn)的單一關(guān)系網(wǎng)絡(luò)，然后將多個(gè)單一關(guān)系網(wǎng)絡(luò)利用多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)的加載功能復(fù)合為一個(gè)多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)，在復(fù)合網(wǎng)中，定義連接度，連接度的大小反應(yīng)了兩個(gè)用戶相似度的大小，從而可根據(jù)連接度做朋友推薦。頂點(diǎn)之間的不同關(guān)系會(huì)影響他們的相似度，所以需要為不同關(guān)系設(shè)置不同的權(quán)重值。

2.1 多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型的構(gòu)建

實(shí)現(xiàn)算法的第一個(gè)關(guān)鍵問題是構(gòu)建一個(gè)有意義的網(wǎng)絡(luò)，使得其能真實(shí)反映用戶在社交網(wǎng)絡(luò)中的拓?fù)潢P(guān)系。構(gòu)建一個(gè)多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)，融合用戶的多種關(guān)系。具體構(gòu)建步驟如下：

（1）以用戶名為頂點(diǎn)，分別以關(guān)注、@、評(píng)論、共同的應(yīng)用等用戶已做出的行為為邊構(gòu)建單一關(guān)系的網(wǎng)絡(luò)，本文構(gòu)建的單一網(wǎng)絡(luò)均是無向網(wǎng)。單一關(guān)系網(wǎng)以頂點(diǎn)之間的關(guān)系命名，比如以關(guān)注為邊的網(wǎng)稱為關(guān)注網(wǎng)。

（2）因?yàn)槊恳粋€(gè)網(wǎng)都有共同的頂點(diǎn)（用戶），利用多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)的子網(wǎng)加載功能可以將它們復(fù)合成一個(gè)網(wǎng)，復(fù)合后的網(wǎng)的頂點(diǎn)之間可能有多種關(guān)系，至此面向微博的基于多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)已構(gòu)建完成。

2.2 連接度的定義

2.3 算法復(fù)雜度簡(jiǎn)化分析

根據(jù)“六度分離”[7]的實(shí)驗(yàn)結(jié)論，當(dāng)兩個(gè)頂點(diǎn)之間的最短路徑長(zhǎng)度大于7時(shí)，說明這兩個(gè)頂點(diǎn)的連接度較小，為進(jìn)一步降低算法的復(fù)雜度，最初執(zhí)行算法時(shí)的候選頂點(diǎn)集合設(shè)定為與給定頂點(diǎn)的最短路徑長(zhǎng)度小于等于4的頂點(diǎn)組成集合。

2.4 算法描述

對(duì)于一個(gè)特定的用戶，其必定對(duì)應(yīng)復(fù)合網(wǎng)中的某一頂點(diǎn)，為某一用戶設(shè)計(jì)個(gè)性化推薦關(guān)注的步驟為：

（1）計(jì)算確定復(fù)合網(wǎng)中與給定頂點(diǎn)的最短路徑長(zhǎng)度小于等于4的頂點(diǎn)組成集合S；

（2）刪除S中給定用戶已關(guān)注的頂點(diǎn)：SC=S-給定頂點(diǎn)已關(guān)注的頂點(diǎn)。若SC大于或等于需要推薦的關(guān)注數(shù)目N，則執(zhí)行步驟（3）；否則增大步驟（1）中的最短路徑長(zhǎng)度（每次增加1個(gè)單位），并從步驟（1）開始重復(fù)執(zhí)行；

（3）根據(jù)連接度公式，計(jì)算集合SC中所有頂點(diǎn)與給定點(diǎn)的連接度；

（4）根據(jù)推薦關(guān)注的數(shù)目N取出連接度排名（與給頂點(diǎn)的連接度越大，排名越靠前）前N的頂點(diǎn)組成集合TC；

（5）將TC中頂點(diǎn)對(duì)應(yīng)的用戶推薦給給定用戶。

3 結(jié)語和展望

現(xiàn)實(shí)的社交網(wǎng)絡(luò)含有多種對(duì)象，呈現(xiàn)出復(fù)雜的關(guān)系。傳統(tǒng)的社交網(wǎng)絡(luò)推薦僅僅考慮基于一種關(guān)系的網(wǎng)絡(luò)。充分挖掘和使用網(wǎng)絡(luò)中的多種對(duì)象以及多種關(guān)系，是提高社交網(wǎng)路的推薦算法精度的一個(gè)很好的角度，本文提出了一種基于多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)的推薦算法，但是沒有考慮有向網(wǎng)絡(luò)，用有向網(wǎng)絡(luò)來描述社交網(wǎng)絡(luò)多種關(guān)系的拓?fù)浣Y(jié)構(gòu)并用于個(gè)性化推薦是下一步的工作方向。

參考文獻(xiàn)：

[1]俞琰，邱廣華.基于混合圖的在線社交網(wǎng)絡(luò)朋友推薦算法[J].現(xiàn)代圖書情報(bào)技術(shù)，2011，11.

[2]劉建國(guó)，周濤.個(gè)性化推薦系統(tǒng)的研究進(jìn)展[J].自然科學(xué)進(jìn)展，2009，19（1）.

[3]隋毅.多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型及其相關(guān)性質(zhì)的研究[D].青島：青島大學(xué)，2012，04.

[4]陸鋒.最短路徑算法-分類體系與研究進(jìn)展[J].測(cè)繪學(xué)報(bào)，2011，30（2）.

[5]唐晉韜，王挺.適合復(fù)雜網(wǎng)絡(luò)分析的最短路徑近似算法[J].軟件學(xué)報(bào)，2011，10.

[6]汪小帆，李翔.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京：清華大學(xué)出版社，2006，10-45.

[7]朱亞麗.“六度分離”假說的信息學(xué)意義[J].圖書情報(bào)工作，2005，6.

作者簡(jiǎn)介：孫榮德（1987.03-），男，山東臨沂市平邑縣地方鎮(zhèn)新華村人，研究生，碩士，計(jì)算機(jī)軟件與理論專業(yè)，研究方向：數(shù)據(jù)挖掘。

作者單位：青島大學(xué) 信息工程學(xué)院，山東青島 266071