基于拓撲勢的網(wǎng)絡熱點話題發(fā)現(xiàn)研究

淦文燕，劉常昱，李德毅

（1.解放軍理工大學 指揮自動化學院，江蘇 南京200007；2.中國電子系統(tǒng)工程研究所，北京100840）

1 引 言

隨著網(wǎng)絡的普及和web2.0的發(fā)展，互聯(lián)網(wǎng)日漸成為輿情產(chǎn)生和傳播的主要場所。人們不再是被動地在網(wǎng)絡上查閱信息，而更多是在網(wǎng)絡上主動表達自己的觀點和看法，再加上網(wǎng)絡本身具有虛擬性、隱藏性、滲透性和隨意性等特點，使得網(wǎng)絡輿情的社會影響力越來越大，甚至會影響國家重大決策，因此，各國政府與軍隊都高度關注網(wǎng)絡輿情的研究。

目前，網(wǎng)絡輿情研究主要有兩種思路：一是利用搜索引擎、數(shù)據(jù)挖掘、模式識別等技術，設計出各種網(wǎng)絡輿情分析與預警系統(tǒng)，對熱點、焦點與敏感話題及時做出反應。在這些系統(tǒng)中，輿情分析引擎是核心技術，主要包括文本分類與聚類、主題發(fā)現(xiàn)與跟蹤、觀點傾向性識別、多文檔自動摘要等技術[1，2]；二是將網(wǎng)絡輿情傳播視為社會復雜系統(tǒng)，以CAS理論為基礎，借助基于Agent的計算機仿真建模方法，來模擬分析網(wǎng)絡上的輿論傳播過程[3]。其中，前者偏重文本的統(tǒng)計分析與挖掘，而后者強調通過復雜系統(tǒng)建模仿真來揭示網(wǎng)絡輿情的內(nèi)在機理和深層規(guī)律。

本文試圖集成上述兩種研究思路，分析復雜網(wǎng)絡拓撲特性，發(fā)現(xiàn)網(wǎng)絡輿情中的熱點話題及其演化趨勢。具體實現(xiàn)時，我們將引入物理場論思想，通過定義網(wǎng)絡節(jié)點的拓撲勢評估其重要性，通過節(jié)點的全局重要性排序實現(xiàn)網(wǎng)絡輿情研究中的熱點話題發(fā)現(xiàn)。

2 基本思想

復雜網(wǎng)絡是目前技術、生物、社會等各類復雜系統(tǒng)的抽象方法。研究表明，眾多真實復雜網(wǎng)絡具有某些共同的拓撲性質，如小世界、無尺度、模塊化與社區(qū)結構等。這些性質深刻揭示了真實網(wǎng)絡的異質性，即網(wǎng)絡中每個節(jié)點的重要程度是不同的。采用復雜網(wǎng)絡方法研究網(wǎng)絡輿情時，諸如怎樣度量話題的重要性，哪些話題更值得關注等問題，都可以歸結到復雜網(wǎng)絡研究中的基礎性問題：如何度量網(wǎng)絡節(jié)點的重要性。本文將從物理場論的思想出發(fā)研究網(wǎng)絡節(jié)點的重要性評估方法。

給定網(wǎng)絡G=（V，E），V={v1，…，vn}為節(jié)點的非空有限集，E?V×V為節(jié)點偶對或邊的集合且=m，將網(wǎng)絡G看作是一個包含n個節(jié)點及其相互作用的物理系統(tǒng)，每個節(jié)點周圍存在一個作用場，位于場中的任何節(jié)點都將受到其他節(jié)點的聯(lián)合作用，由此在整個網(wǎng)絡拓撲上確定了一個虛擬相互作用場。根據(jù)真實網(wǎng)絡的模塊化與抱團特性，可以認為，節(jié)點間相互作用具有局域特性，每個節(jié)點的影響能力會隨網(wǎng)絡距離的增長而快速衰減。根據(jù)數(shù)據(jù)場的相關討論[4]，我們傾向于采用代表短程場且具有良好數(shù)學性質的高斯勢函數(shù)描述節(jié)點間的相互作用，并稱相應的場為拓撲勢場。根據(jù)數(shù)據(jù)場的勢函數(shù)定義[4，5]，任一節(jié)點V的拓撲勢可表示為：

式（1）中，dij表示節(jié)點vi與vj間的網(wǎng)絡距離，本文采用最短路徑長度來度量；影響因子σ用于控制每個節(jié)點的影響范圍；mi≥0表示節(jié)點vi（i=1，…，n）的質量，可以用來描述每個節(jié)點的固有屬性。真實網(wǎng)絡中，節(jié)點的固有屬性具有豐富的物理含義，如城市交通網(wǎng)中城市的規(guī)模，人際關系網(wǎng)中個體的社會背景和活動能力，通信網(wǎng)絡中節(jié)點的存儲能力等。本文中，忽略節(jié)點固有屬性的差異性，假設每個節(jié)點的質量相等且滿足歸一化條件，由此得到簡化的拓撲勢公式：

根據(jù)式（2），對于給定的σ值，可以計算出每個節(jié)點的拓撲勢值，并根據(jù)勢值大小對節(jié)點進行全局重要性排序，由此得到基于拓撲勢的節(jié)點重要性評估方法。

其中影響因子σ是一個重要參數(shù)。根據(jù)數(shù)據(jù)場中關于影響因子σ的討論[4，5]，我們引入勢熵衡量σ值的合理性。給定網(wǎng)絡G=（V，E）及其對應某個σ值的拓撲勢場，令v1，…，vn的勢值為φ（v1），…，φ（vn），相應的勢熵可定義為：

3 基于拓撲勢的網(wǎng)絡節(jié)點重要性排序算法

基于拓撲勢的節(jié)點重要性排序算法包括兩個基本步驟：①影響因子σ的優(yōu)選；②根據(jù)估計所得的σ值，計算每個節(jié)點的拓撲勢，并按勢值從大到小的順序輸出節(jié)點。

算法：基于拓撲勢的節(jié)點排序算法（Potential Rank algorithm）

輸入：網(wǎng)絡G=（V，E），其中V={v1，…，vn}=m；

輸出：按拓撲勢從大到小的順序輸出每個節(jié)點及其拓撲勢；

（2）初始化節(jié)點的1跳鄰居集lhop_neighbors（vi，1），i=1，…，n；

（3）令l=1；

（4）While H≤min_H do

（6）根據(jù)極小勢熵對應的拓撲勢分布，按勢值從大到小的順序輸出節(jié)點。

分析算法的時間復雜度，步驟（1）、（2）的時間復雜度為O（m）；步驟（4）的時間復雜度[6]最好情況下為O（m+n3/γ），2＜γ＜3為一個常數(shù)，最壞情況下為O（n2）；步驟（5）的時間復雜度取決于迭代計算所有節(jié)點的勢熵的時間開銷。由于每個節(jié)點的勢熵計算只涉及該節(jié)點已知的l—1跳內(nèi)的鄰居數(shù)，時間復雜度為O（ns），s為迭代次數(shù)。算法總的時間復雜度為O（n2）～O（m+n（3/γ））。

4 維基百科的熱點條目發(fā)現(xiàn)

維基百科是由全球志愿者協(xié)作完成的免費百科全書。截至2009年11月，全球271種語言的獨立運作版本共突破1，400萬條條目，總編輯次數(shù)超越7億次。截至2009年11月，中文維基百科已擁有282，000條條目，幾乎涵蓋了法律、翻譯、計算機、運動等所有領域。鑒于計算機學科具有發(fā)展迅速、知識體系更新快等特點，這里將選取中文維基百科統(tǒng)計數(shù)據(jù)（http：//zh.wikipedia.org/zh—cn/）中2003—2009年計算機領域相關條目作為實驗數(shù)據(jù)，通過對其進行對條目引用關系網(wǎng)絡建模與拓撲分析，揭示計算機學科領域的熱點研究問題及其演化規(guī)律。

4.1 中文維基百科中的計算機領域條目引用關系網(wǎng)絡建模

維基百科中最基本的元素是條目，每個條目描述一個具有確定含義的概念或實體，如“計算機科學”、“人工智能”等。為了方便人們進行訪問和瀏覽，維基百科中的條目不僅可以按類別進行組織、索引，而且可以通過超鏈接互相引用。這里，我們將條目視為節(jié)點，條目間的超鏈接關系視為連接，由此可得到2003—2009年的中文維基百科計算機領域條目引用關系網(wǎng)絡，如圖1所示分別為2003、2005、2009年的計算機領域條目引用關系網(wǎng)絡。

圖1中可以看出，由于中文維基百科是2002年10月份成立的，2003年計算機領域條目引用關系網(wǎng)比較小，只有183個節(jié)點與914條邊，網(wǎng)絡中存在孤立節(jié)點，如“計算器”、“費馬大定理”等；2005年的條目引用關系網(wǎng)規(guī)模顯著增長，包含1，813個節(jié)點與12，550條邊；而到2009年底，網(wǎng)絡規(guī)模已達到2，805個節(jié)點與42，635條邊，新增條目節(jié)點反映了近年來計算機領域中新的研究方向，如“云計算”、“中國網(wǎng)絡審查”、“復雜性理論”等。

4.2 基于拓撲勢的熱點條目發(fā)現(xiàn)

采用拓撲勢方法對條目引用關系網(wǎng)進行節(jié)點重要性排序，可以得到不同年度的前10個拓撲勢值最大的熱點條目，見表1。從表1中可以發(fā)現(xiàn)，自2003年以來，計算機領域研究熱點已經(jīng)由早期的計算機組成原理、程序設計基礎等逐步演變?yōu)楦叩葮I(yè)務邏輯、應用于網(wǎng)頁和ASP程序制作的腳本語言（如Jscript、VBScript等）、具有平臺無關性與網(wǎng)絡透明性的軟件開發(fā)平臺.NET框架，以及使用最廣泛的網(wǎng)頁瀏覽器Internet Explorer等。此外，敏捷軟件開發(fā)（Agile software development）、快速應用開發(fā)（Rapid application development）等新的條目的拓撲勢值也名列前位，合理地反映了當前計算機領域的研究熱點問題及其主流發(fā)展方向。

表1 2003—2009年度前10個拓撲勢值最大的熱點條目

5 總 結

本文引入了物理場論思想，通過定義網(wǎng)絡節(jié)點的拓撲勢評估其重要性。以中文維基百科計算機領域的熱點條目發(fā)現(xiàn)為例，闡述了通過節(jié)點的全局重要性排序實現(xiàn)網(wǎng)絡輿情研究中的熱點話題發(fā)現(xiàn)。下一步的工作將通過條目或者話題關系網(wǎng)絡結構演化趨勢分析，來研究網(wǎng)絡輿情的熱點話題動態(tài)傳播規(guī)律。

1 黃曉斌.網(wǎng)絡信息挖掘[M].北京：電子工業(yè)出版社，2005.

2 戴媛，程學旗.面向網(wǎng)絡輿論分析的實用關鍵技術概述[J].信息網(wǎng)絡安全，2008，（6）：63—65.

3 劉常昱，胡曉峰，司光亞，等.輿論涌現(xiàn)模型研究[J].復雜系統(tǒng)與復雜性科學，2007，4（1）：22—27.

4 淦文燕.聚類—數(shù)據(jù)挖掘中的基礎問題研究[D].南京：解放軍理工大學，2003.

5 淦文燕，李德毅，王建民.一種基于數(shù)據(jù)場的層次聚類方法[J].電子學報，2006，34（2）：258—262.

6 淦文燕，赫南，李德毅，等.一種基于拓撲勢的網(wǎng)絡社區(qū)發(fā)現(xiàn)方法[J].軟件學報，2009，20（8）：2241—2254.