在線社交網(wǎng)絡(luò)中的新興話題檢測技術(shù)綜述

笱程成,杜 攀, 劉 悅, 程學(xué)旗

(1. 中國科學(xué)院 計(jì)算技術(shù)研究所, 中國科學(xué)院網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京100190; 2. 中國科學(xué)院大學(xué), 北京 100190)

在線社交網(wǎng)絡(luò)中的新興話題檢測技術(shù)綜述

笱程成1,2,杜 攀1, 劉 悅1, 程學(xué)旗1

(1. 中國科學(xué)院 計(jì)算技術(shù)研究所, 中國科學(xué)院網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京100190; 2. 中國科學(xué)院大學(xué), 北京 100190)

新興話題檢測是社交網(wǎng)絡(luò)研究的熱點(diǎn)問題之一。在線社交網(wǎng)絡(luò)特別是微博的開放性，給話題的流行和爆發(fā)提供了前所未有的便利條件。新興話題是即將流行或爆發(fā)的話題，往往伴隨著重大的事件或新聞的發(fā)生，會(huì)產(chǎn)生重大的社會(huì)影響，如何在早期識(shí)別此類話題，是新興話題檢測研究的主要內(nèi)容。該文回顧了近年來在新興話題檢測方面的主要進(jìn)展，分析了新興話題檢測領(lǐng)域面臨的挑戰(zhàn)，闡述了相關(guān)的概念、方法和理論，重點(diǎn)從內(nèi)容突發(fā)特征和信息傳播模型兩個(gè)方面對影響新興話題檢測的方法進(jìn)行了分析和討論，并對新興話題檢測的前景做了展望。

新興話題；話題檢測；信息傳播；社交網(wǎng)絡(luò)

1 引言

近年來，以Twitter、Facebook、微博和微信為代表的在線社交網(wǎng)絡(luò)的迅速發(fā)展極大地影響了人們的社交和工作方式。在社交網(wǎng)絡(luò)中，個(gè)人可以隨時(shí)隨地和朋友進(jìn)行互動(dòng)，分享自身的相關(guān)信息，關(guān)注感興趣的用戶，訂閱信息，查看各式各樣的新聞，各種組織和官方機(jī)構(gòu)也可以利用社交網(wǎng)絡(luò)發(fā)布新產(chǎn)品和新聞。

由于社交網(wǎng)絡(luò)的開放性和共享性，人們在其中共享的信息或談?wù)摰脑掝}可能會(huì)在網(wǎng)絡(luò)中廣泛傳播，造成巨大的社會(huì)影響。對個(gè)人和公司來講，新興話題檢測是公司進(jìn)行在線信譽(yù)監(jiān)控(online reputation monitoring)的重要手段，如果公司可以在早期檢測到社交網(wǎng)絡(luò)中產(chǎn)生的與自身有關(guān)的事件和觀點(diǎn)，就可以較早地發(fā)現(xiàn)與公司有關(guān)的話題，及時(shí)采取相應(yīng)措施，若為負(fù)面話題則及時(shí)公關(guān)，降低公司信譽(yù)損失，若為正面話題則可借機(jī)營銷，提升公司業(yè)績。對于政府部門來講，盡早地發(fā)現(xiàn)社交網(wǎng)絡(luò)中的虛假信息、欺詐信息、誹謗謠言等不良甚至反動(dòng)信息，可以采取有針對性的措施凈化網(wǎng)絡(luò)環(huán)境，打擊犯罪，及時(shí)處置緊急事態(tài)，避免惡性群體性事件的發(fā)生；同時(shí)，對于弘揚(yáng)正能量，宣揚(yáng)社會(huì)主義道德的消息則可以因勢利導(dǎo)，擴(kuò)大在社會(huì)中造成的影響，有助于在整個(gè)社會(huì)中樹立正確的價(jià)值導(dǎo)向。因此，社交網(wǎng)絡(luò)時(shí)代，在網(wǎng)絡(luò)話題產(chǎn)生的早期及時(shí)地發(fā)現(xiàn)它們，即新興話題發(fā)現(xiàn)技術(shù)，具有十分重要的研究和實(shí)踐價(jià)值。

新興話題(emerging topic)就是在話題流行或爆發(fā)之前話題的早期存在狀態(tài)，也常常被稱為趨勢話題(trending topic)或突發(fā)話題(burst topic)。新興話題檢測和話題檢測與跟蹤[1-2](topic detection and tracking，TDT)中的首篇報(bào)道檢測[3](first story detection，F(xiàn)SD)比較相似，但是存在兩個(gè)顯著差別： (1)從分析目標(biāo)看，F(xiàn)SD的目標(biāo)主要是判斷某篇新聞是否是某個(gè)話題的首篇報(bào)道，并不關(guān)注該話題是否會(huì)爆發(fā)，會(huì)不會(huì)引起廣泛關(guān)注，而新興話題檢測任務(wù)的主要目標(biāo)除了需要識(shí)別消息是否是新的，還要預(yù)測該消息可能造成的影響； (2)從處理對象看，F(xiàn)SD最初是針對靜態(tài)的新聞報(bào)道提出的話題檢測任務(wù)，而新興話題檢測主要關(guān)注社交網(wǎng)絡(luò)上的用戶產(chǎn)生內(nèi)容及其傳播網(wǎng)絡(luò)要素。

不同的社交網(wǎng)絡(luò)，其信息傳播的特性是不同的。以微信和Facebook為代表的社交網(wǎng)絡(luò)是基于雙向朋友關(guān)系構(gòu)建的網(wǎng)絡(luò)，個(gè)人發(fā)布的信息只在朋友之間進(jìn)行共享。而以微博和Twitter為代表的社交網(wǎng)絡(luò)是以用戶興趣為紐帶構(gòu)建的網(wǎng)絡(luò)，微博中的用戶可以關(guān)注任何感興趣的用戶，幾乎不受限制地發(fā)布或轉(zhuǎn)發(fā)任何感興趣的信息。由于微博網(wǎng)絡(luò)開放的社交網(wǎng)絡(luò)結(jié)構(gòu)，微博上的消息具有傳播速度快，輻射范圍廣、實(shí)時(shí)性高的顯著特點(diǎn)，微博中的信息常常在短時(shí)間內(nèi)大規(guī)模的傳播，產(chǎn)生巨大的社會(huì)影響。因此，以微博平臺(tái)為主要研究場景，在微博中的事件或話題大規(guī)模爆發(fā)之前或爆發(fā)早期對其進(jìn)行檢測是一個(gè)具有重要理論價(jià)值和現(xiàn)實(shí)意義的問題，近年來引起了信息檢索、數(shù)據(jù)挖掘、復(fù)雜網(wǎng)絡(luò)等領(lǐng)域?qū)W者的普遍關(guān)注，產(chǎn)生了許多一系列特色鮮明的研究成果。本文主要針對社交網(wǎng)絡(luò)中的微博平臺(tái)上的新興話題檢測技術(shù)展開調(diào)研。

與傳統(tǒng)的話題檢測任務(wù)相比，在線社交網(wǎng)絡(luò)上的新興話題檢測技術(shù)主要面臨以下三個(gè)新的核心挑戰(zhàn)。首先，新興話題檢測的核心問題是話題的早期發(fā)現(xiàn)，傳統(tǒng)的基于聚類[4-10]、主題模型[11-13]、矩陣分解[14-15]、混合模型[16]、神經(jīng)網(wǎng)絡(luò)[17]等技術(shù)的話題發(fā)現(xiàn)方法，常常需要足夠的語料規(guī)模才能保證話題發(fā)現(xiàn)的性能。然而，在話題產(chǎn)生早期，話題尚未成為熱點(diǎn)話題之初，其相關(guān)的語料，往往極為稀少，不足以保證上述技術(shù)能夠產(chǎn)生足夠好的發(fā)現(xiàn)效果。以K-means聚類方法為例，當(dāng)某一類的樣本較少時(shí)，該類樣本常常會(huì)被誤認(rèn)為噪音而不是新的類別。因此，如何在稀疏的樣本中準(zhǔn)確發(fā)現(xiàn)新興話題，是新興話題檢測任務(wù)面對的第一個(gè)新的核心挑戰(zhàn)。

其次，社交網(wǎng)絡(luò)洪泛式信息傳播造成的海量數(shù)據(jù)流，給實(shí)時(shí)分析帶來挑戰(zhàn)。以Twitter為例，目前Twitter上有五億多用戶，每天產(chǎn)生多達(dá)五億條的實(shí)時(shí)推文。一方面，如此海量且快速演化的信息中，小體量的新興話題很容易被眾多大體量的熱點(diǎn)話題所吞噬，從而難以捕捉。另一方面，巨大的數(shù)據(jù)規(guī)模本身對傳統(tǒng)的話題分析技術(shù)的計(jì)算效率和實(shí)時(shí)性也提出了新的挑戰(zhàn)。因此，從海量且快速流動(dòng)變化的社交網(wǎng)絡(luò)信息中，區(qū)分熱點(diǎn)話題，迅速捕捉剛剛發(fā)生的新話題，是新興話題任務(wù)的又一個(gè)重大挑戰(zhàn)。

第三，社交網(wǎng)絡(luò)上用戶產(chǎn)生內(nèi)容(user generated content, UGC)具有文本短、內(nèi)容雜、語言質(zhì)量差等獨(dú)特性質(zhì)。如微博中的內(nèi)容是普通用戶產(chǎn)生的，缺乏專業(yè)的編輯，用詞比較隨意，有很多的縮寫和不規(guī)范的語法，其中還混雜著很多個(gè)人狀態(tài)信息和大量的垃圾信息[18]；微博消息的長度大都非常短，導(dǎo)致數(shù)據(jù)非常稀疏，詞與詞之間的共現(xiàn)關(guān)系在統(tǒng)計(jì)意義上的顯著性不強(qiáng)，許多常用的文本分析技術(shù)在其上的效果較差[19]。因此，社交網(wǎng)絡(luò)上的用戶產(chǎn)生數(shù)據(jù)的特性對新興話題的發(fā)現(xiàn)也提出了極大的挑戰(zhàn)。

按照解決新興話題發(fā)現(xiàn)問題的角度不同，目前的研究方法主要分為兩類： 一類是基于內(nèi)容特征的突發(fā)性分析方法；另一類是基于信息傳播特征的流行度預(yù)測方法。內(nèi)容特征又分為文本特征和非文本特征兩類，文本特征主要包括關(guān)鍵詞、Hashtag、用戶名、提及(mentioning)行為標(biāo)識(shí)等；非文本特征主要包括URL、圖像、視頻等，現(xiàn)有的方法有的對一種特征進(jìn)行重點(diǎn)分析，有的則從多個(gè)特征綜合考慮?；趦?nèi)容特征的方法主要通過分析關(guān)鍵詞的使用趨勢，或者圖像的轉(zhuǎn)發(fā)變化趨勢等判斷話題是否新興話題。信息傳播特征則包括用戶網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、傳播者興趣模型、用戶興趣網(wǎng)絡(luò)社區(qū)等?；谛畔鞑ツＰ偷姆椒▌t主要通過分析信息的可能傳播路徑，以及潛在參與用戶的影響力等，預(yù)測信息的傳播發(fā)展趨勢，判斷話題是否可能成為新興話題。

2 基于內(nèi)容特征的方法

新興話題檢測的研究涉及到話題的定義，Gullie等人[20]定義了話題的三種表示方式： 1)一個(gè)詞就是一個(gè)話題； 2)多個(gè)詞表示一個(gè)話題； 3)詞集合上的概率分布。早期的研究從內(nèi)容特征的角度入手，結(jié)合時(shí)間因素，通過分析社交網(wǎng)絡(luò)中的內(nèi)容特征隨時(shí)間的突發(fā)變化找出新興話題。Kleinberg[21]首次利用自動(dòng)機(jī)建模隨時(shí)間順序到達(dá)的文檔流，用自動(dòng)機(jī)之間的狀態(tài)轉(zhuǎn)換識(shí)別話題中的突發(fā)特征。Leskovec等人[22]進(jìn)一步研究發(fā)現(xiàn)新聞和博客中的話題隨時(shí)間呈現(xiàn)出起起落落的動(dòng)態(tài)變化，并從全局和局部兩個(gè)角度進(jìn)行定量的分析，雖然文中沒有提及到如何檢測新興話題，但是讓研究人員對話題隨時(shí)間的變化關(guān)系有了清晰的認(rèn)識(shí)。

基于內(nèi)容特征的方法主要是通過觀察話題的內(nèi)容特征隨時(shí)間的變化趨勢，識(shí)別特征突發(fā)改變的時(shí)間點(diǎn)[23-36]。根據(jù)處理內(nèi)容的不同，可以分為基于文本特征的方法和基于非文本特征的方法。根據(jù)對時(shí)間的處理方式不同，可以分為離散時(shí)間模型和連續(xù)時(shí)間模型，目前大部分方法都采用離散時(shí)間模型。所謂的離散時(shí)間模型，就是把時(shí)間劃分成連續(xù)的時(shí)間窗口，以時(shí)間窗口作為話題分析的基本時(shí)間單位。根據(jù)任務(wù)的服務(wù)對象不同，又可分為通用目的話題檢測和針對特定組織機(jī)構(gòu)的話題檢測。

Mathioudakis等人[24]觀察到新話題的興起會(huì)引起話題相關(guān)的關(guān)鍵詞特征的突發(fā)改變，并將這類關(guān)鍵詞定義為突發(fā)關(guān)鍵詞(burst keyword)，據(jù)此提出了一種在Twitter上進(jìn)行新興話題分析的框架TwitterMonitor，并被以后的研究廣泛的采用，如圖1所示。該框架分為突發(fā)關(guān)鍵詞檢測、關(guān)鍵詞聚類和趨勢分析等關(guān)鍵步驟。突發(fā)關(guān)鍵詞檢測的目的是找到新興話題突發(fā)特征詞集合，關(guān)鍵詞聚類則把屬于同一個(gè)話題的關(guān)鍵詞組合在一起，趨勢分析根據(jù)檢測出的關(guān)鍵詞組，檢索出關(guān)鍵詞所屬的微博內(nèi)容，利用內(nèi)容摘要方法給出話題的詳細(xì)描述。下面介紹一些基于內(nèi)容特征的新興話題檢測模型。

圖1 基于內(nèi)容特征的新興話題檢測框架

2.1 文本特征方法

文本特征方法是指利用微博消息中的文本內(nèi)容等特征隨時(shí)間的變化來檢測新興話題。該類方法研究重點(diǎn)在于文本特征的定義和抽取，垃圾文本特征的過濾，與外部知識(shí)庫的融合，以及話題的發(fā)展趨勢預(yù)測等方面。按照話題定義，可以分為基于突發(fā)關(guān)鍵詞的方法和基于主題模型的方法。

Shamma等人[25]提出了在微博中檢測PT(peaky topics)和PCT(persistent conversational topics)兩種話題的方法，采用單個(gè)詞表示一個(gè)話題。其文本特征的計(jì)算方法是將微博按時(shí)間切分到一個(gè)個(gè)時(shí)間窗口中，將每個(gè)時(shí)間窗口中的所有微博消息看成是一個(gè)偽文檔，通過計(jì)算不同時(shí)間片中單詞的正規(guī)化詞頻ntf(normalized term frequency)特征的變化來檢測兩類話題 ，ntf的定義如式(1)所示。

(1)

ntft,i表示時(shí)間窗口t中標(biāo)號為i的單詞的正規(guī)化詞頻，tft,i表示時(shí)間窗口t內(nèi)含有單詞i的消息數(shù)量，cfi表示當(dāng)前語料中包含單詞i的所有消息數(shù)量。PT話題通過識(shí)別ntf短時(shí)間內(nèi)達(dá)到峰值，然后又迅速回歸常態(tài)的單詞來判定的，具有高度的時(shí)間局部性，表現(xiàn)出文本突發(fā)特征的話題；PCT話題是通過識(shí)別ntf短時(shí)間內(nèi)達(dá)到峰值之后頻率雖有降低但仍顯著高于均值并持續(xù)一段時(shí)間的單詞來判定的。從算法的描述中可以看出該算法執(zhí)行簡單，適合大規(guī)模語料集合，但是只用一個(gè)單詞表示話題，描述能力較弱。

Cataldi等人[26]提出的方法也是基于文本特征—增強(qiáng)正規(guī)化詞頻antf(augmented normalized term frequency)[27]，但是同時(shí)考慮了用戶在社交網(wǎng)絡(luò)中的權(quán)威性，利用PageRank算法得到用戶的權(quán)威值，最后結(jié)合antf計(jì)算出每個(gè)詞的能量特征，觀察比較詞能量特征在不同時(shí)間窗口的變化找出具有突發(fā)特征的詞，最后通過聚類的方法找出相關(guān)的新興話題，該方法采用詞集合的方式表示一個(gè)話題，與上述兩種方法的不同點(diǎn)在于考慮了用戶的社交屬性，提高了內(nèi)容特征的精度。

主題模型(latent dirichlet allocation，LDA)在文本處理領(lǐng)域取得了巨大的成功，其話題表示方式采用的是詞集合上的概率分布，相比較Shamma提出的方法，話題的表示更清晰，因此，基于LDA的主題模型的社交網(wǎng)絡(luò)新興話題檢測方法得到了廣泛的研究[28-29]。由于用戶產(chǎn)生內(nèi)容的特點(diǎn)，傳統(tǒng)的LDA模型在微博語料上的效果并不理想，Mehrotra提出了四種微博消息聚合的方法來改進(jìn)LDA在用戶產(chǎn)生內(nèi)容上的效果，分別是將屬于同一作者的所有微博、將檢測出具有突發(fā)特征的詞所屬的微博，將屬于預(yù)定時(shí)間間隔的微博或?qū)儆谕籋ashtag的微博聚合成一個(gè)文檔。在不改變標(biāo)準(zhǔn)LDA結(jié)構(gòu)的情況下，將聚合后的微博文檔作為輸入，取得了比不聚合之前更好的效果，其中Hashtag聚合方式效果提升最明顯。但是，由于主題模型訓(xùn)練和推斷時(shí)間在實(shí)際處理海量數(shù)據(jù)過程中開銷較大，離實(shí)際使用還有較大距離。

為了應(yīng)對微博內(nèi)容的文本短、垃圾多、用語不規(guī)范等特點(diǎn)，EDCoW[30]方法利小波分析方法對微博中出現(xiàn)單詞的頻率構(gòu)建信號，通過檢測自相關(guān)(auto-correlation)的詞來去除垃圾詞，大大降低了備選詞集的大小。TwEvent[31]利用n-grams分析Twitter中消息的內(nèi)容特征，同時(shí)借助Wikipedia和微軟的“Web N-gram Services”中的統(tǒng)計(jì)信息過濾掉不重要的特征。該方法采用外部知識(shí)庫的信息來過濾微博消息中大量的垃圾和噪音，是對TwitterMonitor框架的擴(kuò)展，有助去除微博內(nèi)容中的噪音，但是對知識(shí)庫有較大的依賴性，可能會(huì)遺漏部分話題或事件。賀敏等人[32]提出了一種基于有意義串的微博新興話題發(fā)現(xiàn)方法，利用詞頻、上下文、規(guī)則等多種策略發(fā)現(xiàn)表示話題突發(fā)特征的有意義串，通過聚類有意義串發(fā)現(xiàn)有關(guān)的話題。該方法與傳統(tǒng)基于文本特征不同在于其將文本特征表示為有意義串。有意義串是包含具體語義、靈活獨(dú)立的語言單元，能在多種語境中使用，克服了微博數(shù)據(jù)高維稀疏導(dǎo)致內(nèi)容關(guān)系難以準(zhǔn)確計(jì)算的問題。

2.2 非文本特征方法

文本特征方法以社交網(wǎng)絡(luò)內(nèi)容中的關(guān)鍵詞特征為基礎(chǔ)進(jìn)行研究，但是隨著非文本媒體如圖像、視頻、URL的流行，僅采用關(guān)鍵詞特征的方法已經(jīng)不能全面準(zhǔn)確反映話題的內(nèi)容信息，因此，有必要結(jié)合社交網(wǎng)絡(luò)中豐富的用戶關(guān)系數(shù)據(jù)(如提及行為，好友關(guān)系等)來進(jìn)行新興話題的檢測。

目前，在利用非文本內(nèi)容信息的檢測方法上，Takahashi等人提出了通過檢測用戶社交過程中提及行為的異常來檢測新興話題的方法[33]，該方法利用概率模型建模每個(gè)用戶的提及行為，設(shè)T為訓(xùn)練集，T中的提及行為總數(shù)為m，用戶v在T中的提及行為數(shù)為mv，則用戶v的提及行為的概率P(v|T)=mv/m，為了估計(jì)不在訓(xùn)練集T中出現(xiàn)用戶的提及行為概率，采用了基于CRP(Chinese Restaurant Process)估計(jì)方法，引入了一個(gè)參數(shù)γ，則對于在T中出現(xiàn)的用戶，其提及行為概率如式(2)所示。

(2)

對于不在T中出現(xiàn)的用戶，其提及行為概率為如式(3)所示。

(3)

Chen等人[35]提出了一種基于特定組織的新興話題檢測方法，與之前方法的不同之處在于除了考慮微博內(nèi)容外，與組織相關(guān)的用戶及其社會(huì)關(guān)系也被考慮進(jìn)來。作者定義了話題相關(guān)的用戶和微博影響，并由此計(jì)算出話題的六個(gè)關(guān)鍵特征，包括用戶數(shù)量增長率、微博數(shù)量增長率、轉(zhuǎn)發(fā)微博數(shù)量增長率、組織關(guān)鍵用戶中高影響力用戶的比例、組織關(guān)鍵詞中高影響力關(guān)鍵詞的比例、當(dāng)前時(shí)間窗口內(nèi)的微博積累權(quán)重，把新興話題檢測看成為一個(gè)分類問題，先通過增量聚類方法發(fā)現(xiàn)候選的話題，接著利用SVM(support vector machine)分類算法找出新興話題。在話題趨勢預(yù)測方面，Lu等人[36]利用股票交易中一種常見的技術(shù)分析工具M(jìn)ACD(moving average convergence divergence)來分析Twitter中詞隨時(shí)間的變化特征，與之前的方法相比，該方法不僅能夠預(yù)測話題的興起，還可以預(yù)測話題的衰亡。

2.3 小結(jié)

基于內(nèi)容特征的在線社交網(wǎng)絡(luò)新興話題檢測方法，旨在通過捕捉話題相關(guān)的內(nèi)容特征發(fā)生的異常變化，找到相關(guān)的新興話題，而內(nèi)容特征的變化從概率上講是通過觀測值和期望值之間的背離來衡量的。該方法通過首先過濾出具有突發(fā)特征的消息，大大降低了數(shù)據(jù)的規(guī)模，進(jìn)一步的處理可以借鑒傳統(tǒng)話題檢測手段，因此，該方法從本質(zhì)上講是對傳統(tǒng)話題檢測手段的延伸和擴(kuò)展。

圖2 某話題消息數(shù)隨時(shí)間變化關(guān)系

應(yīng)該指出的是，基于內(nèi)容特征的方法需要檢測到內(nèi)容特征的突發(fā)改變，即觀測值和期望值之間的背離，也就是說社交網(wǎng)絡(luò)中對某一話題產(chǎn)生了一定數(shù)量的轉(zhuǎn)發(fā)和評論，并且已經(jīng)達(dá)到了顯著的水平。這在客觀上造成了新興話題被檢測出的時(shí)間較大地滯后于話題實(shí)際發(fā)生的時(shí)間。如圖2所示，坐標(biāo)軸中的曲線表示某一話題相關(guān)的消息數(shù)隨時(shí)間變化的趨勢，基于內(nèi)容特征的檢測方法一般會(huì)在t2時(shí)刻做出響應(yīng)，此時(shí)離話題發(fā)生已經(jīng)過了較長的時(shí)間。因此，如何在更早的時(shí)間，如t1時(shí)刻附近檢測出話題是一個(gè)需要進(jìn)一步研究的問題，t1時(shí)刻與話題相關(guān)的消息在網(wǎng)絡(luò)中剛剛出現(xiàn)零星的傳播，還沒有形成一定的規(guī)模。此外，基于內(nèi)容特征的方法也不能預(yù)測話題的參與者以及最終話題傳播的范圍，在需要預(yù)測話題參與者和爆發(fā)規(guī)模的場景中，可以采用基于信息傳播模型的話題發(fā)現(xiàn)方法。

3 基于信息傳播模型的方法

傳播問題在流行病學(xué)中已經(jīng)研究了較長的時(shí)間，如對病毒擴(kuò)散機(jī)制的研究等。社交網(wǎng)絡(luò)中用戶轉(zhuǎn)發(fā)消息的行為，造成了承載信息的消息在網(wǎng)絡(luò)的節(jié)點(diǎn)之間和社區(qū)之間傳播，是新興話題形成的客觀條件。因此，研究社交網(wǎng)絡(luò)上的信息傳播或擴(kuò)散(information diffusion or propagation)現(xiàn)象的規(guī)律，對于新興話題的檢測有重要作用的。

從信息傳播的角度考慮，話題之所以流行，是因?yàn)橛写罅康挠脩艮D(zhuǎn)發(fā)了相關(guān)消息，引起了廣泛的關(guān)注和評論。因此，如何將信息傳播的模型運(yùn)用于社交網(wǎng)絡(luò)的新興話題檢測也是目前新興話題檢測研究的熱點(diǎn)。歸納起來，可以分為兩類，即基于關(guān)鍵節(jié)點(diǎn)的檢測和基于消息初始傳播動(dòng)態(tài)的檢測。首先，介紹在線社交網(wǎng)絡(luò)中經(jīng)典的信息傳播模型。

3.1 信息傳播模型

針對不同的應(yīng)用領(lǐng)域，研究人員提出了各種各樣的模型，如建模疾病傳播的SIS(susceptible infected susceptible)、SIR(susceptible infected removed)等；對于在線社交網(wǎng)絡(luò)，可以看成一個(gè)圖結(jié)構(gòu)，如微博網(wǎng)絡(luò)可以看一個(gè)有向圖G(V,E)，頂點(diǎn)集V表示用戶的集合，邊集E為用戶之間的關(guān)系，假設(shè)用戶u關(guān)注了用戶v，則∈E。由于其具有顯式的網(wǎng)絡(luò)結(jié)構(gòu)，有以下兩種基本的傳播模型，獨(dú)立級聯(lián)模型IC(independent cascades)[37]和線性閾值模型LT(linear threshold)[38]。這兩種模型都將傳播時(shí)間離散化，G中的節(jié)點(diǎn)有激活和非激活兩種狀態(tài)，所有的激活節(jié)點(diǎn)的傳播過程是同步的，且有以下假設(shè)：

1) 單調(diào)假設(shè)，一個(gè)節(jié)點(diǎn)被激活后不能再變成非激活狀態(tài)。

2) 每次信息傳播過程都是由若干個(gè)種子節(jié)點(diǎn)組成的初始集合開始的。

3) 每一個(gè)節(jié)點(diǎn)只能從他的鄰居節(jié)點(diǎn)中接收到傳播消息。

4) 網(wǎng)絡(luò)結(jié)構(gòu)是靜態(tài)的，不隨時(shí)間動(dòng)態(tài)改變。

運(yùn)用IC模型需要事先計(jì)算節(jié)點(diǎn)之間的傳播概率，而LT模型需要事先定義加點(diǎn)之間的影響度并設(shè)置每個(gè)節(jié)點(diǎn)的激活閾值。IC模型認(rèn)為節(jié)點(diǎn)之間的影響是獨(dú)立的，設(shè)∈E，節(jié)點(diǎn)v以概率puv影響節(jié)點(diǎn)u，設(shè)在某個(gè)時(shí)刻t，v被激活，則在t+1時(shí)刻，v有一次以概率puv激活節(jié)點(diǎn)u的機(jī)會(huì)。LT模型則認(rèn)為節(jié)點(diǎn)受其激活的鄰居節(jié)點(diǎn)的共同影響，設(shè)U?V，滿足?u∈U，?∈E，U中每個(gè)節(jié)點(diǎn)對v的影響力為fuv，設(shè)在某個(gè)時(shí)刻t，U中被激活的用戶為act(U)，如果∑u∈act(U)fuv>θv，則v在t+1時(shí)刻被激活。上述的過程不斷重復(fù)直到?jīng)]有新的節(jié)點(diǎn)被激活為止。

Saito等人[39-40]進(jìn)一步打破了上述兩種模型中離散時(shí)間和同步傳播假設(shè)，分別提出考慮到傳播中時(shí)間延遲影響的CTIC和CTLT(continuoustimedelayindependentcascadeandcontinuoustimedelaylinearthreshold)模型，以及考慮到傳播中異步性的AsIC和AsLT(asynchronousindependentcascadesandasynchronouslinearthreshold)模型。王巍等人[41]在消息傳播模型的基礎(chǔ)上，提出了一種基于微博粉絲關(guān)系、用戶活躍度和影響力的話題傳播模型，提出了“內(nèi)外場強(qiáng)”的概念來描述影響信息傳播的內(nèi)在和外在因素。

3.2 基于關(guān)鍵節(jié)點(diǎn)的檢測

圖3 某話題消息傳播級聯(lián)示意圖

運(yùn)用信息傳播模型進(jìn)行新興話題檢測，最直接的方式就是在社交網(wǎng)絡(luò)中選取關(guān)鍵的節(jié)點(diǎn)集合，圖3展示了某話題的消息傳播軌跡，消息從節(jié)點(diǎn)a發(fā)出經(jīng)多個(gè)節(jié)點(diǎn)的轉(zhuǎn)發(fā)不斷傳播。雖然傳感器在節(jié)點(diǎn)b、c、d和e都可以檢測到該消息，但是時(shí)效存在巨大的差異。新興話題的檢測，就是盡可能早的檢測到流行或爆發(fā)的話題，對于該話題來說，節(jié)點(diǎn)b和c是好的檢測點(diǎn)。這個(gè)問題可以定義為： 選取網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)，使得能夠在新興話題爆發(fā)之前盡可能早的覆蓋到新興話題的傳播[42]，即影響最大化問題。影響最大化問題是建立在傳播模型上的最優(yōu)化問題[38]，其研究重點(diǎn)在于傳播模型建模，傳播概率的學(xué)習(xí)以及算法時(shí)間復(fù)雜度的優(yōu)化。

3.3 基于消息初始傳播動(dòng)態(tài)的檢測

與基于節(jié)點(diǎn)選擇的方法不同，基于消息初始化的傳播方法假設(shè)已經(jīng)觀測到某話題消息被前k個(gè)節(jié)點(diǎn)轉(zhuǎn)發(fā)，預(yù)測話題將來是否可能爆發(fā)。如圖4所示，觀察到某話題的消息的初始傳播動(dòng)態(tài)為節(jié)點(diǎn)集合{a, b, c}，需要預(yù)測消息可能的傳播范圍?？梢越柚绊懽畲蠡瘑栴}中求k個(gè)節(jié)點(diǎn)傳播范圍的方法，但是，在影響最大化問題中，對用戶之間的傳播概率沒有做過多的探究，基本都是人為設(shè)定的統(tǒng)一概率，這種對問題的簡化和真實(shí)的社交網(wǎng)絡(luò)有很大區(qū)別。真實(shí)的社交網(wǎng)絡(luò)中，用戶和用戶間的傳播影響力存在很大的差異，如同一用戶和他的不同好友之間的交互頻度不同，存在親疏之別。因此，為了在真實(shí)的社交網(wǎng)絡(luò)中利用消息的初始傳播動(dòng)態(tài)來檢測新興話題，首先面臨的問題是如何準(zhǔn)確估計(jì)用戶的傳播影響力，下面簡要介紹影響力估計(jì)的相關(guān)工作。

圖4 某話題消息的初始傳播動(dòng)態(tài)

用戶的影響力估計(jì)是目前學(xué)術(shù)界研究的熱點(diǎn)[43-47]。基于網(wǎng)絡(luò)結(jié)構(gòu)的影響力分析方面，Kitsak等人[48]發(fā)現(xiàn)最有效的轉(zhuǎn)播者不一定是節(jié)點(diǎn)度數(shù)高的節(jié)點(diǎn)，也不一定是介數(shù)中心度高的節(jié)點(diǎn)，而是通過k-shell分解得到的核心節(jié)點(diǎn)。Garas等人[49]意識(shí)到網(wǎng)絡(luò)中邊的權(quán)重是描述網(wǎng)絡(luò)結(jié)構(gòu)的重要因素，據(jù)此提出了一種帶權(quán)重的k-shell分解的方法，發(fā)現(xiàn)帶權(quán)重的k-shell分解方法找到的核心節(jié)點(diǎn)在信息擴(kuò)散方面的影響力一致優(yōu)于不帶權(quán)重的k-shell分解方法。Kwak等人[50]對Twitter數(shù)據(jù)集Twitter7[51]上的用戶進(jìn)行了排序分析，用Kendall相關(guān)系數(shù)[52]進(jìn)行了比較，實(shí)驗(yàn)結(jié)果和Kitsak的發(fā)現(xiàn)是一致的。Weng等人[53]綜合考慮了用戶的消息內(nèi)容和關(guān)系結(jié)構(gòu)，基于PageRank算法[54]提出了TwitterRank算法來識(shí)別Twitter上話題相關(guān)的關(guān)鍵用戶。Lv等人[55]提出了LeaderRank算法，通過加一個(gè)背景節(jié)點(diǎn)(ground node)解決了PageRank中用戶排序不唯一的問題，具有較好的抗干擾性和魯棒性。

Tang等人[56-57]從話題的角度提出了TAP(Topical Affinity Propagation)模型來計(jì)算科學(xué)合作網(wǎng)等社會(huì)網(wǎng)中的用戶影響力，其方法是利用因子圖聯(lián)合建模用戶節(jié)點(diǎn)的話題分布和結(jié)構(gòu)，并提出了有效的分布式的模型訓(xùn)練算法。Liu等人[58]研究了異質(zhì)網(wǎng)絡(luò)結(jié)構(gòu)中的影響力問題，提出了一種概率產(chǎn)生式模型，聯(lián)合利用消息內(nèi)容和社交網(wǎng)絡(luò)結(jié)構(gòu)信息來建模用戶歷史數(shù)據(jù)的話題分布來表示用戶的興趣，借此可以計(jì)算出用戶之間的影響力。Bian等人[59]從用戶行為的角度研究了在微博網(wǎng)絡(luò)中預(yù)測新興話題和傳播者的問題，方法從用戶的轉(zhuǎn)發(fā)行為入手，定義了基于信息擴(kuò)散的影響力的三個(gè)方面，即流行度相關(guān)的影響力，興趣相關(guān)的影響力和社交相關(guān)的影響力，最后利用因子圖(factor graph)聯(lián)合建模用戶的影響力。Saito等人[37]聯(lián)合建模用戶的影響力和傳播模型，將用戶的影響力轉(zhuǎn)化為模型的參數(shù)，根據(jù)社交網(wǎng)絡(luò)上的信息傳播的歷史數(shù)據(jù)，利用極大似然方法來學(xué)習(xí)用戶的社交影響力。

3.4 小結(jié)

基于信息傳播模型的新興話題方法，其優(yōu)勢是可以從微觀層面更早地檢測出新興話題，且能預(yù)測話題傳播的參與者，因而逐漸成為研究熱點(diǎn)。但是，應(yīng)該指出，基于傳播模型方法的性能在很大程度上取決于傳播模型的好壞和用戶間傳播影響力的計(jì)算，在這點(diǎn)上，學(xué)術(shù)界目前的研究還沒有能很好的和新興話題發(fā)現(xiàn)應(yīng)用結(jié)合起來；此外，該類方法需要豐富的歷史傳播數(shù)據(jù)進(jìn)行模型的訓(xùn)練，這對數(shù)據(jù)的采集和處理也提出了較高的要求。

4 未來研究方向

(1) 信息傳播和社交網(wǎng)絡(luò)的共同演化： 在線社交網(wǎng)絡(luò)結(jié)構(gòu)的變化對現(xiàn)有傳播模型的影響需要進(jìn)一步探討。事實(shí)上，社交網(wǎng)絡(luò)結(jié)構(gòu)不是一成不變的，而是動(dòng)態(tài)變化的[60]，Myers等人[61]研究了Twitter網(wǎng)絡(luò)中用戶的發(fā)帖和轉(zhuǎn)發(fā)行為與網(wǎng)絡(luò)結(jié)構(gòu)之間的動(dòng)態(tài)關(guān)系，發(fā)現(xiàn)網(wǎng)絡(luò)中的信息級聯(lián)傳播會(huì)極大改變用戶的局部結(jié)構(gòu)(即朋友關(guān)系)，并表現(xiàn)出突發(fā)性。而現(xiàn)有的傳播模型還沒有考慮到網(wǎng)絡(luò)結(jié)構(gòu)隨時(shí)間的變化因素，因此，設(shè)計(jì)新的傳播模型來建模時(shí)變的社交網(wǎng)絡(luò)是一個(gè)有價(jià)值的研究內(nèi)容。

(2) 封閉世界假設(shè)的突破： 目前研究社交網(wǎng)絡(luò)中信息傳播的一個(gè)公認(rèn)的假設(shè)是封閉世界假設(shè)[20]： 即一個(gè)社交網(wǎng)絡(luò)就是一個(gè)封閉的世界，節(jié)點(diǎn)之間的信息傳播只會(huì)沿著網(wǎng)絡(luò)中的邊進(jìn)行，節(jié)點(diǎn)不會(huì)受到網(wǎng)絡(luò)之外的環(huán)境的影響。但是Myers等人[61]觀察到網(wǎng)絡(luò)中的信息存在跳躍傳播的現(xiàn)象，并指出在Twitter網(wǎng)絡(luò)中，29%的信息傳播受到外部環(huán)境的影響，如何定量的分析外部因素對社交網(wǎng)絡(luò)中信息傳播的影響，進(jìn)而更好地指導(dǎo)新興話題的檢測，是一個(gè)有待深入研究的問題。

(3) 多源點(diǎn)的信息傳播： 目前針對社交網(wǎng)絡(luò)中信息傳播的研究，大部分僅考慮單源信息的傳播情況。而在實(shí)際的傳播過程當(dāng)中，話題中消息的傳播過程往往是多傳播源共同作用的結(jié)果。多個(gè)傳播源之間既有競爭又存在協(xié)作關(guān)系[62]，較好的理解和建模多源點(diǎn)信息傳播問題將有助于提高網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)選取和消息傳播范圍預(yù)測的準(zhǔn)確性。

(4) 大規(guī)模分布式檢測算法： 目前的研究主要集中在如何提高話題發(fā)現(xiàn)和預(yù)測的準(zhǔn)確性，但是社交網(wǎng)絡(luò)產(chǎn)生的數(shù)據(jù)規(guī)模十分巨大，如Twitter和新浪微博各自有五億多用戶，每天新產(chǎn)生數(shù)億條消息，如此海量的數(shù)據(jù)給現(xiàn)有的計(jì)算機(jī)體系結(jié)構(gòu)和算法帶來了不小的挑戰(zhàn)。未來的新興話題發(fā)現(xiàn)算法有賴于大規(guī)模文檔快速聚類算法和大規(guī)模社交網(wǎng)絡(luò)信息傳播算法的進(jìn)步。

5 結(jié)論

本文回顧了社交網(wǎng)絡(luò)中新興話題發(fā)現(xiàn)領(lǐng)域的最新進(jìn)展，首先，內(nèi)容突發(fā)特征選取和基于突發(fā)特征的時(shí)序分析方法是研究的主流，但是，突發(fā)特征的出現(xiàn)依賴于話題相關(guān)的消息數(shù)量達(dá)到一定的顯著水平，因而基于內(nèi)容突發(fā)特征的檢測往往不能在第一時(shí)間發(fā)現(xiàn)新興話題。接著，闡述了從信息傳播模型的角度進(jìn)行新興話題發(fā)現(xiàn)的有關(guān)方法，該方法與主流方法相比，具有實(shí)時(shí)性高、描述性強(qiáng)等優(yōu)點(diǎn)，目前已成為研究熱點(diǎn)。利用信息傳播模型涉及到對用戶的影響力的定量表示，現(xiàn)在的方法主要從內(nèi)容特征、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征和話題特征等角度對影響力進(jìn)行研究，從歷史數(shù)據(jù)中學(xué)習(xí)出用戶的影響力，然而如何估計(jì)用戶的影響力目前仍然是一個(gè)開放的問題。最后，探討了該領(lǐng)域進(jìn)一步研究的方向，如社交網(wǎng)絡(luò)中海量實(shí)時(shí)數(shù)據(jù)處理給現(xiàn)有處理手段帶來了巨大的挑戰(zhàn)，需要從算法和體系結(jié)構(gòu)進(jìn)行革新，社交網(wǎng)絡(luò)結(jié)構(gòu)的動(dòng)態(tài)變化和外部環(huán)境對社交網(wǎng)絡(luò)中新興話題檢測造成的影響還需要進(jìn)一步評估等。

[1] Victor Lavrenko, James Allan, Edward DeGuzman, et al. Relevance models for topic detection and tracking[C]// Proceedings of the 2nd International Conference on Human Language Technology Research. San Francisco, USA, 2002: 115-121.

[2] 洪宇, 張宇, 劉挺等. 話題檢測與跟蹤的評測及研究綜述[J]. 中文信息學(xué)報(bào), 2007, 21(6): 71-87.

[3] James Allan, Victor Lavrenko, Daniella Malin, et al. Detections, bounds, and timelines: Umass and tdt-3[C]// Proceedings of Topic Detection and Tracking Workshop. Vienna, VA, 2000: 167-174.

[4] James Allan, Jaime G Carbonell, George Doddington, et al. Topic detection and tracking pilot study final report[C]// Proceedings of the DARPA Broadcast News Transcription and Understanding Workshop. 1998: 194-218.

[5] Yiming Yang, Thomas Pierce, Brian T Archibald, et al. Learning approaches for detecting and tracking news events[J]. IEEE Intelligent Systems, 1999, 14(4): 32-43.

[6] Douglass R Cutting, David R Karger, Jan O Pedersen, et al. Scatter/gather: A cluster-based approach to browsing large document collections[C]//Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval. 1992: 318-329.

[7] 于滿泉, 駱衛(wèi)華, 許洪波等. 話題識(shí)別與跟蹤中的層次化話題識(shí)別技術(shù)研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2006, 43(3): 489-495.

[8] David Arthur and Sergei Vassilvitskii. k-means++: The advantages of careful seeding[C]//Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics. Philadelphia, USA, 2007: 1027-1035.

[9] D. Sculley. Web Scale K-Means clustering[C]//Proceedings of the 19th international conference on World Wide Web. New York, USA, 2010: 1177-1178.

[10] 張小明,李舟軍,巢文涵.基于增量型聚類的自動(dòng)話題檢測研究[J]. 軟件學(xué)報(bào), 2012, 23(6): 1578-1587.

[11] Thomas Hofmann. Probabilistic latent semantic indexing[C]//Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval. New York, USA, 1999: 50-57.

[12] David M. Blei, Andrew Y. Ng, Michael I. Jordan. Latent Dirichlet Allocation[J]. Journal of Machine Learning Research , 2003, 3: 993-1022.

[13] 單斌, 李芳. 基于LDA話題演化研究方法綜述[J]. 中文信息學(xué)報(bào), 2010, 24(6): 43-68.

[14] Scott Deerwester, Susan T. Dumais, George W. Furnas, et al. Indexing by latent semantic analysis[J]. Journal of the American society for information science, 1990, 41(6): 391-407.

[15] Wei Xu, Xin Liu, and Yihong Gong. Document clustering based on non-negative matrix factorization[C]//Proceedings of the 26th annual international ACM SIGIR conference on Research and development in information retrieval. New York, USA, 2003: 267-273.

[16] 路榮, 項(xiàng)亮, 劉明榮等. 基于隱主題分析和文本聚類的微博客中新聞話題的發(fā)現(xiàn)[J]. 模式識(shí)別與人工智能, 2012, 25(3): 382-387.

[17] Kanagasabi Rajaraman, Ah-Hwee Tan. Topic Detect ion, Tracking, and Trend Analysis Using Self-Organizing Neural Networks[C]//Proceedings of the 5th Pacific-Asia Conference on Knowledge Discovery and Data Mining. London, UK, 2001: 102-107.

[18] Xia Hu, Jiliang Tang, Huan Liu. Leveraging knowle dge across media for spammer detection in microblogging[C]//Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval. New York, USA, 2014: 547-556.

[19] X.-H. Phan, L.-M. Nguyen, S. Horiguchi. Learning to classify short and sparse text & web with hidden topics from large-scale data collections[C]//Proceeding of the 17th WWW. Beijing, China, 2008: 91- 100.

[20] Adrien Guille, Hakim Hacid, Cecile Favre, et al. Information diffusion in online social networks: A survey[J]. ACM SIGMOD Record, 2013, 42(2): 31-36.

[21] Jon Kleinberg. Bursty and Hierarchical Structure in Streams[C]//Proceedings of the eighth ACM SIGKDD international conference on knowledge discovery and data mining. Edmonton, Canada, 2002: 91- 101.

[22] Jure Leskovec, Lars Backstrom, Jon Kleinberg. Meme-tracking and the dynamics of the news cycle[C]// Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. Paris, France, 2009: 497-506.

[23] Ruchi Parikh, Kamalakar Karlapalem. ET: events from tweets[C]//Proceedings of the 22nd international conference on World Wide Web. Republic and Canton of Geneva, Switzerland, 2013: 613-620.

[24] Michael Mathioudakis, Nick Koudas. TwitterMonitor: Trend Detection over the Twitter Stream[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. New York, USA, 2010: 1155-1158.

[25] David A Shamma Lyndon Kennedy, Elizabeth F Churchil. Peaks and persistence: modeling the shape of microblog conversation[C]//Proceedings of the ACM 2011 conference on Computer supported cooperative work. New York, NY, USA, 2011: 355-358.

[26] Mario Cataldi, Luigi Di Caro, Claudio Schifanella. Emerging Topic Detection on twitter based on temporal and social terms evaluation[C]//Proceedings of the Tenth International Workshop on Multimedia Data Mining. New York, USA, 2010: 4-13.

[27] G Salton, C Buckley. Term-weighting approaches in automatic text retrieval[J]. Information Processing and Management, 1988: 513-523.

[28] Matthew D Hoffman, David M Blei, Francis R Bach. Online Learning for Latent Dirichlet Allocation[C]// Proceedings of NIPS Vancouver, Canada, 2010: 856-864.

[29] Rishabh Mehrotra, Scott Sanner, Wray Buntine, et al. Improving LDA topic models for microblogs via tweet pooling and automatic labeling[C]//Proceedings of the 36th international ACM SIGIR conference on Research and development in information retrieval. New York, USA, 2013: 889-892.

[30] Jianshu Weng, Bu-Sung Li. Event Detection in Twitter[C]//Proceedings of the Fifth International AAAI Conference on Weblogs and Social Media. Barcelona, Spain, 2011: 401-408.

[31] Chenliang Li, Aixin Sun, Anwitaman Datta. Twevent: segment-based event detection from tweets[C]//Proceedings of the 21st ACM international conference on Information and knowledge management. New York, USA, 2012: 155-164.

[32] 賀敏, 王麗宏, 杜攀等. 基于有意義串聚類的微博熱點(diǎn)話題發(fā)現(xiàn)方法[J]. 通信學(xué)報(bào), 2013, (Z1): 256-262.

[33] Toshimitsu Takahashi, Ryota Tomioka, Kenji Yamanishi. Discovering Emerging Topics in Social Streams via Link Anomaly Detection[C]//Proceedings of the 2011 IEEE 11th International Conference on Data Mining. Washington, DC, USA, 2011: 1230-1235.

[34] Adrien Guille, Cécile Favre. Mention-anomaly-based Event Detection and Tracking in Twitter[C]//Proceedings of the IEEE/ACM International Conference on Advances in Social Network Analysis and Mining. Beijing, China, 2014.

[35] Yan Chen, Hadi Amiri, Zhoujun Li, et al. Emerging Topic Detection for Organization from Microblogs[C]// Proceedings of the 36th international ACM SIGIR conference on Research and development in information retrieval. New York, USA, 2013: 43-52.

[36] Rong Lu, Qing Yang. Trend Analysis of News Topics on Twitter[J]. International Journal of Machine Learning and Computing, 2012, 2(3): 327-332.

[37] Jacob Goldenberg Barak Libai, Eitan Muller. Talk of the network: A complex systems look at the underlying process of word-of-mouth[J]. Marketing Letters, 2001, 12(3): 211-223.

[38] David Kempe, Jon Kleinberg, éva Tardos. Maximizing the spread of influence through a social network[C]// Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. New York, USA, 2003: 137-146.

[39] Kazumi Saito, Masahiro Kimura, Kouzou Ohara, et al. Learning Continuous-Time Information Diffusion Model for Social Behavioral Data Analysis[C]//Proceedings of the 1st Asian Conference on Machine Learning: Advances in Machine Learning. Berlin, Heidelberg, 2009: 322-337.

[40] Kazumi Saito, Masahiro Kimura, Kouzou Ohara, et al. Selecting information diffusion models over social networks for behavioral analysis[C]//Proceedings of the 2010 European conference on Machine learning and knowledge discovery in databases. Berlin, Heidelberg, 2010.

[41] 王巍, 李銳光, 周淵等. 基于用戶與節(jié)點(diǎn)規(guī)模的微博突發(fā)話題傳播預(yù)測算法[J]. 通信學(xué)報(bào), 2013, (Z1): 84-91.

[42] Jure Leskovec, Andreas Krause, Carlos Guestrin, et al. Cost-effective Outbreak Detection in Networks[C]// Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. New York, USA, 2007: 420-429.

[43] 赫南, 李德毅, 淦文燕等. 復(fù)雜網(wǎng)絡(luò)中重要性節(jié)點(diǎn)發(fā)掘綜述[J]. 計(jì)算機(jī)科學(xué), 2007, 34 (12): 1-5.

[44] 孫睿, 羅萬伯. 網(wǎng)絡(luò)輿論中節(jié)點(diǎn)重要性評估方法綜述[J]. 計(jì)算機(jī)應(yīng)用研究, 2012, 29(10): 3606-3608.

[45] 劉建國, 任卓明, 郭強(qiáng)等. 復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要性排序的研究進(jìn)展[J]. 物理學(xué)報(bào), 2013, 62(17): 178901.

[46] 趙之瀅, 于海, 朱志良等. 基于網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的節(jié)點(diǎn)傳播影響力分析[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(4): 753-766.

[47] 汪小帆, 李翔, 陳關(guān)榮. 網(wǎng)絡(luò)科學(xué)導(dǎo)論[M]. 北京: 高等教育出版社, 2012.

[48] Maksim Kitsak, Lazaros K. Gallos, Shlomo Havlin, et al. Identifying influential spreaders in complex networks[J]. Nature Physics, 2010, 6(11): 888-893.

[49] Antonios Garas, Frank Schweitzer, Shlomo Havlin. A k-shell decomposition method for weighted networks[J]. New Journal of Physics, 2012, 14(8): 083030.

[50] Haewoon Kwak, Changhyun Lee, Hosung Park, et al. What is Twitter, a Social Network or a News Media?[C]// Proceedings of the 19th international conference on World Wide Web. New York, USA, 2010: 591-600.

[51] J. Yang, J. Leskovec. Patterns of temporal variation in online media[C]//Proceedings of the fourth ACM international conference on web search and data mining. New York, USA, 2011: 177-186.

[52] Ronald Fagin, Ravi Kumar, D. Sivakumar. Comparing top k lists[C]//Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms. Philadelphia, USA, 2003: 28-36.

[53] Jianshu Weng, Ee-Peng Lim, Jing Jiang et al. TwitterRank: Finding Topic-sensitive Influential Twitterers[C]// Proceedings of the third ACM international conference on Web search and data mining. New York, USA, 2010: 261-270.

[54] Sergey Brin, Lawrence Page. The anatomy of a large-scale hypertextual Web search engine[C]//Proceedings of the seventh international conference on World Wide Web. Amsterdam, The Netherlands, 2013: 107-117.

[55] Liyuan Lü, Yi-cheng Zhang, Chi Ho Yeung. et al. Leaders in Social Networks, the Delicious Case[J]. PLoS One, 2011, 6: e21202.

[56] Jie Tang, Jimeng Sun, Chi Wang, et al. Social Influence Analysis in Large-scale Networks[C]//Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. New York, USA, 2009: 807-816.

[57] Jie Tang, Sen Wu， Jimeng Sun. Confluence: Conformity Influence in Large Social Networks[C]// Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. New York, USA, 2013: 347-355.

[58] Lu Liu, Jie Tang, Jiawei Han, et al. Learning Influence from Heterogeneous Social Networks[J]. Data Mining and Knowledge Discovery, 2012, 25(3): 511-544.

[59] Jingwen Bian, Yang Yang， Tat-Seng Chua. Predicting Trending Message and Diffusion Participants in Microblogging Network[C]//Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval. New York, USA, 2014: 537-546.

[60] M. Farajtabar, M. Gomez-Rodriguez, Y. Wang, et al. Co-evolutionary Dynamics of Information Diffusion and Network Structure[C]//Proceedings of the 24th International Conference on World Wide Web Companion. Republic and Canton of Geneva, Switzerland, 2015: 619-620.

[61] S. A. Myers， J. Leskovec. The Bursty Dynamics of the Twitter Information Network[C]//Proceedings of the 23rd international conference on World Wide Web. New York, USA, 2014: 913-924.

[62] S. A. Myers， J. Leskovec. Clash of the contagions: Cooperation and competition in information diffusion[C]// Proceedings of the 12th International Conference on Data Mining. Brussels, Belgium, 2012: 539-548.

Emerging Topic Detection in Online Social Networks: A Survey

GOU Chengcheng1,2, DU Pan1, LIU Yue1, CHENG Xueqi1

(1. CAS Key Lab of Network Data Science and Technology,Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China) (2. University of Chinese Academy of Sciences, Beijing 100190, China)

Emerging topic detection is one of the major research focus in Social Network Analysis. The openness of social networks, microblog in particular, provides unprecedented favorable conditions on which the topics might rage and outbreak. The emerging topics are often accompanied by big news or events, which are about to outbreak and have a significant social impact. How to identify these topics in the early stages is the major research content of the emerging topic detection. The main developments in the field of the emerging topic detection in the recent years are reviewed and the relevant concepts, methods and theory are elaborated. The methods of the emerging topic detection are analyzed and discussed form the perspective of the content bursty feature and information diffusion models. Finally we conclude the paper with an exploration of future research directions.

emerging topic; topic detection; information diffusion; social network

笱程成(1985—)，博士研究生，主要研究領(lǐng)域?yàn)樯缃痪W(wǎng)絡(luò)，數(shù)據(jù)挖掘，機(jī)器學(xué)習(xí)。E?mail：gouchengcheng@software．ict．a(chǎn)c．cn杜攀(1981—)，博士，助理研究員，主要研究領(lǐng)域?yàn)樾畔z索，數(shù)據(jù)挖掘，機(jī)器學(xué)習(xí)。E?mail：dupan@software．ict．a(chǎn)c．cn劉悅(1971—)，博士，副研究員，主要研究領(lǐng)域?yàn)樾畔z索，數(shù)據(jù)挖掘，機(jī)器學(xué)習(xí)。E?mail：liuyue@ict．a(chǎn)c．cn

1003-0077(2016)05-0009-10

2015-05-04 定稿日期： 2016-02-03

國家“九七三”重點(diǎn)基礎(chǔ)研究計(jì)劃基金(2012CB316303，2014CB340401)；國家“八六三”高技術(shù)研究發(fā)展計(jì)劃基金(2015AA015803，2014AA015204)；中國科學(xué)院重點(diǎn)部署項(xiàng)目(KGZD-EW-T03-2)；國家自然科學(xué)基金(61232010，61572473，61303156)；國家242信息安全計(jì)劃基金(2015F028)；山東省自主創(chuàng)新及成果轉(zhuǎn)化專項(xiàng)(2014CGZH1103)；歐盟第七科技框架計(jì)劃項(xiàng)目(FP7)(PIRSES-GA-2012-318939)

TP

A