在線社交網絡中的新興話題檢測技術綜述

笱程成,杜 攀, 劉 悅, 程學旗

(1. 中國科學院 計算技術研究所, 中國科學院網絡數據科學與技術重點實驗室，北京100190; 2. 中國科學院大學, 北京 100190)

在線社交網絡中的新興話題檢測技術綜述

笱程成1,2,杜 攀1, 劉 悅1, 程學旗1

(1. 中國科學院 計算技術研究所, 中國科學院網絡數據科學與技術重點實驗室，北京100190; 2. 中國科學院大學, 北京 100190)

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

新興話題；話題檢測；信息傳播；社交網絡

1 引言

近年來，以Twitter、Facebook、微博和微信為代表的在線社交網絡的迅速發展極大地影響了人們的社交和工作方式。在社交網絡中，個人可以隨時隨地和朋友進行互動，分享自身的相關信息，關注感興趣的用戶，訂閱信息，查看各式各樣的新聞，各種組織和官方機構也可以利用社交網絡發布新產品和新聞。

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

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

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

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

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

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

按照解決新興話題發現問題的角度不同，目前的研究方法主要分為兩類： 一類是基于內容特征的突發性分析方法；另一類是基于信息傳播特征的流行度預測方法。內容特征又分為文本特征和非文本特征兩類，文本特征主要包括關鍵詞、Hashtag、用戶名、提及(mentioning)行為標識等；非文本特征主要包括URL、圖像、視頻等，現有的方法有的對一種特征進行重點分析，有的則從多個特征綜合考慮。基于內容特征的方法主要通過分析關鍵詞的使用趨勢，或者圖像的轉發變化趨勢等判斷話題是否新興話題。信息傳播特征則包括用戶網絡拓撲結構、傳播者興趣模型、用戶興趣網絡社區等。基于信息傳播模型的方法則主要通過分析信息的可能傳播路徑，以及潛在參與用戶的影響力等，預測信息的傳播發展趨勢，判斷話題是否可能成為新興話題。

2 基于內容特征的方法

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

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

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

圖1 基于內容特征的新興話題檢測框架

2.1 文本特征方法

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

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

(1)

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

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

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

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

2.2 非文本特征方法

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

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

(2)

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

(3)

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

2.3 小結

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

圖2 某話題消息數隨時間變化關系

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

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

傳播問題在流行病學中已經研究了較長的時間，如對病毒擴散機制的研究等。社交網絡中用戶轉發消息的行為，造成了承載信息的消息在網絡的節點之間和社區之間傳播，是新興話題形成的客觀條件。因此，研究社交網絡上的信息傳播或擴散(information diffusion or propagation)現象的規律，對于新興話題的檢測有重要作用的。

從信息傳播的角度考慮，話題之所以流行，是因為有大量的用戶轉發了相關消息，引起了廣泛的關注和評論。因此，如何將信息傳播的模型運用于社交網絡的新興話題檢測也是目前新興話題檢測研究的熱點。歸納起來，可以分為兩類，即基于關鍵節點的檢測和基于消息初始傳播動態的檢測。首先，介紹在線社交網絡中經典的信息傳播模型。

3.1 信息傳播模型

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

1) 單調假設，一個節點被激活后不能再變成非激活狀態。

2) 每次信息傳播過程都是由若干個種子節點組成的初始集合開始的。

3) 每一個節點只能從他的鄰居節點中接收到傳播消息。

4) 網絡結構是靜態的，不隨時間動態改變。

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

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

3.2 基于關鍵節點的檢測

圖3 某話題消息傳播級聯示意圖

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

3.3 基于消息初始傳播動態的檢測

與基于節點選擇的方法不同，基于消息初始化的傳播方法假設已經觀測到某話題消息被前k個節點轉發，預測話題將來是否可能爆發。如圖4所示，觀察到某話題的消息的初始傳播動態為節點集合{a, b, c}，需要預測消息可能的傳播范圍。可以借助影響最大化問題中求k個節點傳播范圍的方法，但是，在影響最大化問題中，對用戶之間的傳播概率沒有做過多的探究，基本都是人為設定的統一概率，這種對問題的簡化和真實的社交網絡有很大區別。真實的社交網絡中，用戶和用戶間的傳播影響力存在很大的差異，如同一用戶和他的不同好友之間的交互頻度不同，存在親疏之別。因此，為了在真實的社交網絡中利用消息的初始傳播動態來檢測新興話題，首先面臨的問題是如何準確估計用戶的傳播影響力，下面簡要介紹影響力估計的相關工作。

圖4 某話題消息的初始傳播動態

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

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

3.4 小結

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

4 未來研究方向

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

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

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

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

5 結論

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

[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]. 中文信息學報, 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] 于滿泉, 駱衛華, 許洪波等. 話題識別與跟蹤中的層次化話題識別技術研究[J]. 計算機研究與發展, 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] 張小明,李舟軍,巢文涵.基于增量型聚類的自動話題檢測研究[J]. 軟件學報, 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]. 中文信息學報, 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] 路榮, 項亮, 劉明榮等. 基于隱主題分析和文本聚類的微博客中新聞話題的發現[J]. 模式識別與人工智能, 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] 賀敏, 王麗宏, 杜攀等. 基于有意義串聚類的微博熱點話題發現方法[J]. 通信學報, 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] 王巍, 李銳光, 周淵等. 基于用戶與節點規模的微博突發話題傳播預測算法[J]. 通信學報, 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] 赫南, 李德毅, 淦文燕等. 復雜網絡中重要性節點發掘綜述[J]. 計算機科學, 2007, 34 (12): 1-5.

[44] 孫睿, 羅萬伯. 網絡輿論中節點重要性評估方法綜述[J]. 計算機應用研究, 2012, 29(10): 3606-3608.

[45] 劉建國, 任卓明, 郭強等. 復雜網絡中節點重要性排序的研究進展[J]. 物理學報, 2013, 62(17): 178901.

[46] 趙之瀅, 于海, 朱志良等. 基于網絡社團結構的節點傳播影響力分析[J]. 計算機學報, 2014, 37(4): 753-766.

[47] 汪小帆, 李翔, 陳關榮. 網絡科學導論[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—)，博士研究生，主要研究領域為社交網絡，數據挖掘，機器學習。E?mail：gouchengcheng@software．ict．ac．cn杜攀(1981—)，博士，助理研究員，主要研究領域為信息檢索，數據挖掘，機器學習。E?mail：dupan@software．ict．ac．cn劉悅(1971—)，博士，副研究員，主要研究領域為信息檢索，數據挖掘，機器學習。E?mail：liuyue@ict．ac．cn

1003-0077(2016)05-0009-10

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

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

TP

A