唐四慧

(華南理工大學(xué) 工商管理學(xué)院，廣東 廣州 510640)

隨著互聯(lián)網(wǎng)應(yīng)用的普及，使用這些應(yīng)用的個(gè)體與個(gè)體之間的交互行為會(huì)產(chǎn)生一些大量的，相互作用的信息網(wǎng)絡(luò)，Newman在他的論文中將這種在結(jié)點(diǎn)上存有信息的網(wǎng)絡(luò)歸結(jié)為信息網(wǎng)絡(luò)，他舉的最典型的信息網(wǎng)絡(luò)的例子就是引文網(wǎng)；另一個(gè)就是萬(wàn)維網(wǎng)，這個(gè)網(wǎng)絡(luò)不同于互聯(lián)網(wǎng)，它是由網(wǎng)頁(yè)及網(wǎng)頁(yè)之間的鏈接組成的。[1]對(duì)于萬(wàn)維網(wǎng)的研究非常多，最多的研究領(lǐng)域是網(wǎng)頁(yè)的推薦算法，根據(jù)CNNIC的調(diào)查，2010年僅中國(guó)網(wǎng)頁(yè)數(shù)量達(dá)到600億個(gè)，年增長(zhǎng)率達(dá)78.6%，在這樣的龐大的網(wǎng)絡(luò)中如何有效的提供網(wǎng)頁(yè)搜索推薦確實(shí)是一個(gè)具有挑戰(zhàn)性的問(wèn)題。

一、研究背景

對(duì)于如此巨大的網(wǎng)頁(yè)數(shù)量，更多的研究是將推薦問(wèn)題聚焦在一些特定的應(yīng)用中，如Amazon的圖書(shū)推薦、Netflix的電影推薦、Youtube的視頻推薦、eBay的商品推薦等等。推薦系統(tǒng)各種各樣，包括協(xié)同過(guò)濾(collaborative filtering)推薦系統(tǒng)，基于內(nèi)容(content-based)推薦系統(tǒng)，混合(hybrid)推薦系統(tǒng)。[2]隨著用戶使用數(shù)據(jù)的不斷被記錄，基于用戶行為數(shù)據(jù)形成的信息網(wǎng)絡(luò)之上的推薦方法也隨之被提出，其中有周濤的資源分配算法，[3]Han的RankClus算法。[4]在周濤的資源分配算法中，他將用戶和產(chǎn)品的二部圖映射為產(chǎn)品單粒子圖，對(duì)邊和點(diǎn)進(jìn)行加權(quán)來(lái)做推薦的，這種映射的操作會(huì)使推薦問(wèn)題簡(jiǎn)化，但也會(huì)使得一些信息被丟失掉；在考慮了映射操作會(huì)使得異質(zhì)信息網(wǎng)絡(luò)的信息損失后，Han在其RankClus算法中，直接對(duì)異質(zhì)的信息網(wǎng)絡(luò)進(jìn)行排序和聚類操作，研究結(jié)果顯示這種不進(jìn)行映射的算法所得的排序結(jié)果和聚類結(jié)果都更加有意義。在一般的推薦算法中，都會(huì)用到排序這一環(huán)節(jié)，通過(guò)排序得到哪種商品是用戶最想購(gòu)賣(mài)或最想閱讀的。在Han的算法中，核心是利用聚類后的條件概率進(jìn)行排序，然后利用排序的結(jié)果來(lái)指征聚類的優(yōu)劣，他給的例子是會(huì)議—作者的兩類異質(zhì)網(wǎng)絡(luò)，對(duì)于多類異質(zhì)網(wǎng)絡(luò)僅是一帶而過(guò)沒(méi)有更詳細(xì)的交待，事實(shí)上，我們發(fā)現(xiàn)現(xiàn)實(shí)社會(huì)中更多的信息網(wǎng)絡(luò)包括兩種以上的異質(zhì)結(jié)點(diǎn)，本文中所研究的豆瓣網(wǎng)數(shù)據(jù)，它就包括小組，組員，圖書(shū)三類結(jié)點(diǎn)；另一個(gè)是在他的研究中假設(shè)會(huì)議這種結(jié)點(diǎn)之間是沒(méi)有關(guān)系的，關(guān)系僅存在于會(huì)議與作者，作者與作者之間；而我們的案例中，小組與小組，組員與組員，圖書(shū)與圖書(shū)，小組與組員，小組與圖書(shū)，組員與圖書(shū)之間均存在不同類型的關(guān)系，并且我們通過(guò)對(duì)組員的行為進(jìn)行分析后發(fā)現(xiàn)，小組，組員，圖書(shū)這三種結(jié)點(diǎn)在推薦中有先后關(guān)系，這些現(xiàn)象是Han的論文中不曾涉及的，因此我們認(rèn)為有必要對(duì)這一現(xiàn)象進(jìn)行分析，進(jìn)而產(chǎn)生更有效的推薦方法。

二、前人的研究

基于網(wǎng)絡(luò)的搜索，最早的研究我們可以追溯到Milgram的小世界實(shí)驗(yàn)，在Milgram的實(shí)驗(yàn)中，他選定了兩個(gè)目標(biāo)對(duì)象，一個(gè)是美國(guó)馬薩諸塞州沙朗的一位神學(xué)院研究生的妻子，另一位是波士頓的證券經(jīng)紀(jì)人。然后他在遙遠(yuǎn)的堪薩斯州和內(nèi)布拉斯加州招募發(fā)信者，要求發(fā)信者通過(guò)自己的熟人，用自己認(rèn)為盡可能少的傳遞次數(shù)，將信轉(zhuǎn)交到一個(gè)給定的目標(biāo)對(duì)象手中，實(shí)驗(yàn)的結(jié)果證明社會(huì)網(wǎng)絡(luò)是可達(dá)的并且是可導(dǎo)航的。[5]在2002年，Watts等人重做了上述實(shí)驗(yàn)也證明網(wǎng)絡(luò)的直徑是小的，并且網(wǎng)絡(luò)是可導(dǎo)航的。[6]Watts在其后來(lái)的研究中，對(duì)這種可導(dǎo)航性進(jìn)行了解釋，他認(rèn)為在實(shí)際的社會(huì)網(wǎng)絡(luò)中人們會(huì)根據(jù)各種各樣的標(biāo)準(zhǔn)來(lái)判斷兩人之間的距離，地理位置、職業(yè)、國(guó)籍、受教育程度、興趣愛(ài)好等都是很好的標(biāo)準(zhǔn)，這些標(biāo)準(zhǔn)將整個(gè)世界分為更小更特定的團(tuán)體，在對(duì)團(tuán)體進(jìn)行劃分的時(shí)候，通常存在多重標(biāo)準(zhǔn)。[7]這種結(jié)論的得出，是基于他前面實(shí)驗(yàn)的結(jié)果，在那次實(shí)驗(yàn)中他發(fā)現(xiàn)在搜索的早期大約在前兩、三步人們會(huì)考慮地理上與目標(biāo)對(duì)象接近，到了三步以后人們更多的考慮后續(xù)者在職業(yè)上是與目標(biāo)對(duì)象相似的。在整個(gè)搜索過(guò)程中，我們可以看到判斷標(biāo)準(zhǔn)是在變化的，因此我們考慮異質(zhì)信息網(wǎng)絡(luò)的搜索時(shí)，我們用異質(zhì)的樹(shù)結(jié)構(gòu)搜索方式更符合實(shí)際情況。但我們?cè)谧鰣D書(shū)或音樂(lè)的推薦的時(shí)候，與Watts不同的是，我們并不知道目標(biāo)是什么，更不要說(shuō)目標(biāo)的具體信息。

另一種搜索的研究是Gnutella網(wǎng)絡(luò)中的廣播搜索，它與我們這里研究的內(nèi)容相同的是用戶并不知道所要查找文件在網(wǎng)絡(luò)中的具體位置，因此在每次信息傳遞過(guò)程中不知道是接近還是遠(yuǎn)離了目標(biāo)節(jié)點(diǎn)。在這樣的搜索條件下，Gnutella采用的是一種廣播的方式進(jìn)行搜索，為了避免搜索范圍的幾何級(jí)數(shù)的增長(zhǎng)，在Gnutella網(wǎng)絡(luò)搜索中規(guī)定每次查詢的生存時(shí)間為5次或6次。為了減輕Gnutella中廣播搜索帶來(lái)的大量的流量負(fù)載，人們提出了一些改進(jìn)的方法如Yang和Garcia-Molina提出的有向廣度優(yōu)先搜索策略，[8]在這種搜索策略中要求源節(jié)點(diǎn)選擇一些能夠快速返回高質(zhì)量結(jié)果的鄰居并將查詢消息發(fā)給它們，為了能夠選擇“好”的鄰居，在每個(gè)節(jié)點(diǎn)中會(huì)存儲(chǔ)一些關(guān)于鄰居的簡(jiǎn)單的統(tǒng)計(jì)信息，這樣就自然而然的形成了我們前面所講的信息網(wǎng)絡(luò)——在結(jié)點(diǎn)上存有信息的網(wǎng)絡(luò)。這種搜索策略與我們研究的對(duì)象不同的是，在它進(jìn)行搜索過(guò)程中，它的鄰居會(huì)加入到搜索過(guò)程，而我們研究的圖書(shū)推薦或音樂(lè)推薦主要是用戶自己的查找，查找的深度會(huì)比有其它鄰居加入的算法要短，因?yàn)橐粋€(gè)人的精力是有限的。對(duì)于本地信息的存儲(chǔ)內(nèi)容，Yang和Garcia-Molina又提出了一種本地索引的方法，在這種方法中本地節(jié)點(diǎn)上會(huì)存儲(chǔ)與自己距離在r步之內(nèi)的所有節(jié)點(diǎn)的文件目錄。[8]

圖1 讀過(guò)與想讀關(guān)系圖

圖2 分類與排序關(guān)系圖[4]

(一)數(shù)據(jù)來(lái)源及收集方法

我們考慮圖書(shū)推薦是一個(gè)比較經(jīng)典的推薦例子，同時(shí)在豆瓣網(wǎng)上圖書(shū)、用戶、小組呈現(xiàn)出的多種類型的關(guān)系也比較符合異質(zhì)網(wǎng)絡(luò)的特性，在豆瓣網(wǎng)中每本圖書(shū)、每個(gè)用戶、每個(gè)小組都有一些介紹信息，這也符合我們對(duì)信息網(wǎng)絡(luò)的要求。此次實(shí)驗(yàn)的數(shù)據(jù)來(lái)自一個(gè)比對(duì)實(shí)驗(yàn)，我們先在圖書(shū)館中抽取了6萬(wàn)多條借閱記錄，然后再將借閱記錄中有的書(shū)，在豆瓣網(wǎng)上找出來(lái)，比對(duì)這兩種不同方式推薦圖書(shū)的效果，另外豆瓣網(wǎng)也有一個(gè)推薦效果的記錄就是每本書(shū)都有一個(gè)讀過(guò)和想讀的記錄，記錄下哪些用戶讀過(guò)，哪些用戶想讀，想讀的用戶我們可以理解為受了網(wǎng)上宣傳或讀過(guò)這些書(shū)的人的影響。我們共找到1291本圖書(shū)，有923個(gè)讀過(guò)這些書(shū)，簡(jiǎn)單的統(tǒng)計(jì)信息如表1。

表1 讀書(shū)的簡(jiǎn)單統(tǒng)計(jì)信息表

我們將讀過(guò)的人數(shù)和想讀的人數(shù)畫(huà)在圖上，得到圖1。從圖中我們找出那本想讀人數(shù)最多的書(shū)，書(shū)的編號(hào)為1049136，書(shū)名為《數(shù)學(xué): 確定性的喪失》，原來(lái)共有53人讀過(guò)，現(xiàn)在有91人想讀。這本書(shū)只被一個(gè)名為數(shù)學(xué)的小組所收藏，如果用戶參加了這個(gè)小組，我們可以認(rèn)為書(shū)的信息可以通過(guò)對(duì)小組收藏書(shū)籍的瀏覽所獲得。

為了去除小組對(duì)于想讀書(shū)的影響，我們收集了另一組數(shù)據(jù)，此組數(shù)據(jù)中的書(shū)籍是某個(gè)組員讀過(guò)，小組的收藏中沒(méi)有的書(shū)籍，收集的組員注冊(cè)名為jake，他讀過(guò)的書(shū)但小組沒(méi)有的如表2。

表2 組員有小組沒(méi)有的書(shū)籍被想讀的統(tǒng)計(jì)信息表

在這個(gè)表中，我們可以看到，想讀的人數(shù)非常多的書(shū)籍，在關(guān)注jake人中并不是很多，這里我們理解為，這些被很多人想讀的書(shū)籍屬于熱門(mén)書(shū)籍，人們可以通過(guò)很多渠道得到對(duì)于該書(shū)的評(píng)價(jià)，如《長(zhǎng)尾理論》這樣的熱門(mén)書(shū)籍，學(xué)生在學(xué)校的時(shí)候老師都會(huì)講到這本書(shū)，甚至在當(dāng)當(dāng)，亞馬遜這樣的網(wǎng)上書(shū)店，這些熱門(mén)的書(shū)都會(huì)出現(xiàn)在網(wǎng)站首頁(yè)的醒目位置，所以這里非常多的用戶不是通過(guò)關(guān)注jake來(lái)得到這本書(shū)的信息也是非常正常的。反而我們應(yīng)該關(guān)注的是那種想讀的人不是很多，比如人數(shù)是100以下，而讀過(guò)的人不是很多的那種書(shū)，它是怎樣通過(guò)豆瓣中的關(guān)注關(guān)系擴(kuò)散開(kāi)來(lái)。這才是本文要研究的重點(diǎn)，如何讓一些大眾媒體沒(méi)有觀注到的，而且對(duì)于讀者個(gè)人來(lái)講又是有意義的書(shū)籍，如何進(jìn)行推送。這里我們看到有四本書(shū)是比較符合我們前面的限定：《量子計(jì)算和量子信息(一)——量子計(jì)算部分》、《Quantum Finance》、《In the Beat of a Heart》、《Laws of Form》。選擇這些書(shū)去研究它們的推送過(guò)程還有一個(gè)優(yōu)勢(shì)，在于這四本書(shū)里有三本是外文名，基于關(guān)鍵字的查詢方法，它的優(yōu)勢(shì)在于只要讀者能夠比較準(zhǔn)確的判斷自己所需書(shū)籍的關(guān)鍵字，往往可以通過(guò)關(guān)鍵字來(lái)找到自己所需的書(shū)籍，但如果是外文的書(shū)籍，我們?cè)谂卸ㄋ钑?shū)籍的關(guān)鍵字的時(shí)候就會(huì)存在一些困難，這時(shí)人際推薦的意義就顯得更大。

(二)數(shù)據(jù)分析

在對(duì)數(shù)據(jù)進(jìn)行分析時(shí)，因?yàn)槲覀冄芯康氖钱愘|(zhì)的網(wǎng)絡(luò)，傳統(tǒng)的分析是將網(wǎng)絡(luò)映射為單粒子然后再處理，我們想直接對(duì)異質(zhì)的粒子進(jìn)行處理可以用的方法如Han的條件概率的方法，因?yàn)樵谟?jì)算條件概率時(shí)條件和概率可以是不同的屬性，比如條件是圓的(形狀)，紅色(顏色)，判斷它是蘋(píng)果(水果種類)的概率，在這里我們可以看到異質(zhì)屬性在一個(gè)公式里出現(xiàn)，另一個(gè)我們常用的就是判定樹(shù)，判定樹(shù)是一個(gè)類似于流程圖的樹(shù)結(jié)構(gòu)，其中每個(gè)內(nèi)部結(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試，每個(gè)分枝代表一個(gè)測(cè)試輸出。判定樹(shù)同條件概率一樣可以將不同的屬性放在一起進(jìn)行判斷，但在判定樹(shù)中會(huì)體現(xiàn)流程的概念，我們選用判定樹(shù)的方法來(lái)分析這些數(shù)據(jù)。

圖3 數(shù)學(xué)被傳播的判定樹(shù)

對(duì)另一組將小組的影響去除的數(shù)據(jù)我們也可以得出這樣的判定樹(shù)圖：

圖4 量子被傳播的判定樹(shù)

(三)結(jié)果分析

我們將計(jì)算的結(jié)果列在下表中：

表3 小眾書(shū)籍傳播的可解釋比例表

可解釋人數(shù)的計(jì)算是關(guān)注過(guò)讀過(guò)此書(shū)的人，參加過(guò)此人為小組長(zhǎng)的小組，參加收藏此書(shū)的小組或這個(gè)小組的友情小組，我們認(rèn)為影響流是通過(guò)這些關(guān)系流動(dòng)的。

圖5 搜索小眾書(shū)籍的路徑圖示

圖6 異質(zhì)網(wǎng)絡(luò)間相互影響示意圖

在這張圖上，我們除了看到成員在形成自己的社會(huì)關(guān)系網(wǎng)絡(luò)，從而對(duì)自己今后的讀書(shū)信息過(guò)濾起到作用，而且看到了成員從一個(gè)已知的領(lǐng)域走向自己未知領(lǐng)域的理性過(guò)程，自己讀過(guò)的書(shū)、自己的興趣，成員自己是知道的，由自己知道的找到與自己相似的一群人——讀過(guò)同一本書(shū)的人(這些人并不一定會(huì)形成關(guān)注關(guān)系，它只是為下一步找尋小組信息提供過(guò)濾的標(biāo)準(zhǔn))，然后找到讀過(guò)同一本書(shū)的人參加的小組，然后再在這些小組中找到跟自己興趣相近的人形成關(guān)注關(guān)系，然后通過(guò)這樣的關(guān)注關(guān)系，找到自己沒(méi)有讀過(guò)但與自己有較大關(guān)系的書(shū)。這里需要澄清的一點(diǎn)是，成員為什么不是通過(guò)讀過(guò)同一本書(shū)來(lái)找自己關(guān)注的人，因?yàn)樵诙拱曛忻總€(gè)成員的名字都是自己定義的，有英文，有中文，有數(shù)字編號(hào)，成員發(fā)現(xiàn)與自己讀過(guò)同一本書(shū)的人后得到是這個(gè)人在豆瓣注冊(cè)的用戶名，這個(gè)用戶名基本不包括用戶的興趣，另外，與成員讀過(guò)同一本書(shū)的人是非常多的，在如此重多的選擇中找到與已相似的人所需的精力是比較大的。不去直接選擇讀過(guò)同一本書(shū)的人形成關(guān)注關(guān)系，從小組的角度來(lái)講，小組的組名一般會(huì)以小組關(guān)注的問(wèn)題為名，并且小組的組數(shù)要遠(yuǎn)小于成員的人數(shù)，舉個(gè)例子，《虛實(shí)世界：計(jì)算機(jī)仿真如何改變科學(xué)的疆域》讀過(guò)這本書(shū)的用戶有96個(gè)，但收藏了這本書(shū)的小組只有3個(gè)，分別為集智俱樂(lè)部小組、人工生命小組、復(fù)雜自適應(yīng)系統(tǒng)研究小組，這些小組的名字中會(huì)有一些與書(shū)名契合的點(diǎn)，成員可以通過(guò)自己的經(jīng)驗(yàn)來(lái)選擇這些小組，所以小組在這里起到的作用是幫助進(jìn)行信息過(guò)濾和橋的作用。

四、結(jié)論

通過(guò)對(duì)異質(zhì)的復(fù)雜信息網(wǎng)絡(luò)上的讀者被影響行為的研究，我們發(fā)現(xiàn)，讀者在找尋自己想要讀的書(shū)時(shí)候可以有多種獲得方式，通過(guò)自己構(gòu)建的社會(huì)網(wǎng)絡(luò)是一種形式，這種形式對(duì)于較專業(yè)的書(shū)籍的推薦作用是比較大的。整個(gè)的圖書(shū)信息的獲得是有路徑的，讀者大多是從自己關(guān)注的人或關(guān)注的小組獲得，從關(guān)注的人那里獲得的解釋更多些；而對(duì)于自己關(guān)注的人是怎么得到的，我們從小組角度進(jìn)行了解釋。所有這些都與傳統(tǒng)的度大的結(jié)點(diǎn)(小組，成員，書(shū))會(huì)獲得更多的關(guān)注存在不同，這與Watts的搜索實(shí)驗(yàn)相印證，在他的實(shí)驗(yàn)中沒(méi)有出現(xiàn)“漏斗”現(xiàn)象——大家通過(guò)度大的點(diǎn)來(lái)傳遞信件，我們認(rèn)為這是人們利用信息網(wǎng)絡(luò)中結(jié)點(diǎn)信息的結(jié)果。另一個(gè)，我們發(fā)現(xiàn)，在進(jìn)行推薦的時(shí)候，如果我們將異質(zhì)的網(wǎng)絡(luò)轉(zhuǎn)換成單粒子結(jié)點(diǎn)時(shí)會(huì)損失信息，在我們發(fā)現(xiàn)的找尋路徑上，發(fā)現(xiàn)了小組、關(guān)注的人在不同的階段起到不同的作用，這也與Watts實(shí)驗(yàn)中，前三步人們用地理信息，后續(xù)步驟用職業(yè)信息吻合，由此我們可以看出不進(jìn)行映射操作是必要的。文章中提出的判定樹(shù)的方法是對(duì)以往分析異質(zhì)網(wǎng)絡(luò)的一種嘗試，用了這種方法我們確實(shí)也得到了一些新的結(jié)果。由于篇幅的限制，我們應(yīng)該還可以做的更細(xì)致些，如在確定小組后讀者如何找到自己關(guān)注的人；加入小組后，如何確定自己感興趣的書(shū)；另外，我們還可以考慮將條件概率方法與判定樹(shù)方法相結(jié)合，因?yàn)闂l件概率方法提供的是一種概率，更容易讓人接受。

參考文獻(xiàn)：

[1]Newman M E J.The structure and function of complex networks[J].SIAM Review ，2003(2)：167 -256.

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

[3]Zhou T, Ren J，Medo M，et al.Bipartite network projection and personal recommendation[J].Phys Rev E，2007(4)：1-10.

[4]Yizhou Sun，Jiawei Han.RankClus：integrating clustering with ranking for heterogeneous information network analysis[C].Saint Peterbung, Russia: Extending Database Technology - EDBT, 2009 ：565-576.

[5]汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及應(yīng)用[M].北京: 清華大學(xué)出版社，2006.

[6]Peter Sheridan Dodds，Roby Muhanad，Duncan J Watts.An Experimental Study of Search in Global Social Networks[J].Science，2003(301)：827-829.

[7]Duncan J Watts，P S Dodds，M E J Newman.Identity and search in social networks[J].Science，2002，296：1302～1305.

[8]Yang B，Garcia Molina H.Improving search in peer～to～peer networks[C].Vienna, Austria: Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02)，2002.