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

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

中圖分類號：TP301.6

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

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

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

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

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

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

相比于上述方法，本文拓展了單個朋友網(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)建以用戶為頂點的單一關(guān)系網(wǎng)絡(luò)，然后將多個單一關(guān)系網(wǎng)絡(luò)利用多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)的加載功能復(fù)合為一個多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)，在復(fù)合網(wǎng)中，定義連接度，連接度的大小反應(yīng)了兩個用戶相似度的大小，從而可根據(jù)連接度做朋友推薦。頂點之間的不同關(guān)系會影響他們的相似度，所以需要為不同關(guān)系設(shè)置不同的權(quán)重值。

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

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

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

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

2.2 連接度的定義

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

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

2.4 算法描述

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

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

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

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

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

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

3 結(jié)語和展望

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

參考文獻(xiàn)：

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

[2]劉建國，周濤.個性化推薦系統(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].測繪學(xué)報，2011，30（2）.

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

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

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

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

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