丁沂

摘要：當前網絡挖掘還處在一個不斷發(fā)展的階段，還未形成一個被大眾廣泛接受的研究框架，關于網絡挖掘的主要問題、研究方法、技術和應用相關的研究文獻也比較少。文章對網絡挖掘領域的研究問題以及未來的研究方向進行了探討。

關鍵詞：網絡；結構；數據挖掘

在過去的十幾年中，人們對現(xiàn)實世界中表現(xiàn)出的復雜的“連通性”表現(xiàn)出與日俱增的興趣，這種興趣的核心是網絡。網絡是現(xiàn)實事物之間相互關聯(lián)的一種模式，在很多場合人們都能發(fā)現(xiàn)網絡的存在。首先，人們身在其中的社會網絡，它體現(xiàn)了人與人之間的社交聯(lián)系。這種社交聯(lián)系的復雜性隨著人類歷史進程所發(fā)生的各種技術進步不斷增強，這些技術包括方便人們長途旅行的交通技術、網絡通信技術和無線互聯(lián)技術等。過去半個世紀以來，社會網絡在地理上的含義越來越弱化，但在其他方面卻變得越來越豐富。人們使用的信息也有類似的網絡結構，它們的復雜性也在不斷增加。大量信息源對少數高質量信息提供者支配信息生產的傳統(tǒng)局面形成了沖擊。在這樣的環(huán)境中要理解任何一條信息，不僅要看其內容本身，還要理解其引用其他信息的方式。社會的技術系統(tǒng)和經濟系統(tǒng)也日益依賴于復雜的網絡。這使得人們越來越難以推理它們的行為，對它們進行調整的風險也越來越大。網絡使人們的技術和經濟系統(tǒng)容易受到很大的影響，這種影響會通過網絡結構傳播開來，有時局部問題會導致全局的崩潰。在某些情況下，網絡研究的重點通常不在網絡結構本身，而在于它所帶來的另一種復雜性，即網絡作為一個大型的、由各種關聯(lián)成分構成的總體，以一種難以預知的方式，反作用于中央權威行動的復雜性。

在電子商務、市場營銷、知識管理、Web挖掘等眾多領域，人們在做決策的時候往往需要考慮各種類型的網絡。從20世紀90年代末開始，大量關于新的網絡模型、技術和應用的論文發(fā)表在《自然》《科學》以及很多高級別的學術期刊上。與此同時，F(xiàn)aceBook和MySpace等社交網絡站點也隨著這股潮流越來越流行，社會網絡數據挖掘，也可以簡稱為網絡挖掘受到越來越多研究者的關注。網絡數據挖掘和傳統(tǒng)的數據挖掘有著本質的區(qū)別，比如關聯(lián)規(guī)則挖掘旨在從單個數據對象中提取模式，而網絡挖掘是從Internet，WWW和社交網絡等網絡數據中提取不同對象之間的關系，即有價值的結構模式。

1網絡挖掘中的主要研究問題

網絡挖掘主要包括靜態(tài)結構挖掘和動態(tài)結構挖掘兩個方面：靜態(tài)結構挖掘關注網絡的一個快照，在某一個指定的時間點觀測到的節(jié)點和連邊；與靜態(tài)網絡挖掘相比，動態(tài)網絡挖掘基于多個不同時間點的網絡數據分析網絡。靜態(tài)分析關注某一個觀測時間點網絡節(jié)點和連邊配置的結構規(guī)則；動態(tài)分析旨在發(fā)現(xiàn)網絡隨時間變化的模式?？偠灾?，靜態(tài)分析的重點在網絡結構，動態(tài)分析的重點在于網絡演化的過程和機制。

1.1靜態(tài)結構挖掘

靜態(tài)網絡結構挖掘有3個主要的研究問題：（1）如何定位網絡中的重要資源？（2）如何降低網絡的復雜性并生成網絡的“最大圖像”？（3）如何從網絡中提取拓撲屬性？

1.1.1定位網絡資源

網絡可以看作是資源的集合，網絡中重要資源包括重要的節(jié)點、連邊以及網絡中的關鍵路徑。例如在WWW網絡中，Web文檔的內容就是WWW網絡中的重要資源，用戶在WWW網絡中搜索與他們需求匹配的高質量的Web頁面。網絡中的用戶、文檔、關系以及通信渠道對于一個網絡的功能至關重要。重要資源定位技術在網絡科學中得到廣泛的應用，例如：在Web上搜索高質量的頁面；在Internet上定位某些關鍵的電纜，這些電纜的故障會降低互聯(lián)網的健壯性；在協(xié)作網絡中發(fā)現(xiàn)解決某些特定問題的專家等等。

1.1.2降低網絡的復雜性

由于網絡由大量節(jié)點和連邊組成，因此網絡顯得非常復雜。隨著網絡規(guī)模的不斷擴大，理解網絡的結構也變得越發(fā)困難。例如：當一個市場管理者面臨著一個由成千上萬的消費者組成的網絡時將變得手足無措；一個研究者試圖理解一個不太熟悉學科中的引文網絡所包含的智能結構也是一件困難的事情。因此，研究者需要從復雜網絡中提取“最大圖像”，從而降低網絡的復雜性，并確保這個“最大圖像”與原來網絡具有一致的結構。為了達到這個目的，網絡首先被分割為若干子群，每個子群包含若干節(jié)點和連邊，從而提取子群之間的關系。網絡分隔技術在Web社區(qū)發(fā)現(xiàn)、引文網絡中的主題發(fā)現(xiàn)，犯罪網絡中的主要成員發(fā)現(xiàn)等領域也得到了廣泛的應用。

1.1.3提取網絡拓撲屬性

近年來，對大規(guī)模網絡的拓撲屬性的研究受到越來越多研究者的關注，很多因素導致了這種趨勢。首先，計算機不斷提高的計算能力讓大規(guī)模網絡數據的搜集和分析成為可能。例如，對Web網絡研究需要處理的節(jié)點多達上百萬。其次，近年來小世界和無標度網絡模型的流行也激勵了研究者去發(fā)現(xiàn)現(xiàn)實世界中存在的統(tǒng)一的組織原則。最后，F(xiàn)aceBook，MySpace等在線社會網絡站點的流行促使研究者去研究這種網絡現(xiàn)象。

靜態(tài)結構挖掘提供了一個發(fā)現(xiàn)網絡結構模式的方法，但是網絡不是靜態(tài)的而是不斷變化的，如何揭示網絡的動力學以及網絡的演化機制導所致的拓撲結構是動態(tài)結構挖掘領域的研究重點。

2動態(tài)網絡挖掘

回顧人類歷史的長河，任何一次傳染病的大規(guī)模流行，都是人類文明進程帶來的，反過來，每一次大規(guī)模的傳染病又對人類文明本身產生深遠的影響。人類社會的日益網絡化促進了現(xiàn)代公共衛(wèi)生體系的不斷完善，以努力減少疾病的威脅，但另一方面，這種網絡化進程使得人員和物資的流動日益頻繁和便捷，反過來加速了傳染病的快速擴散。在技術網絡領域，如果不加干預，整個Internet可以在幾十秒至幾十分鐘內因為計算機病毒的蔓延而完全崩潰。一次次嚴峻的考驗讓人們不得不重新考慮如下問題：在擁有發(fā)達醫(yī)療水平和生物技術的現(xiàn)代公共衛(wèi)生體系的今天，為什么新的病毒還能迅速蔓延？為什么在每年投入了巨額費用的防止病毒措施之后，Internet上計算機病毒的傳播仍然防不勝防？人們可以將生物種群和計算機網絡中的個體定義為節(jié)點，而將個體之間存在的關聯(lián)途徑定義為節(jié)點之間的邊。迅速發(fā)展的復雜網絡理論正有效地增進人們對爆發(fā)大規(guī)模生物和計算機病毒流行的傳染機制的認識。研究表明，當網絡規(guī)模無限增大時，無標度網絡的臨界值趨于零，即使是很微小的傳染病源也足以在龐大的網絡中蔓延。

網絡是在不斷變化的，新節(jié)點可能會加入系統(tǒng)，老節(jié)點可能會被移除。另外，新的連邊可能會出現(xiàn)在以前并不相連的兩個節(jié)點之間，節(jié)點之間原有的連邊可能在某個時刻崩潰。因此，理解網絡的演化機制和動力學至關重要。網絡的演化機制會導致某種類型的網絡拓撲結構的形成，從而直接影響系統(tǒng)的功能。動態(tài)網絡挖掘主要包含兩個研究問題：（1）如何描述網絡動力學；（2）如何對網絡建模以及預測網絡動力學。網絡動力學的描述方法通常相對簡單，通常都是利用在一段時間內觀測到的拓撲統(tǒng)計量的變化，例如網絡平均度和聚集系數的變化。

網絡結構動力學的建模和預測是一個極具挑戰(zhàn)性的問題。由于大多數網絡都呈現(xiàn)出無標度特征，當前大多數研究都關注在無標度網絡的演化過程。其中關鍵的問題是究竟什么機制導致了網絡中節(jié)點度的冪律分布。生長、偏好依附、競爭、獨立偏好等機制通常用來解釋大量真實網絡中無標度拓撲特征的形成。

3結語

網絡挖掘未來研究主要包括理論研究、技術研究和實證研究3個方面。在理論研究方面，隨著網絡結構挖掘研究的日益成熟，需要建立一個更加綜合的研究框架，新的研究問題、技術和發(fā)現(xiàn)可以融合到這個框架里面，例如，網絡中信息、創(chuàng)新和疾病的傳播都是非常具有前景的研究領域。另外在網絡演化研究方面，需要開發(fā)新的模型從而揭示網絡演化的機制，這些研究對網絡理論的建立極具價值。在技術研究方面，未來的研究將瞄準網絡結構模式挖掘新技術和新方法的開發(fā)。傳統(tǒng)的網絡分隔方法仍然缺乏有效性，這種方法從大規(guī)模網絡中提取子結構的能力是非常有限的。在實證研究領域，網絡結構挖掘在支持知識管理和決策應用方面的意義和影響仍然需要被驗證，大量實證研究也需要被用來驗證和解釋這些新的結構挖掘技術和方法。