異質(zhì)復(fù)雜信息網(wǎng)絡(luò)上的搜索路徑研究*

唐四慧

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

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

一、研究背景

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

二、前人的研究

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

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

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

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

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

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

表1 讀書的簡單統(tǒng)計信息表

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

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

表2 組員有小組沒有的書籍被想讀的統(tǒng)計信息表

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

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

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

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

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

圖4 量子被傳播的判定樹

(三)結(jié)果分析

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

表3 小眾書籍傳播的可解釋比例表

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

圖5 搜索小眾書籍的路徑圖示

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

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

四、結(jié)論

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

參考文獻：

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

[2]劉建國，周濤，汪秉宏.個性化推薦系統(tǒng)的研究進展[J].自然科學(xué)進展，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.