社會化標簽系統(tǒng)的結(jié)構(gòu)、演化和功能

張子柯

(1.杭州師范大學信息經(jīng)濟研究所,杭州 310036；2.杭州師范大學阿里巴巴商學院,杭州 310036；3.電子科技大學互聯(lián)網(wǎng)科學中心,成都 611731)

社會化標簽系統(tǒng)的結(jié)構(gòu)、演化和功能

張子柯1,2,3

(1.杭州師范大學信息經(jīng)濟研究所,杭州 310036；2.杭州師范大學阿里巴巴商學院,杭州 310036；3.電子科技大學互聯(lián)網(wǎng)科學中心,成都 611731)

從復雜性科學角度總結(jié)了社會化標簽系統(tǒng)的結(jié)構(gòu)、演化和功能問題.包括多類異質(zhì)性節(jié)點和超圖模型的網(wǎng)絡結(jié)構(gòu);基于標注行為的網(wǎng)絡演化模型;基于標簽的個性化推薦系統(tǒng).系統(tǒng)地總結(jié)和比較了當前幾種代表性的模型和推薦算法,并指出各方法的優(yōu)缺點和適用范圍.有助于更深層次理解和解決社會化標簽系統(tǒng)中的理論和應用問題.

社會化標簽;推薦系統(tǒng);模型;超圖

社會化標簽系統(tǒng)研究是以“用戶-對象-標簽”(user-object-tag)為基本研究對象,用定量和定性的方法研究其結(jié)構(gòu)關系、演化動力學機制和功能的一個研究方向[1].作為Web2.0的一個核心構(gòu)件[2],社會化標簽自產(chǎn)生后就得到了科學界和工業(yè)界的廣泛關注,被普遍認為是解決信息爆炸時代數(shù)據(jù)組織、管理和挖掘的有效工具[3-4].同時,個性化推薦則被認為是目前解決信息過載問題的有效手段之一[5-6].由于標簽中包含著豐富的用戶個性化信息,因此很多學者都嘗試將標簽功能應用到推薦系統(tǒng)中來進行個性化推薦工作[7-9].其中大多數(shù)研究都是從應用層面出發(fā),以設計推薦算法為主.然而同一推薦算法在不同標簽系統(tǒng)的數(shù)據(jù)上表現(xiàn)迥異,其根本原因在于對不同標簽系統(tǒng)的特性不盡相同,而“社會化標簽系統(tǒng)的統(tǒng)計結(jié)構(gòu)、演化及其功能應用的關聯(lián)關系”這個基本問題尚沒有理論上清晰和系統(tǒng)的認識.

社會化標簽系統(tǒng)的研究工作涉及信息科學、物理學、社會科學、管理科學等多門學科,是一個典型的交叉研究領域.其研究對象——“用戶-對象-標簽”三元關系,是一個復雜動態(tài)系統(tǒng).受互聯(lián)網(wǎng)和社會經(jīng)濟發(fā)展的影響,社會化標簽系統(tǒng)在不同時期不同的統(tǒng)計特性有很大不同.因此,更好地理解標簽系統(tǒng)所特有的多節(jié)點結(jié)構(gòu)和演化機制,將有利于設計具有高精確性和更為個性化的推薦算法.從而系統(tǒng)地認識和理解社會化標簽系統(tǒng)的結(jié)構(gòu)、演化和功能.

社會化標簽系統(tǒng)中的“用戶-對象-標簽”三元關系網(wǎng)絡是典型的復雜動態(tài)網(wǎng)絡.而分析這類網(wǎng)絡的拓撲結(jié)構(gòu)、統(tǒng)計性質(zhì)和演化機制,及其對個性化推薦的影響,正是統(tǒng)計物理和非線性動力學的強項,也是當前復雜性科學研究的前沿方向之一.因此,相關研究不僅可以拓展復雜網(wǎng)絡研究所涵蓋的對象,而且可以從理論層面一定程度上彌補信息科學、社會科學和管理科學等其他科學在研究社會化標簽系統(tǒng)中的理論不足,為交叉科學的研究提供一定的理論支持,并切實有效地解決個性化推薦系統(tǒng)中的重大理論和實踐問題.

1 國內(nèi)外研究現(xiàn)狀分析

隨著社會化標簽系統(tǒng)在互聯(lián)網(wǎng)、電子商務和圖書管理等領域的重要性日益凸顯,深入系統(tǒng)地研究其結(jié)構(gòu)、演化和功能應用的研究已成為目前的研究熱點.以下將從社會化標簽系統(tǒng)的結(jié)構(gòu)和演化模型,以及其在個性化推薦中的功能應用兩個方面介紹相關的研究背景.

1.1 社會化標簽系統(tǒng)的結(jié)構(gòu)和演化模型

復雜網(wǎng)絡理論被普遍認為是認識和分析復雜動態(tài)系統(tǒng)的一個強大而有效的工具[10-12].在一個典型的復雜動態(tài)系統(tǒng)中,復雜網(wǎng)絡用節(jié)點代表個體(如用戶),連邊表示了個體之間的相互作用.復雜網(wǎng)絡理論就是為了理解和解釋這一類復雜動態(tài)系統(tǒng)的結(jié)構(gòu)、演化和功能等問題而提出來的[13-17].一般而言,可以用圖論的相關理論來描述和刻畫復雜網(wǎng)絡,其中最為普遍的就是一部分圖[18]和二部分圖理論[19-20].所謂一部分圖,是指網(wǎng)絡中的所有節(jié)點都是同一類節(jié)點,如圖1所示.典型的一部分圖如社會網(wǎng)絡、WWW網(wǎng)絡和航空網(wǎng)絡等.而二部分圖是指網(wǎng)絡中存在兩類節(jié)點,連邊只存在于一類節(jié)點到另一類節(jié)點之間,同類節(jié)點之間沒有連邊,如圖2所示.如用戶購買商品,用戶給電影打分等,可以統(tǒng)一抽象為“用戶-對象”二部分圖.社會化標簽系統(tǒng)除了用戶-對象二元關系之外,還存在第三類屬性的節(jié)點:標簽.用戶利用標簽管理自己的對象或者尋找自己感興趣的對象.社會化標簽系統(tǒng)是一類典型的復雜動態(tài)系統(tǒng),它包含了用戶、對象和標簽3類不同質(zhì)的信息,構(gòu)成了其獨特的“用戶-對象-標簽”三元結(jié)構(gòu)[1],而傳統(tǒng)的一部分圖和二部分圖理論都無法完整的描述和刻畫這種結(jié)構(gòu).因此很多學者試圖尋找新的理論來刻畫這種三元結(jié)構(gòu),其中最受關注的就是三部分圖[21]和超圖理論[22].三部分圖是對二部分圖的延伸,一般來說,是將用戶、對象、標簽看作成3類不同的節(jié)點,連邊只存在于不同類別的節(jié)點之間,而同類別的節(jié)點之間不存在連邊.而超圖理論則打破了傳統(tǒng)的一條邊有且僅有兩個節(jié)點的約束,允許一條邊連接一個及以上數(shù)目的節(jié)點[22],如圖3所示(見下頁).

圖1 一部分圖Fig.1 Unipartite graph

圖2 二部分圖Fig.2 Bipartite graph

圖3 超圖Fig.3 Hyper graph

由于超圖理論具有一般性,因此在社會科學[23]、生物學[24]和信息科學[25]等領域都有廣泛的應用.而在社會化標簽系統(tǒng)中,如果將用戶的每次標注行為都看做一條邊的話,由于每次標注行為所給的標簽數(shù)目不同,因此這樣的一條邊會包含不同數(shù)目的節(jié)點,這與超圖對邊的定義是一致的.因此,利用超圖來研究標簽系統(tǒng)中的結(jié)構(gòu)和統(tǒng)計特性成為了目前該領域的熱點課題[26].Estrada等[27]探索了基于超圖的子圖中心性和聚類問題.Ghoshal等[28]提出了用隨機超圖模型來表示這種三元結(jié)構(gòu),其核心思想是定義每條邊有且僅有3個節(jié)點:一個用戶節(jié)點、一個對象節(jié)點和一個標簽節(jié)點.在此基礎之上, Zlatic[29]定義和分析了基于這種三角形模型的統(tǒng)計特性,包括超度分布、超度-簇系數(shù)相關性和節(jié)點之間的最短距離,并在兩個數(shù)據(jù)集(Delicious和Flickr)上分別予以展示,都與實際數(shù)據(jù)的統(tǒng)計特性比較吻合.Neubauer等[30]利用超圖理論給出了一種在標簽網(wǎng)絡中尋找最大連通子圖的方法,并半定量地指出這種最大連通子圖的不同構(gòu)成是由惡意用戶的標注行為導致的,并進一步提出了一種檢測惡意用戶行為的方法.Palla等[31]從自相似的角度研究了標簽網(wǎng)絡的統(tǒng)計特性.

另外,很多學者利用復雜網(wǎng)絡動態(tài)建模的思路來研究標簽網(wǎng)絡的演化規(guī)律.Golder等[32]較為系統(tǒng)地研究了標簽系統(tǒng)的結(jié)構(gòu)和用戶使用模式,并且定義了標簽的7種功能.Cattuto等[1]在經(jīng)典的Yu-Simon模型[33]基礎之上,加入了記憶效應,考察了記憶效應對用戶標注行為的影響,從一定程度上揭示了標簽系統(tǒng)的增長規(guī)律.進一步地,Cattuto等[34]利用網(wǎng)絡中的隨機游走思想揭示了標簽系統(tǒng)中蘊含的群集動力學機制[35],該模型能較好的重現(xiàn)標簽系統(tǒng)中標簽規(guī)模分布服從的Zipf定律[36]、標簽增長服從次線性的Heaps定律[37].Halpin等[38]提出了標簽具有“信息價值”這一理念,定義標簽所包含的信息價值是利用它能找到指定資源的概率,并利用用戶標注行為之間的模仿作用設計了標簽系統(tǒng)的演化模型,該模型能較好地解釋標簽系統(tǒng)中的“共現(xiàn)”現(xiàn)象和標簽規(guī)模分布服從Zipf定律,但不能解釋標簽增長服從次線性的Heaps定律.在此基礎之上, Dellschaft等[39]除了考慮用戶模仿標注行為外,還考慮了用戶自身的背景知識對標簽系統(tǒng)演化的影響.該模型能較好地彌補文獻[38]不能解釋標簽增長服從次線性的Heaps定律這一缺陷.

國內(nèi)在社會化標簽系統(tǒng)的結(jié)構(gòu)和建模方面的研究起步較晚,但進展較快,近年來取得了豐碩的成果.王志平、王眾托[40]和何大韌等[41-43]分別從系統(tǒng)工程科學和復雜網(wǎng)絡的角度提出利用“超網(wǎng)絡”和交聯(lián)網(wǎng)理論來刻畫和解決復雜動態(tài)系統(tǒng)中的結(jié)構(gòu)和應用問題,為復雜系統(tǒng)的建模提供了新思路[44].王建偉等[45]采用了超邊增長和超邊優(yōu)先連接兩種增長機制建立了基于超網(wǎng)絡的增長模型,并解析給出了標簽系統(tǒng)中的超度分布,同時給出了該模型的簇系數(shù)和平均最短距離的數(shù)值分析結(jié)果.張子柯等[46]從語義動力學的角度出發(fā),建立了基于用戶背景知識和對象、標簽雙重優(yōu)先連接機制的超圖增長模型,該模型不僅可以得到標簽系統(tǒng)中的超度分布的解析解,還能得到標簽系統(tǒng)中的超度-簇系數(shù)分布的理論解,同時該模型能較好地重現(xiàn)實際數(shù)據(jù)的統(tǒng)計特性.劉闖等[47]提出了用戶標注行為存在趨同性,從而最終導致了標簽系統(tǒng)中用戶標注行為自組織現(xiàn)象的涌現(xiàn).裴偉東等[48]研究了基于一類三角形結(jié)構(gòu)的動態(tài)網(wǎng)絡結(jié)構(gòu)的演化模型,利用平均場方法得到了這一類網(wǎng)絡結(jié)構(gòu)的理論解,證明了該類演化模型具有和很多真實網(wǎng)絡相似的無標度性[10]和小世界現(xiàn)象[9].此外,國內(nèi)學者還利用復雜網(wǎng)絡理論對標簽系統(tǒng)的統(tǒng)計特性進行了廣泛而深入的研究[49-52].進一步地,劉丹[53]總結(jié)了近年來社會化標簽系統(tǒng)的發(fā)展和改進方面的研究進展.楊青云等[54]總結(jié)了當前國際上對用戶標注行為研究的現(xiàn)狀和最新進展.當然,國內(nèi)的研究成果遠不止于此,由于篇幅限制這里就不做過多介紹.

1.2 基于社會化標簽的個性化推薦系統(tǒng)

互聯(lián)網(wǎng)和Web2.0技術的迅速發(fā)展將我們帶入了信息爆炸的時代.海量數(shù)據(jù)信息的涌現(xiàn),在給人們帶來更多選擇的同時,也導致人們很難快速有效地定位自己所需要的信息.個性化推薦則被認為是解決這一問題的有效工具之一[5-6],也被認為是復雜網(wǎng)絡理論的發(fā)展方向之一[55].由于標簽包含了豐富的個性化信息,因此將社會化標簽應用到個性化推薦中也是當前推薦系統(tǒng)領域的一個重要研究課題[7-8],屬于社會計算[56]的范疇.Hotho等[57]使用改進后的PageRank[58]算法進行推薦標簽的研究,為使用標簽進行推薦提供了切實有效的思路.到目前為止,利用標簽進行個性化推薦主要有以下幾個方向:

a.基于三部分圖的推薦算法

最近,很多學者從網(wǎng)絡角度,利用物質(zhì)擴散和熱傳導等物理學方法在“用戶-對象”二部分圖上來進行個性化推薦研究[19,59-64].同時將標簽作為單獨一類節(jié)點,在“用戶-對象-標簽”三部分圖上利用物理方法進行推薦,也已成為該領域的熱點課題.張子柯等[65]將物質(zhì)擴散方法分別應用到“用戶-對象”和“對象-標簽”兩個二部分圖中,得到對象分別基于用戶和標簽的得分值,最后通過兩個得分混合得到對象的最終得分.該算法在最優(yōu)參數(shù)下會得到比二部分圖更高的推薦準確性、多樣性和新穎性.尚明生等[66]將該方法應用到以用戶為中心的“對象-用戶-標簽”的三部分圖上,進一步提高了推薦效果.張子柯等[67]提出標簽擁有兩種功能:管理和檢索功能,并將其應用到推薦系統(tǒng)中,得到了更高的推薦精確性和多樣性.進一步的統(tǒng)計分析表明,該算法尤其對相對冷門的對象有效,從而在一定程度上解決了困擾個性化推薦的“冷啟動”難題.Liang等[68]指出簡單的混合方式會導致信息的丟失,并提出了利用標簽所蘊含的語義信息來衡量用戶對標簽和對象的喜好程度,在此基礎上利用混合算法得到更好的推薦效果.

基于三部分圖算法存在的不足是將用戶、對象、標簽看作成3類不同的節(jié)點,連邊只存在于不同類別的節(jié)點之間,同類別的節(jié)點之間不存在連邊.這種人為的劃分方式,割裂了3類節(jié)點相互之間的“共現(xiàn)”關系,從而不可避免地會造成信息丟失.為了更為完善地解決這個問題,需要從分析社會化標簽系統(tǒng)的結(jié)構(gòu)入手,從理論上建立較為完整的理論模型.只有建立合理的理論模型,這個問題才能更好地得到解決.

b.基于概率模型的推薦算法

基于概率模型的方法最早出現(xiàn)在信息檢索領域中,如潛層語義分析(latent semantic analysis, LSA)[69],基于概率的潛層語義分析(probabilistic latent semantic analysis,PLSA)[70]和潛層狄利克萊分配(latent dirichlet allocation,LDA)[71].近年來,很多學者將基于概率模型的方法應用到個性化推薦中去,期望獲得更好的推薦效果.Said等[72-73]提出了基于PLSA的混合推薦算法.該算法利用潛層主題變量來衡量“用戶-對象”和“對象-標簽”的共現(xiàn)概率,再將兩者混合起來進行推薦.Krestel等[74-75]利用LDA模型從對象的標簽庫里抽取出潛層主題,然后在這些主題之上向用戶推薦個性化標簽.Bundschus等[76-77]則使用LDA模型混合利用用戶信息和標簽信息,并提出用“主題-標簽”模型和“用戶-主題-標簽”模型來獲得潛層主題,然后再使用兩步迭代來進行個性化標簽推薦.Li等[78]則將LDA模型和GN社團發(fā)現(xiàn)算法[79]結(jié)合在一起,發(fā)現(xiàn)同一個社區(qū)的用戶傾向于喜好類似的主題,該算法為設計基于社團的推薦算法提供了新思路.Li等[80]進一步將概率模型和網(wǎng)絡結(jié)構(gòu)模型結(jié)合起來,獲得了更好的推薦效果.

基于概率模型算法存在的不足是以機器學習為基礎.這種方法一般采用Gibbs抽樣[81]或者期望最大化方法[82]來迭代獲得最優(yōu)的推薦結(jié)果,因此對計算機的計算能力要求較高.特別是當數(shù)據(jù)量規(guī)模非常大的時候,使用基于概率模型的算法將會消耗較長的計算時間.目前,如何快速有效地設計基于概率模型的推薦算法還是一個難題.

c.基于協(xié)同過濾的推薦算法

基于協(xié)同過濾的推薦算法是目前為止應用最為廣泛的個性化推薦算法[83-84].其原理是根據(jù)具有相似興趣的用戶以往的購買記錄來預測目標用戶未來可能喜好的物品[6].類似地,用戶對相似標簽的喜好程度也一定程度上反映了用戶之間相似度.Tsosutter等[85]分別計算了基于標簽的用戶相似度和對象相似度,分別歸一化后使用混合方法進行個性化推薦.Liang等[86]指出由于標注行為的自由性所導致的噪音問題會影響到推薦性能,因此提出使用“流行”標簽來衡量用戶相似性,再在協(xié)同過濾框架下進行推薦,實驗結(jié)果表明取得了比文獻[68]和[85]更高的精確性.與以往單純的推薦一類節(jié)點不同的是,Peng等[87]提出了利用協(xié)同過濾算法推薦“對象-標簽”對的想法,為個性化推薦拓展了思路. Kim等[88]使用標簽來過濾用戶偏好,該算法對較為稀疏的數(shù)據(jù)集和“冷啟動”用戶有一定效果.Durao 等[89]利用標簽之間的語義關聯(lián)來衡量對象之間的相似度,并在協(xié)同過濾框架下進行個性化推薦.陳超等[90]則將協(xié)同過濾和三部分圖結(jié)合起來,提出了一種基于含權(quán)三部圖的協(xié)同過濾算法.該算法除了能提高推薦效果外,還在一定程度上解決了用戶“冷啟動”問題.最近國內(nèi)學者對應用社會化標簽進行個性化推薦的研究進展做了詳細的綜述[7,91].

基于協(xié)同過濾的推薦算法存在的不足是以用戶過去的行為來計算相似度的,因此需要大量的歷史數(shù)據(jù)才能較好地衡量相似性.同時,在海量數(shù)據(jù)的情況下計算相似度也是非常消耗時間的.此外,很多在線用戶的行為并不十分顯著(比如購買過程中的瀏覽和比較行為),如何衡量基于這一類用戶行為的相似度還是一個研究難題.

2 總結(jié)與討論

從復雜性科學角度總結(jié)了社會化標簽系統(tǒng)的結(jié)構(gòu)、演化和功能問題研究進展.包括基于三節(jié)點結(jié)構(gòu)和超圖結(jié)構(gòu)的網(wǎng)絡模型、基于個體和群體效應的網(wǎng)絡演化建模機制、以及基于社會化標簽的個性化推薦系統(tǒng).作為一類典型的復雜系統(tǒng),除了一般復雜系統(tǒng)的共性以外,社會化標簽系統(tǒng)的特性及其引發(fā)的一系列科學問題也引起越來越多的科學界的廣泛關注.

目前,社會化標簽系統(tǒng)的結(jié)構(gòu)、演化和功能問題的研究已經(jīng)取得了一些進展.然而,也可以看到,當前的研究仍然存在諸多問題:a.盡管社會化標簽已經(jīng)在Web 2.0網(wǎng)站中得到了廣泛應用,然而對社會化標簽系統(tǒng)的結(jié)構(gòu)和演化機制缺乏足夠清晰的認識.社會化標簽系統(tǒng)中的3類節(jié)點不是各自孤立的,而是彼此之間有著很緊密的關聯(lián)關系.因此無法直接用經(jīng)典的復雜網(wǎng)絡理論進行建模分析.需要綜合分析用戶、對象和標簽這3類節(jié)點的微觀聯(lián)系,進而更為深刻地理解社會化標簽系統(tǒng)的宏觀結(jié)構(gòu)和統(tǒng)計特性.而基于超圖模型的結(jié)構(gòu)[22,29,46]將有望處理類似這種異質(zhì)性節(jié)點系統(tǒng)的一種有效理論工具.b.對用戶標注行為習慣缺乏足夠的了解.目前對社會化標簽系統(tǒng)建模的研究都是假設用戶每次只標注一個標簽.然而,在實際的社會化標簽系統(tǒng)中,每次用戶標注行為往往包含了多個標簽.因此,需要從大量實際數(shù)據(jù)中分析用戶的同一個標注行為中多個標簽的關系,在此基礎上,進行用戶標注行為的模擬和建模.目前涉及這方面的內(nèi)容的研究工作還較少.c.無法定量分析社會化標簽系統(tǒng)的結(jié)構(gòu)和演化規(guī)律對推薦算法的影響.現(xiàn)有的基于標簽的個性化推薦算法都沒有考慮標簽系統(tǒng)的結(jié)構(gòu)特性,以及不同系統(tǒng)的用戶標注行為習慣.因此,正確利用標注行為設計準確性和多樣性都較高的推薦算法,將有望成為解決困擾推薦系統(tǒng)已久的“稀疏性”、“冷啟動”等問題的一種有效途徑.

[1] CATTUOC,LORETO V,PIETRONERO L.Semiotic dynamics and collaborative tagging[J].Proceedings of the National Academy of Sciences,2007,104(5): 1461-1464.

[2] 翟爽,宋文.社會標簽進展研究概述[J].圖書情報工作,2010,54(20):41-44.

[3] TRANT J.Studying social tagging and folksonomy:a review and framework[J].Journal of Digital Information,2009,10(1):1-42.

[4] DING Y,JACOB E,ZHANG Z,et al.Perspectives on social tagging[J].Journal of the American Society for Information Science and Technology,2009,60(12): 2388-2401.

[5] ADOMAVICIUSG,TUZHILIN A.Toward the next generation of recommender systems:A survey of the state-of-the-art and possible extensions[J].IEEE Transactions on Knowledge and Data Engineering, 2005,17(6):734-749.

[6] 劉建國,周濤,汪秉宏.個性化推薦系統(tǒng)的研究進展[J].自然科學進展,2009,19(1):1-15.

[7] 魏建良,朱慶華.基于社會化標注的個性化推薦研究進展[J].情報學報,2010,29(4):625-633.

[8] ZHANGZ K,ZHOU T,ZHANGYC.Tag-aware recommender systems:A state-of-the-art survey[J].Journal of Computer Science and Technology,2011,26(5): 767-777.

[9] MILICEVIC A K,NANOPOULOS A,IVANOVIC M.Social tagging in recommender systems:A survey of the state-of-the-art and possible extensions[J].Artificial Intelligence Review,2010,33(3):189-204.

[10] WATTS D J,STROGATZ S H.Collective dynamics of “small-world”networks[J].Nature,1998,393(6684): 440-442.

[11] BARABáSI A L,ALBERT R.Emergence of scaling in random networks[J].Science,1999,286(5439): 509-512.

[12] 汪小帆,李翔,陳關榮.復雜網(wǎng)絡理論及其應用[M].北京:清華大學出版社,2006.

[13] ALBERT R,BARABáSI A L,Statistical mechanics of complex networks[J].Review of Model Physics,2002, 74(1):47-97.

[14] DOROGOVTSEV S N,MENDES J F F,Evolution of networks[J].Advances in Physics,2002,51(4): 1079-1187.

[15] NEWMAN M E J,The structure and function of complex networks[J].SIAM Review,2003,45(2): 167-256.

[16] BOCCALETTI S,LATORA V,MORENO Y,et al.Complex networks:Structure and dynamics[J].Physics Reports,2006,424(4-5):175-308.

[17] COSTA L F,RODRIGUES F A,TRAVIESO G,et al. Characterization of complex networks:A survey of measurements[J].Advances in Physics,2007,56(1): 167-242.

[18] NEWMAN M E J,WATTSD J,STROGATZ S H.Random graph models of social networks[J].Proceedings of the National Academy of Sciences,2002,99(3): 2566-2572.

[19] ZHOU T,REN J,MEDO M,et al.Bipartite network projection and personal recommendation[J].Physical Review E,2007,76(4):046115.

[20] SHANG M S,LüL,ZENG W,et al.Empirical analysis of web-based user-object bipartite networks[J].Europhysics Letters,2009,90(4):48006.

[21] LAMBIOTTE R,AUSLOOS M.Collaborative tagging as a tripartite network[J].Lecture Notes in Computer Science,2006(3993):1114-1117.

[22] VITALY I V.Introduction to Graph and Hypergraph Theory[M].Hauppauge:Nova Science Publishers, 2009.

[23] VAZQUEZ A.Population stratification using a statistical model on hypergraphs[J].Physical Review E, 2008,77(6):066106.

[24] KLAMT S,HAUSU U,THEISF.Hypergraphs and cellular networks[J].PLoSComputational Biology,2009, 5(5):e1000385.

[25] ZHOU D,HUANG J,SCHOLKOPF B.Learning with hypergraphs:clustering,classification,and embedding [J].Advances in Neural Information Processing Systems,2007,19:1601-1608.

[26] CATTUTOC,SCHMITZ C,BALDASSARRI A,et al. Network properties of folksonomies[J].AI Communications,2007,20(4):245-262.

[27] ESTRADA E,RODRIGUEZ-VELáZQUEZ J A.Subgraph centrality and clustering in complex hyper-networks[J].Physica A,2006,364:581-594.

[28] GHOSHAL G,ZLATIC′V,CALDARELLI G,et al.Random hypergraphs and their applications[J].Physical Review E,2009,79(6):066118.

[29] ZLATIC′V,GHOSHAL G,CALDARELLIG.Hypergraph topological quantities for tagged social networks[J]. Physical Review E,2009,80(3):036118.

[30] NEUBAUER N,OBERMAYER K.Hyperincident connected components of tagging networks[C]∥Proceeding of the 20th ACM Conference on Hypertext and Hypermedia.New York:ACM press,2009:229-238.

[31] PALLA G,FARKAS I J,POLLNERP,et al.Fundamental statistical features and self-similar properties of tagged networks[J].New Journal of Physics,2008,10 (12):123026.

[32] GOLDERS A,HUBERMAN B A,Usage patterns of collaborative tagging systems[J].Journal of Information Science,2006,32(2):198-208.

[33] YULE G U.A mathematical theory of evolution,based on the conclusions of Dr.JCWillis,FRS[J].Philosophical Transactions of the Royal Society of London.Series B,Containing Papers of a Biological Character, 1925,213:21-87.

[34] CATTUTOC,BARRAT A,BALDASSARRI A,et al. Collective dynamics of social annotation[J].Proceedings of the National Academy of Sciences,2009,106 (26):10511-10515.

[35] CASTELLANO C,FORTUNATOS,LORETO V.Statistical physics of social dynamics[J].Review of Model Physics,2009,81(2):591-646.

[36] ZIPF G K.Human Behaviour and the Principle of Least Effort:An Introduction to Human Ecology[M]. Cambridge:Addison-Wesley Press,1949.

[37] HEAPSH S.Information Retrieval:Computational and Theoretical1 Aspects[M].New York:Academic Press,1978.

[38] HALPIN H,ROBU V,SHEPHERD H,The complex dynamics of collaborative tagging[C]∥Proceeding of the 16th International WWW Conference.New York:ACM Press,2009:211-220.

[39] DELLSCHAFT K,STAAB S.An epistemic dynamic model for tagging systems[C]∥Proceeding of the 9th ACM Conference on Hypertext Hypermedia.New York:ACM press,2008:71-80.

[40] 王志平,王眾托.超網(wǎng)絡理論及其應用[M].北京:科學出版社,2008.

[41] 張培培,侯威,何閱,等.淮揚菜系的網(wǎng)絡描述[J].復雜系統(tǒng)與復雜性科學,2005,2(2):49-53.

[42] 張培培,何閱,周濤,等.一個描述合作網(wǎng)絡頂點度分布的模型[J].物理學報,2006,55(1):59-66.

[43] 何閱,張培培,許田,等.一個科研合作網(wǎng)的雙粒子圖自適應演化模型[J].物理學報,2004,53(6): 1710-1715.

[44] 席運江,黨延忠.基于加權(quán)超網(wǎng)絡模型的知識網(wǎng)絡魯棒性分析方法[J].系統(tǒng)工程理論與實踐,2007,27(4):134-140.

[45] WANG J W,RONG L L,DENG Q H.Evolving hypernetwork model[J].European Journal of Physics B, 2010,77(4):493-498.

[46] ZHANGZ K,LIU C.A hypergraph model of social tagging networks[J].Journal of Statistical Mechanics, 2010,(10):P10005.

[47] LIU C,YEUNG C H,ZHANG Z K.Self-Organization in Social Tagging Systems[J].Physical Review E,2011, 83(6):066104.

[48] 裴偉東,夏瑋,王全來,等.一類三角形結(jié)構(gòu)動態(tài)復雜網(wǎng)絡演化模型分析[J].中國科學技術大學學報, 2010,40(11):1186-1190.

[49] 魯曉明.Web 2.0中社會性標簽系統(tǒng)的復雜網(wǎng)絡特性研究[J].現(xiàn)代情報,2007,27(12):64-66.

[50] 李靜.Folksonomy的網(wǎng)絡性質(zhì)分析[J].現(xiàn)代情報, 2009,29(7):61-63.

[51] 吳超,周波.基于復雜網(wǎng)絡的社會化標簽分析[J].浙江大學學報(工學版),2010,44(11):2194-2197.

[52] 劉知遠,司憲策,鄭亞斌,等.中文博客標簽的若干統(tǒng)計性質(zhì)[C]∥中國計算技術與語言問題研究——第七屆中文信息處理國際會議論文集.北京:電子工業(yè)出版社,2007:533-539.

[53] 劉丹.近年來國外Folksonomy的改進研究進展[J].圖書情報工作,2010,54(8):55-59.

[54] 楊青云,裴雷,吳克文.國外社會化標注系統(tǒng)中標注行為研究現(xiàn)狀[J].資源管理,2009,28(11):185-188.

[55] NEWMAN M E J.Complex systems:A survey[J]. 2011,to be published.

[56] 王飛躍.社會計算:科學技術人文[J].中國科學院院, 2005,20(5):370-376.

[57] HOTHOA,JASCHKE R J,SCHMITZC,et al.Information retrieval in folksonomies:Search and ranking[J]. Lecture Notes in Computer Science,2006,4011:411-426.

[58] BRIN S,PAGE L.The anatomy of a large-scale hypertextual Web search engine[J].Computer Networks ISDN System,1998,30(1):107-117.

[59] ZHANG YC,BLATTNER M,YU Y K.Heat conduction process on community networks as a recommendation model[J].Physical Review Letters,2007,99 (15):154301.

[60] ZHOU T,KUSCSIK Z,LIU J G,et al.Solving the apparent diversity-accuracy dilemma of recommender systems[J].Proceedings of the National Academy of Sciences,2010,107(10):4511-451.

[61] ZHOU T,SU R Q,LIU RR,et al.Accurate and diverse recommendations via eliminating redundant correlations[J].New Journal of Physics,2009,11 (12):123008.

[62] SUN D,ZHOU T,LIU J G,et al.Information filtering based on transferring similarity[J].Physical Review E,2009,80(1):17101.

[63] ZHOU T,JIANG L L,SU R Q,et al.Effect of initial configuration on network-based recommendation[J]. Europhysics Letters,2008,81(5):58004.

[64] LIU JG,ZHOU T,CHE H A,et al.Effects of high-order correlations on personalized recommendations for bipartite networks[J].Physica A,2010,389(4): 881-886.

[65] ZHANGZ K,ZHOU T,ZHANG Y C.Personalized recommendation via integrated diffusion on user-item-tag tripartite graphs[J].Physica A,2010,389(1): 179-186.

[66] SHANG M S,ZHANG Z K,ZHOU T,et al.Collaborative filtering with diffusion-based similarity on tripartite graphs[J].Physica A,2010,389(6):1259-1264.

[67] ZHANGZ K,LIU C,ZHANG Y C,et al.Solving the cold-start problem in recommender systems with social tags[J].Europhysics Letters,2010,92(2):28002.

[68] LIANG H,XU Y,LI Y,et al.Connecting users and items with weighted tags for personalized Item recommendations[C]∥Proceeding of the 21st ACM Conference on Hypertext and Hypermedia.New York:ACM press,2010:51-60.

[69] DEERWESTER S,DUMAISS T,FURNASG W,et al. Indexing by latent semantic analysis[J].Journal of the American Society for Information Science and Technology,1990,41(6):391-407.

[70] HOFMANN T.Probabilistic latent semantic indexing [C]∥Proceeding of the 22nd Ann.Intl.ACM SIGIR Conference on Research and Development Information Retrieval.New York:ACM press,1999:50-57.

[71] BLEI D M,NG A Y,JORDAN M I.Latent dirichlet allocation[J].Journal of Machine Learning Research, 2003,3(3):993-1022.

[72] SAID A,WETZKER R,UMBRATH W,et al.A hybrid PLSA approach for warmer cold start in folksonomy recommendation[C]∥Proceeding of ACM Recsys 2009 Workshop on Recommender Systems&the Social Web.New York:ACM Press,2009:87-90.

[73] WETZKER R,UMBRATH W,SAID A.A hybrid approach to item recommendation in folksonomies[C]∥Proceedings of the Workshop Exploiting Semantic Annotation Information Retrieval.2009:25-29.

[74] KRESTEL R,FANKHAUSER P.Tag recommendationusing probabilistic topic models[C]∥Proceeding of ECML PKDD Discovery Challenge.2009:131-141.

[75] KRESTEL R,FANKHAUSER P,NEJDL W.Latent dirichlet allocation for tag recommendation[C]∥Proceedings of the 3rd ACM Conference on Recommender Systems.New York:ACM press,2009:61-68.

[76] BUNDSCHUS M,YU S,TRESP V,et al.Hierarchical bayesian models for collaborative tagging systems[C] ∥The 9th IEEE International Conference on Data Mining.Los Alamitos:IEEE Computer Society Press, 2009:728-733.

[77] BUNDSCHUS M,TRESP V,KRIEGEL H P.Topic models for semantically annotated document collections[R].Whistler:NIPS workshop,2009.

[78] LI D,HE B,DING Y,et al.Community-based Topic Modeling for Social Tagging[C]∥Proceeding of the 9th ACM International Conference on Information Knowledge Management.New York:ACM press,2010: 54-63.

[79] GIRVAN M,NEWMAN M EJ.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12): 7821-7826.

[80] LI H Q,XIA F,ZENG D,et al.Exploring Social Annotations with the Application to Web Page Recommendation[J].Journal of Computer Science Technology, 2009,24(6):1028-1034.

[81] GELFAND A E,SMITH A F M.Sampling-based approaches to calculating marginal densities[J].Journal of the American Statistical Association,1990,85 (410):398-409.

[82] DEMPSTER A P,LAIRD N M,RUBIN D B.Maximum likelihood from incomplete data via the EM algorithm [J].Journal of the Royal Statistical Society:Series B, 1977,39(1):1-38.

[83] KONSTAN J A,MILLER B N,MALTZ D,et al.GroupLens:applying collaborative filtering to use net news [J].Communications of ACM,1997,40(3):77-87.

[84] LINDEN G,SMITH B,YORK J.Amazon.com recommendations:Item-to-item collaborative filtering[J]. IEEE Internet Computing,2003,7(1):76-80.

[85] TSO-SUTTER K H L,MARINHO L B,SCHMIDTTHIEME L.Tag-aware recommender systems by fusion of collaborative filtering algorithms[C]∥Proceedings of the 2008 ACM Symposium on Applied Computing.New York:ACM press,2008:1995-1999.

[86] LIANG H,XU Y,LI Y.Collaborative filtering recommender systems based on popular tags[C]∥Proceedings of the 4th Australasian Document Computing Symposium.2009:3-10.

[87] PENG J,ZENG D D,ZHAO H,et al.Collaborative filtering in social tagging systems based on joint item-tag recommendations[C]∥Proceedings of the 19th ACM International Conference on Information Knowledge Management.New York:ACM press,2010:809-818.

[88] KIM H N,JI A T,HA I,et al.Collaborative filtering based on collaborative tagging for enhancing the quality of recommendation[J].Electronic Commerce Research and Applications,2010,9(1):73-83.

[89] DURAO F,DOLOG P.Extending a hybrid tag-based recommender system with personalization[C]∥Proceedings of the 2010 ACM Symposium on Applied Computing.New York:ACM press,2010:1723-1727.

[90] 陳超,張穎超,繆進.一種基于三部圖網(wǎng)絡的協(xié)同過濾算法[J].南京信息工程大學學報(自然科學版), 2010,2(4):337-339.

[91] 吳思竹.社會標注系統(tǒng)中標簽推薦方法研究進展[J].圖書館雜志,2010(3):48-52.

Social tagging systems:structure,dynamics and function

ZHANGZi-ke1,2,3
(1.Imsititute of Imformatiom Ecomomy,Hamgzhou Normal Umiversity,Hamgzhou 310036,Chima；2.Alibaba Busimess College,Hamgzhou Normal Umiversity,Hamgzhou 310036,Chima；3.Web Sciemces Cemter,Umiversity of Electromic Sciemce amd Techmology of Chima,Chemgdu 611731,Chima)

The recent research progress on understanding the structure,dynamics and function of social tagging systems was summarized.In particular,the following was emphasized:network structures of heterogeneous nodes and hypergraph；tagging behavior based evolving models；tag-aware recommender systems.The representive models and algorithms were systematically studied and compared,and advantages and disadvantages of each,as well as their applicable areas,were pointed out respectively.This survey could shed some lights on deep understanding on both theoretical and application problems of social tagging systems.

social tag；recommemder system；model；hypergraph

F 293.3文獻標示碼：A

1007-6735(2011)05-0444-08

2011-10-03

國家自然科學基金資助項目(11105025,61103109,60973069)；四川省科技廳國際合作項目(2010HH0002)

張子柯(1982-),男,教授.研究方向:復雜網(wǎng)絡、社會標簽、推薦系統(tǒng)等.E-mail:zhangzike@gmail.com