復雜網絡中重要性節點發掘綜述

摘 要：發現網絡的重要性一直是圖論領域的一個基本問題。隨著近年來復雜網絡研究的興起，特別是由許多實際網絡提取的復雜網絡，它們表現出與以往圖論不同的特征，如世界特征小，無標度特征。如何在復雜的網絡環境中發現重要節點已成為復雜網絡研究中的基本問題。本文簡要介紹了復雜網絡的基本概念，詳細總結、分析了在復雜網絡環境下幾個領域中發掘重要性節點的方法，最后提出了這一領域內幾個有待深入研究的問題和可能的應用方向。

關鍵詞：復雜網絡；重要節點

1.復雜網絡的概念

自然界中存在的大量復雜系統都可以通過形形色色的網絡加以描述，網絡由許多節點和連接節點之間的邊緣組成。其中，節點代表真實系統中的不同個體，而邊緣代表這些個體之間的連接。通常，當兩個節點之間存在某種關系時，連接一個邊緣，如果不存在，則邊緣連接的兩個節點在網絡中被視為相鄰。當數學研究網絡時，它只關心節點之間是否有任何連接邊緣。至于節點的位置和邊緣的形狀，沒有必要在意。近年來復雜網絡理論的研究越來越熱，也開創了很多其他的相關分支，但是一些基本問題仍然值得我們去深入地研究。可視化技術的應用，能夠定性地表示出小型網絡的層次化結構特征，可以直觀地顯示哪些節點是相連接的。同樣，網絡屬性的定量映射也是非常重要的，尤其是當網絡的規模和復雜性是非常大的，這是非常困難的分析用圖形表示的問題。在各種復雜的網絡，它是在復雜網絡研究的一個基本問題，以找出一個非常大規模的網絡，該網絡節點（邊緣）是最重要的，還是相對于其他節點或節點一個節點的重要性。

2.對社會網絡的分析法

社會網絡分析的研究在20世紀40年代末就開始了，其中各種主流的方法都有這樣一個假設，也就是說，節點的重要性等同于與其他節點的節點的連接，從而使指數的研究不破壞網絡的完整性（連接），一般不會考慮節點集的重要性。這些方法中的一個重要的基本思想是，在網絡中的不同節點之間重要性差由網絡在分析了一些有用的信息而獲得，如節點的度，最短路徑，節點的重量和邊緣。通過對這些基本屬性的統計、計算，能相對定量地反映出節點在網絡中的位置特性，將網絡節點的顯著性進行”放大”來定義節點的重要性。其中，已提出的發現重要節點的指標主要分為核心性和聲望兩大類，度量的方法主要包括節點的度、接近度、介數、信息、特征向量和累計提名等，現簡單介紹一下其中幾種常見的方法。將網絡中的節點按照其度的大小進行排序，可以一定程度上反映節點的重要性。節點的度值越高，則這個節點就越重要，這種方法比較的簡單且符合大眾心理，但是其缺點也同樣明顯，僅僅從節點度的大小并不能準確表達網絡中節點的重要程度。例如，一個節點的度值雖然很高，但是連接它的其他節點并不重要，則這個節點并不一定非常重要，反之，若一個節點的度值并不是非常高，但是連接它的節點多數都非常重要，則這個節點在網絡中可能是個非常重要的節點。例如有些名人的微博寫得并不是很好，像記流水賬，但是他們的微博在排行榜中卻名列前茅，這與他們擁有大量粉絲很有關系。

3.對系統科學的分析法

系統的科學研究方法是利用網絡的連通性來反映系統某些功能的完整性，并通過測量節點對網絡連接的破壞程度來反映網絡節點（集合）的重要性，也就是說，“破壞性等同于重要性，系統科學方法的主要研究成果是系統的”核與核“理論。系統的“核”定義為節點或節點的集合。在系統功能中具有重要或主導作用，并且如果被破壞則導致完全損失或重大損失，“核”的計算由點切集和連接分支的數量來定義。節點（集合）的重要性源于圖論中的點切集概念，即定義刪除節點（集合）后網絡連接損壞的重要性。對網絡連接的損害越大，由于維護網絡連接取決于它們的存在，因此刪除節點（集合）越重要。但該理論的主要目的是了解具有不同連通性的類似連接問題。另外，對于切點中每個節點的重要性，也不能給出明確的等級，不同點割集中節點的重要性也無法橫向比較，因為它們的刪除都會使系統不再連通。系統中節點（集）的刪除除了對系統連通性可能具有破壞，還會影響到系統的一些其他指標，也可以通過計算這些指標的性能變化來度量節點的重要性。類似地，他們也考慮了尋找最短路徑上k個最重要的節點的問題，并且給出了一個指數級復雜度的尋找算法。對于k=1的情況，需要O（mn+n2logn）的時間復雜度和O（m）的空間復雜度，其中m和n分別表示系統中邊和節點的數量。此外，國外的物理學家和數學家們也提出了一種基于最小生成樹的指標，即節點的重要性決定于該節點被刪除后系統中最小生成樹數量的變化情況，去掉節點以及相關聯的邊后，所得到的圖對應的生成樹數量越少，則表明該節點越重要。

4.對信息搜索領域的分析法

互聯網可以被看作是一個巨大的圖，其中節點代表網頁，（有向）邊代表網頁之間的超鏈接。在互聯網搜索領域，計算機科學家也提出了很多算法來判斷網頁節點的重要程度，其中近幾年來兩個最著名、最有代表性的算法是國外科學家Brin和Page在1998年提出的PageRank算法和Kleinberg在同一年提出的HITS算法。此后，互聯網的搜索領域也隨著Google的成功，越來越受到人們的關注，不斷有新的算法和變種提出。Lempel和Moran在2000年提出了SALSA算法，它是HITS算法的一個變種，考慮了用戶回退瀏覽不同頁面的情況。其他一些學者也相繼提出了另外的算法，如PHITS，Bayesian，Reputation等算法，這些算法實際上都顯式或隱式地對網頁節點的重要性進行了計算、排序，在實際的應用中極大地提高了檢索結果的質量，在發掘網絡節點上顯得尤為重要。

5.總結

本文介紹了在復雜網絡環境下，對復雜網絡中節點重要性發掘的幾個領域，并對其中重要的方法進行了討論和分析。主要集中在傳統的社會網絡、系統科學和源于互聯網的信息搜索等領域中的一些算法和思想，指出了其各自的優缺點。另外，相對于全局地評估節點的重要性方法，在最后也介紹了復雜網絡中節點的相對重要性分析。總的來說，社會網絡分析方法的核心思想是”重要性等價于顯著性”，對網絡中重要節點的發掘不以破壞網絡的整體性為基礎。分析網絡中節點的重要性，對于網絡的安全防護等應用具有非常重要的意義。特別是現實世界中很多網絡都具有復雜網絡的特性，如小世界、無尺度、冪律分布等特性，在復雜網絡的環境中，發掘網絡中節點的重要性顯得更加重要。

作者簡介：

錢宇鋒（1986.2--），男，漢族，湖北武漢人，講師，博士，主要從事復雜系統與復雜網絡，應用數學研究

（作者單位：湖北工業大學理學院）