摘 要：發(fā)現(xiàn)網(wǎng)絡(luò)的重要性一直是圖論領(lǐng)域的一個(gè)基本問題。隨著近年來復(fù)雜網(wǎng)絡(luò)研究的興起，特別是由許多實(shí)際網(wǎng)絡(luò)提取的復(fù)雜網(wǎng)絡(luò)，它們表現(xiàn)出與以往圖論不同的特征，如世界特征小，無標(biāo)度特征。如何在復(fù)雜的網(wǎng)絡(luò)環(huán)境中發(fā)現(xiàn)重要節(jié)點(diǎn)已成為復(fù)雜網(wǎng)絡(luò)研究中的基本問題。本文簡要介紹了復(fù)雜網(wǎng)絡(luò)的基本概念，詳細(xì)總結(jié)、分析了在復(fù)雜網(wǎng)絡(luò)環(huán)境下幾個(gè)領(lǐng)域中發(fā)掘重要性節(jié)點(diǎn)的方法，最后提出了這一領(lǐng)域內(nèi)幾個(gè)有待深入研究的問題和可能的應(yīng)用方向。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；重要節(jié)點(diǎn)

1.復(fù)雜網(wǎng)絡(luò)的概念

自然界中存在的大量復(fù)雜系統(tǒng)都可以通過形形色色的網(wǎng)絡(luò)加以描述，網(wǎng)絡(luò)由許多節(jié)點(diǎn)和連接節(jié)點(diǎn)之間的邊緣組成。其中，節(jié)點(diǎn)代表真實(shí)系統(tǒng)中的不同個(gè)體，而邊緣代表這些個(gè)體之間的連接。通常，當(dāng)兩個(gè)節(jié)點(diǎn)之間存在某種關(guān)系時(shí)，連接一個(gè)邊緣，如果不存在，則邊緣連接的兩個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中被視為相鄰。當(dāng)數(shù)學(xué)研究網(wǎng)絡(luò)時(shí)，它只關(guān)心節(jié)點(diǎn)之間是否有任何連接邊緣。至于節(jié)點(diǎn)的位置和邊緣的形狀，沒有必要在意。近年來復(fù)雜網(wǎng)絡(luò)理論的研究越來越熱，也開創(chuàng)了很多其他的相關(guān)分支，但是一些基本問題仍然值得我們?nèi)ド钊氲匮芯俊？梢暬夹g(shù)的應(yīng)用，能夠定性地表示出小型網(wǎng)絡(luò)的層次化結(jié)構(gòu)特征，可以直觀地顯示哪些節(jié)點(diǎn)是相連接的。同樣，網(wǎng)絡(luò)屬性的定量映射也是非常重要的，尤其是當(dāng)網(wǎng)絡(luò)的規(guī)模和復(fù)雜性是非常大的，這是非常困難的分析用圖形表示的問題。在各種復(fù)雜的網(wǎng)絡(luò)，它是在復(fù)雜網(wǎng)絡(luò)研究的一個(gè)基本問題，以找出一個(gè)非常大規(guī)模的網(wǎng)絡(luò)，該網(wǎng)絡(luò)節(jié)點(diǎn)（邊緣）是最重要的，還是相對(duì)于其他節(jié)點(diǎn)或節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)的重要性。

2.對(duì)社會(huì)網(wǎng)絡(luò)的分析法

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

3.對(duì)系統(tǒng)科學(xué)的分析法

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

4.對(duì)信息搜索領(lǐng)域的分析法

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

5.總結(jié)

本文介紹了在復(fù)雜網(wǎng)絡(luò)環(huán)境下，對(duì)復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要性發(fā)掘的幾個(gè)領(lǐng)域，并對(duì)其中重要的方法進(jìn)行了討論和分析。主要集中在傳統(tǒng)的社會(huì)網(wǎng)絡(luò)、系統(tǒng)科學(xué)和源于互聯(lián)網(wǎng)的信息搜索等領(lǐng)域中的一些算法和思想，指出了其各自的優(yōu)缺點(diǎn)。另外，相對(duì)于全局地評(píng)估節(jié)點(diǎn)的重要性方法，在最后也介紹了復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的相對(duì)重要性分析?？偟膩碚f，社會(huì)網(wǎng)絡(luò)分析方法的核心思想是”重要性等價(jià)于顯著性”，對(duì)網(wǎng)絡(luò)中重要節(jié)點(diǎn)的發(fā)掘不以破壞網(wǎng)絡(luò)的整體性為基礎(chǔ)。分析網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性，對(duì)于網(wǎng)絡(luò)的安全防護(hù)等應(yīng)用具有非常重要的意義。特別是現(xiàn)實(shí)世界中很多網(wǎng)絡(luò)都具有復(fù)雜網(wǎng)絡(luò)的特性，如小世界、無尺度、冪律分布等特性，在復(fù)雜網(wǎng)絡(luò)的環(huán)境中，發(fā)掘網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性顯得更加重要。

作者簡介：

錢宇鋒（1986.2--），男，漢族，湖北武漢人，講師，博士，主要從事復(fù)雜系統(tǒng)與復(fù)雜網(wǎng)絡(luò)，應(yīng)用數(shù)學(xué)研究

（作者單位：湖北工業(yè)大學(xué)理學(xué)院）