[摘要]以網(wǎng)絡(luò)中心度計(jì)算方法為研究對(duì)象，首先歸納出網(wǎng)絡(luò)中心度的概括性定義。而后，從中心度算法研究、中心度算法分類(lèi)研究、中心度算法應(yīng)用研究等多個(gè)方面對(duì)該領(lǐng)域的國(guó)外主要研究發(fā)展情況進(jìn)行深入歸納、總結(jié)及分析。最后，對(duì)中心度算法的研究發(fā)展方向進(jìn)行展望。
　　[關(guān)鍵詞]中心度　網(wǎng)絡(luò)分析　中介中心度
　　[分類(lèi)號(hào)]G350
　　
　　中心度是應(yīng)用于網(wǎng)絡(luò)分析的一個(gè)重要度量指標(biāo)，用于測(cè)量網(wǎng)絡(luò)中“元素”的重要性，這里的“元素”是一種泛指，包括網(wǎng)絡(luò)中的節(jié)點(diǎn)、邊、社團(tuán)及整個(gè)網(wǎng)絡(luò)。本文的研究主要集中在節(jié)點(diǎn)中心度上。首先解釋并明確中心度的概念，回顧當(dāng)前的節(jié)點(diǎn)中心度的主要算法，對(duì)現(xiàn)有算法研究、分類(lèi)研究及應(yīng)用研究進(jìn)行總結(jié)和分析，最后對(duì)中心度算法研究情況予以總結(jié)及展望。
　　
　　1　中心度的概念
　　
　　中心度研究能夠識(shí)別網(wǎng)絡(luò)中的重要節(jié)點(diǎn)，節(jié)點(diǎn)的重要程度由網(wǎng)絡(luò)的拓?fù)鋵傩浴⒔Y(jié)構(gòu)特點(diǎn)及節(jié)點(diǎn)在網(wǎng)絡(luò)中的具體位置決定。Mike Gotta指出“中心度的概念，簡(jiǎn)單來(lái)說(shuō)是識(shí)別網(wǎng)絡(luò)中具有高度連接的活動(dòng)者”。這個(gè)定義有些片面，而維基百科中也沒(méi)有給出明確的定義，只給出了相關(guān)解釋?zhuān)骸霸趫D論和網(wǎng)絡(luò)分析中，對(duì)一個(gè)節(jié)點(diǎn)的多種中心度測(cè)量，這些測(cè)量主要是決定圖中一個(gè)節(jié)點(diǎn)的相對(duì)重要性”的一種解釋。
　　之前的研究中并沒(méi)有給出關(guān)于中心度的嚴(yán)格定義，筆者認(rèn)為它是關(guān)于節(jié)點(diǎn)重要性的度量指標(biāo)。這種重要性，根據(jù)不同網(wǎng)絡(luò)和結(jié)構(gòu)特點(diǎn)及關(guān)系表現(xiàn)為節(jié)點(diǎn)的影響力、權(quán)威性(重要思想、知識(shí)或判斷決策的源頭)、流行度、控制力(如傳輸、流量的控制能力)、便利性(位置上的優(yōu)勢(shì)、易于訪問(wèn))或某種特殊意義，也可以表現(xiàn)為節(jié)點(diǎn)的脆弱性和易受攻擊性。不同的中心度算法含義不同，此處給出的是一個(gè)總結(jié)性質(zhì)的定義。
　　
　　2　中心度算法分類(lèi)及研究進(jìn)展
　　
　　2.1　中心度算法分類(lèi)研究
　　已有不少學(xué)者對(duì)中心度算法的分類(lèi)進(jìn)行了研究。Noaht在描述中心度測(cè)量的理論基礎(chǔ)時(shí)將中心度劃分為三種類(lèi)型，包括總體效果中心度、接近效果中心度和調(diào)解中心度。Dirk Kosehtitzki等將中心度分為4種類(lèi)型，包括基于可到達(dá)性、基于流量、基于活力值和基于反饋的中心度。Zhang將中心度算法劃分為5類(lèi)，包括基于點(diǎn)度、基于最短路徑、基于流、基于隨機(jī)行走和基于反饋的中心度。從其他角度考慮中心度的劃分，還可以分為基于全局的中心度算法、基于局部的中心度算法；或根據(jù)具體算法分為絕對(duì)中心度和相對(duì)中心度算法；根據(jù)網(wǎng)絡(luò)動(dòng)態(tài)性，分為動(dòng)態(tài)中心度算法和靜態(tài)中心度算法。另外，根據(jù)網(wǎng)絡(luò)屬性、權(quán)重和方向又可以分為基于有向網(wǎng)絡(luò)的算法和基于無(wú)向網(wǎng)絡(luò)的算法、基于加權(quán)網(wǎng)絡(luò)和基于無(wú)權(quán)網(wǎng)絡(luò)的算法及幾者組合的分類(lèi)方式。
　　2.2　主要的中心度算法研究
　　根據(jù)2.1的分類(lèi)，本文基于生成原理將中心度算法分類(lèi)，劃分為基于連接的、基于最短路徑的、基于流的、基于隨機(jī)行走的和基于反饋的中心度算法5種。
　　2.2.1　基于連接的中心度算法度中心度算法(Degree)用于測(cè)度網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)直接連接數(shù)的總和。在有向網(wǎng)絡(luò)中，度又分為人度和出度。Hildrun基于合著網(wǎng)絡(luò)比較有權(quán)和無(wú)權(quán)的度中心度算法，提出查找一種函數(shù)，使元素權(quán)重均等分布數(shù)等于元素的個(gè)數(shù)。得到偏離相等分布越大、函數(shù)值越小的包含權(quán)重連接關(guān)系的復(fù)雜度中心度算法。Benjamin聚焦于在網(wǎng)絡(luò)規(guī)模、邊密度、邊強(qiáng)度和方向性等變量變化條件下的度中心度研究。由于度中心度算法反映的是靜態(tài)的局部聯(lián)系，在反映重要節(jié)點(diǎn)時(shí)具有局限性，研究中通常與其他網(wǎng)絡(luò)屬性測(cè)度指標(biāo)結(jié)合應(yīng)用。
　　2.2.2　基于最短路徑的中心度算法基于最短路徑的中心度算法包括接近中心度(CIoseness)、中介中心度(Betweenness)、Harmonic中心度、Eccentrality和Centroid等。這一類(lèi)中心度基于網(wǎng)絡(luò)中節(jié)點(diǎn)間的最短距離。Yannick對(duì)Harmonic中心度和接近中心度進(jìn)行比較，指出Harmonic中心度可以作為接近中心度的替代算法，并將其擴(kuò)展到無(wú)向圖當(dāng)中。Centroid也可看作是接近中心度的變種，它測(cè)量的是一個(gè)節(jié)點(diǎn)比其他節(jié)點(diǎn)在位置上的優(yōu)勢(shì)程度。中介中心度是基于最短路徑的經(jīng)典算法，能夠用于揭示網(wǎng)絡(luò)中具有連接橋作用的節(jié)點(diǎn)，從而發(fā)現(xiàn)網(wǎng)絡(luò)連接中的關(guān)鍵點(diǎn)或脆弱點(diǎn)。由于該算法的重要性，諸多學(xué)者關(guān)注該算法的研究，對(duì)其進(jìn)行改進(jìn)與優(yōu)化。其中，Ulrik Brandes較系統(tǒng)地總結(jié)了中介中心度的變種算法及其適用范圍。雖然基于最短路徑的算法是中心度測(cè)量的重要方法之一，但是基于最短路徑的原理也成為這類(lèi)算法的局限，在實(shí)際網(wǎng)絡(luò)中并不是所有重要節(jié)點(diǎn)都通過(guò)最短路徑。
　　2.2.3　基于流的中心度算法基于流的中心度算法引入電網(wǎng)電流流動(dòng)理論，將網(wǎng)絡(luò)關(guān)系看作是包含電壓、電流的電網(wǎng)，基于在網(wǎng)絡(luò)中電流的流動(dòng)進(jìn)行建模。主要包括基于流的中介中心度，基于流的接近中心度及信息中心度。這類(lèi)中心度算法主要被應(yīng)用于社會(huì)網(wǎng)絡(luò)，用于探測(cè)社團(tuán)結(jié)構(gòu)，如Franco提出通過(guò)計(jì)算圖中相關(guān)的局部流中介中心度，利用邊的權(quán)重建模進(jìn)行社團(tuán)的抽取及聚類(lèi)。
　　2.2.4　基于隨機(jī)行走的中心度算法基于隨機(jī)行走的中心度算法包括隨機(jī)行走中介中心度、隨機(jī)行走接近中心度和馬爾可夫中心度算法。這類(lèi)算法主要基于隨機(jī)行走原理，計(jì)算在起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)間對(duì)中間節(jié)點(diǎn)的隨機(jī)訪問(wèn)次數(shù)�；�于隨機(jī)行走的中介中心度算法是由Newman提出的，用于解決最短路徑的局限性問(wèn)題。S.Lee等提出基于偏好隨機(jī)行走的中心度算法，并將其應(yīng)用于復(fù)雜網(wǎng)絡(luò)，在度相當(dāng)大的條件下該算法能夠?qū)Χ喾N中心度算法進(jìn)行統(tǒng)一。
　　2.2.5　基于反饋的中心度算法基于反饋的中心度算法，包括Katzes status、HubbeH、Eigenvector及著名的PageRank、HITS等算法。
　　研究廣泛集中在PageRank等網(wǎng)絡(luò)排序算法上。由于其缺乏對(duì)網(wǎng)頁(yè)主題內(nèi)容等其他因素的考慮，不少學(xué)者對(duì)該算法進(jìn)行了改進(jìn)和擴(kuò)展。算法改進(jìn)注重綜合多方面影響因素，包括網(wǎng)頁(yè)鏈接、網(wǎng)頁(yè)內(nèi)容、用戶點(diǎn)擊及瀏覽行為等。目前較突出的研究如主題敏感的PageRank、個(gè)性化加權(quán)PageRank算法等能夠?qū)σ阎�查詢識(shí)別出更多相關(guān)度更高的網(wǎng)頁(yè)。
　　2.3　中心度近似算法研究
　　由于精確算法需要多次迭代，在時(shí)間和空間消耗上較大，特別是在真實(shí)大型網(wǎng)絡(luò)中，給實(shí)際計(jì)算帶來(lái)巨大挑戰(zhàn)。因此對(duì)近似算法的研究能夠在一定程度上解決這方面的問(wèn)題，近似算法研究關(guān)注在迭代次數(shù)、最短路徑計(jì)算、抽樣等方面的改進(jìn)，提高計(jì)算效率和性能。
　　David等提出一種基于適應(yīng)性抽樣技術(shù)的中介中心度近似算法，大大地降低了對(duì)高中心度節(jié)點(diǎn)的單源最短路徑計(jì)算的消耗。Kazuya等根據(jù)接近中心度的精確值和近似值計(jì)算提出新的算法。算法主要用于選取接近中心度值最高的節(jié)點(diǎn)，而非全部節(jié)點(diǎn)從而降低了時(shí)間消耗。近似算法能夠在一定程度上提高計(jì)算 效率并保證得到的結(jié)果在可接受的誤差之內(nèi)。
　　2.4　并行中心度算法研究
　　由于網(wǎng)絡(luò)、特別是真實(shí)網(wǎng)絡(luò)，更加復(fù)雜并且規(guī)模龐大，因此對(duì)于現(xiàn)有算法的性能和效率提出了挑戰(zhàn)。當(dāng)前的一些算法研究關(guān)注于在更精細(xì)粒度上的并行方法，對(duì)算法進(jìn)行切分和加和，分布到多臺(tái)機(jī)器上運(yùn)行，提高運(yùn)行效率的同時(shí)提高運(yùn)行效果。
　　Christian等提出一種新的并行模式的PageRank算法。該算法通過(guò)引入網(wǎng)絡(luò)二維視圖，保存主機(jī)ID作為區(qū)分，而后將PageRank劃分為不相連的部分，應(yīng)用GauB--Seidel迭代算法進(jìn)行快速的線性系統(tǒng)求解。該算法與其他并行PageRank算法相比，在每次迭代時(shí)間上有很大改進(jìn)。Tan等提出一種新的適用于CREWPRAM的并行中介中心度算法，應(yīng)用于大規(guī)模網(wǎng)絡(luò)分析，通過(guò)適當(dāng)?shù)臄?shù)據(jù)處理器映射、新的數(shù)邊策略和三元數(shù)據(jù)矩陣結(jié)構(gòu)，通過(guò)記錄最短路徑減少訪問(wèn)共享存儲(chǔ)器沖突問(wèn)題。
　　
　　3　中心度計(jì)算方法應(yīng)用研究
　　
　　雖然中心度計(jì)算方法主要被應(yīng)用于復(fù)雜網(wǎng)絡(luò)研究，但是由于它是基于網(wǎng)絡(luò)的，在其他領(lǐng)域研究中也受到廣泛關(guān)注。本文對(duì)其應(yīng)用領(lǐng)域進(jìn)行歸納，可主要體現(xiàn)在復(fù)雜網(wǎng)絡(luò)分析、期刊及論文評(píng)價(jià)、大眾標(biāo)注標(biāo)簽分析及推薦、網(wǎng)頁(yè)排名、關(guān)鍵詞抽取及文本摘要、語(yǔ)義結(jié)構(gòu)探測(cè)及語(yǔ)義消歧、科學(xué)前沿及創(chuàng)新探測(cè)、重要作者識(shí)別等方面。由于網(wǎng)頁(yè)排名主要涉及PageRank算法前文已經(jīng)總結(jié)，此處著重于歸納中心度算法在其他領(lǐng)域的研究情況。
　　3.1　復(fù)雜網(wǎng)絡(luò)分析
　　中心度算法主要被應(yīng)用于復(fù)雜網(wǎng)絡(luò)分析，如社會(huì)網(wǎng)絡(luò)、生物蛋白質(zhì)網(wǎng)絡(luò)、電力網(wǎng)絡(luò)等。Nicola等研究了復(fù)雜網(wǎng)絡(luò)中的中心度算法，回顧并比較了基于圖矩陣拓?fù)鋵傩缘闹行亩人惴�，包括PageRank、Eigenvector和HITS，發(fā)現(xiàn)一些中心度是相互關(guān)聯(lián)的。Francesco等將中心度的拓?fù)涓拍顟?yīng)用于解釋復(fù)雜網(wǎng)絡(luò)連接的可靠性和安全性，將度中心度、中介中心度、接近中心度、信息中心度拓展為可靠性度中心度、可靠性接近中心度等算法，將其應(yīng)用到電力傳輸系統(tǒng)網(wǎng)絡(luò)中，用于評(píng)估網(wǎng)絡(luò)路徑連接元素的重要性。
　　3.2　期刊及論文評(píng)價(jià)
　　隨著研究的深入，不少學(xué)者將中心度算法應(yīng)用于期刊引用網(wǎng)絡(luò)，為科學(xué)質(zhì)量評(píng)價(jià)提供新的方法。其中Jevin West提出一種新的學(xué)術(shù)期刊評(píng)價(jià)指標(biāo)Eigenfactor，它基于Eigenveetor，利用文獻(xiàn)對(duì)期刊的引用率對(duì)期刊進(jìn)行排序，其與傳統(tǒng)期刊評(píng)價(jià)指標(biāo)的區(qū)別在于其考慮了整個(gè)引用網(wǎng)絡(luò)的結(jié)構(gòu)，考慮了間接聯(lián)系及效果。Chena等應(yīng)用PageRank算法對(duì)1982年～2003年物理評(píng)論系列期刊中的所有出版物進(jìn)行了重要性評(píng)估。發(fā)現(xiàn)每個(gè)出版物的PageRank值和引用數(shù)相關(guān)。利用PageRank算法識(shí)別了期刊中物理學(xué)家熟悉的一些杰出的具有影響力的論文。
　　3.3　大眾標(biāo)注標(biāo)簽分析及推薦
　　大眾標(biāo)注是自Web2.0以來(lái)倍受學(xué)術(shù)界關(guān)注的一個(gè)領(lǐng)域，中心度算法在大眾標(biāo)注中的應(yīng)用研究主要體現(xiàn)在對(duì)標(biāo)簽的推薦和對(duì)標(biāo)注用戶的社會(huì)網(wǎng)絡(luò)分析等方面。主要通過(guò)用戶、資源、標(biāo)簽所構(gòu)成的三元組關(guān)系構(gòu)建不同的關(guān)系圖或關(guān)系網(wǎng)絡(luò)，并基于此進(jìn)行中心度的測(cè)量和評(píng)估，進(jìn)行對(duì)標(biāo)簽推薦或標(biāo)簽網(wǎng)絡(luò)規(guī)律特點(diǎn)的分析。
　　Andreas H根據(jù)大眾分類(lèi)法基于用戶、資源、標(biāo)簽三元組關(guān)系的特點(diǎn)，提出FolkRank算法，將其主要用于特殊主題的標(biāo)簽、資源或用戶的推薦。Robert等對(duì)FolkRank、基于改進(jìn)的PageRank及基于標(biāo)簽流行度的推薦方法進(jìn)行了測(cè)試對(duì)比，發(fā)現(xiàn)前兩種方法均比非個(gè)性化的推薦方法更有效，特別是FolkRank方法在探測(cè)超圖結(jié)構(gòu)、解決冷啟動(dòng)問(wèn)題上都有優(yōu)勢(shì)。Ivan基于共現(xiàn)圖使用節(jié)點(diǎn)中心度算法進(jìn)行社會(huì)標(biāo)簽推薦。通過(guò)關(guān)鍵詞集抽取，檢索相關(guān)書(shū)簽，構(gòu)建全局共現(xiàn)子圖，結(jié)合TF4DF算法計(jì)算相關(guān)標(biāo)簽的中心度，將具有最高中心度的標(biāo)簽作為推薦結(jié)果。
　　3.4　關(guān)鍵詞抽取及文本摘要
　　關(guān)鍵詞抽取和文本摘要也是中心度算法應(yīng)用的重要領(lǐng)域，其主要被應(yīng)用于測(cè)量文本中的詞或句子的中心度，確定關(guān)鍵詞或中心句，揭示文本的主題內(nèi)容。特別是在關(guān)鍵詞抽取研究中，中心度算法能夠規(guī)避對(duì)低頻但重要的詞的忽略問(wèn)題。
　　Kino使用Wikify系統(tǒng)從維基百科的文章中抽取關(guān)鍵詞，利用基于隨機(jī)沖浪的中心度算法進(jìn)行主題識(shí)別。Zhang等提出利用Hub，Authority框架進(jìn)行文本摘要的方法，結(jié)合線索短語(yǔ)、句子長(zhǎng)度、首句等線索，將子主題的屬性融入基于圖的句子排序算法中來(lái)探測(cè)多文本子主題。
　　3.5　語(yǔ)義結(jié)構(gòu)探測(cè)及語(yǔ)義消歧
　　時(shí)至今日，對(duì)于語(yǔ)義的探測(cè)和挖掘成為研究者關(guān)注的熱點(diǎn)，中心度在語(yǔ)義結(jié)構(gòu)探測(cè)和語(yǔ)義消歧方面也有主要應(yīng)用。Jason等提出通過(guò)語(yǔ)義結(jié)構(gòu)挖掘算法構(gòu)建一致性本體和計(jì)算局部和全局語(yǔ)義中心度的思想，用于增強(qiáng)子團(tuán)體的發(fā)現(xiàn)和資源的共享。
　　在語(yǔ)義消歧方面，Ravi應(yīng)用詞義相似度和中心度計(jì)算進(jìn)行基于圖的詞義消歧，并使用測(cè)試數(shù)據(jù)集對(duì)入度中心度、接近中心度、中介中心度等算法分別結(jié)合基于WordNet的不同相似度計(jì)算進(jìn)行了實(shí)驗(yàn)，取得較好的效果。
　　3.6　科學(xué)前沿及創(chuàng)新探測(cè)
　　中心度被應(yīng)用于引文網(wǎng)絡(luò)、共被引網(wǎng)絡(luò)測(cè)度具有重要影響力的論文，發(fā)現(xiàn)科學(xué)前沿和研究基礎(chǔ)。在引文網(wǎng)絡(luò)中，Chen提出在知識(shí)域中通過(guò)對(duì)標(biāo)志性節(jié)點(diǎn)、中心節(jié)點(diǎn)和拐點(diǎn)的發(fā)現(xiàn)，查找重要文獻(xiàn)的潛在特征。標(biāo)志性節(jié)點(diǎn)是網(wǎng)絡(luò)中具有特殊屬性的節(jié)點(diǎn)，如高被引文獻(xiàn)提供重要的標(biāo)志，這種節(jié)點(diǎn)具有較大的半徑。中心節(jié)點(diǎn)其節(jié)點(diǎn)度相對(duì)較高，在引文網(wǎng)絡(luò)中體現(xiàn)為共被引文獻(xiàn)，其具有重要智力貢獻(xiàn)。拐點(diǎn)是連接不同網(wǎng)絡(luò)的樞紐，是兩個(gè)子網(wǎng)絡(luò)共享的節(jié)點(diǎn)或子網(wǎng)絡(luò)交互路徑上的節(jié)點(diǎn)。Chen在其開(kāi)發(fā)的引文分析工具Citespace中利用中介中心度對(duì)引用網(wǎng)絡(luò)中科學(xué)發(fā)展中的拐點(diǎn)進(jìn)行識(shí)別。ShibataTM等通過(guò)被引次數(shù)和聚集中心度、中介中心度、接近中心度間的關(guān)系，探測(cè)作為基礎(chǔ)創(chuàng)新萌芽的論文及預(yù)測(cè)論文未來(lái)被引的能力。
　　3.7　重要作者識(shí)別
　　PageRank、中介中心度等算法也被用于論文合著網(wǎng)絡(luò)或作者引用網(wǎng)絡(luò)中，根據(jù)網(wǎng)絡(luò)屬性特點(diǎn)，作者在網(wǎng)絡(luò)中的貢獻(xiàn)，如合作或被引的鏈接數(shù)量，合作者之間、引用者與被引用者之間的相互關(guān)系測(cè)量作者在網(wǎng)絡(luò)中的影響力，對(duì)作者進(jìn)行排序，識(shí)別網(wǎng)絡(luò)中重要的、具有高度影響力及支持度的作者。Yan等將中心度算法作為一種影響力分析指標(biāo)，通過(guò)來(lái)自16個(gè)圖書(shū)情報(bào)期刊的1988年到2007年的數(shù)據(jù)生成合著者網(wǎng)絡(luò)，利用接近中心度、中介中心度、度中心度和PageRank四種算法對(duì)作者排序，分析了各種算法在作者影響力評(píng)估上的局限性。
　　
　　4　結(jié)語(yǔ)
　　
　　本文較系統(tǒng)地對(duì)現(xiàn)有網(wǎng)絡(luò)節(jié)點(diǎn)中心度計(jì)算方法研究及應(yīng)用情況進(jìn)行了總結(jié)和歸納，發(fā)現(xiàn)通過(guò)這些指標(biāo)的計(jì)算能對(duì)不同的網(wǎng)絡(luò)結(jié)構(gòu)和特性進(jìn)行揭示。就現(xiàn)有研究而言，由于中心度算法只是反映網(wǎng)絡(luò)屬性的一個(gè)方面，并且每種中心度算法都具有一定的適用范圍和局限性，因此當(dāng)前很多研究不僅考慮單一算法的運(yùn)用，更多的是注重多種算法的結(jié)合，并且特別關(guān)注于對(duì)網(wǎng)絡(luò)的動(dòng)態(tài)性變化和規(guī)模不斷增長(zhǎng)的情況的考慮，提出適于增量計(jì)算和具有高性能的改進(jìn)算法。在應(yīng)用研究中，除了在復(fù)雜網(wǎng)絡(luò)分析中的應(yīng)用，中心度算法在主題識(shí)別、語(yǔ)義探測(cè)等多個(gè)領(lǐng)域也都發(fā)揮了巨大潛力，并且有待于更深入的研究和拓展。由于不同網(wǎng)絡(luò)具有不同特點(diǎn)，因此，基于特定網(wǎng)絡(luò)特點(diǎn)的中心度算法研究將在未來(lái)得到更多的重視和關(guān)注。另外，在中心度算法的評(píng)估上研究者注意針對(duì)多種算法進(jìn)行測(cè)評(píng)、比較及對(duì)算法不足的分析，這是也保證算法有效性的必要手段。

相關(guān)熱詞搜索：網(wǎng)絡(luò)中心 計(jì)算方法 綜述 網(wǎng)絡(luò)中心度計(jì)算方法研究綜述 網(wǎng)絡(luò)語(yǔ)言研究綜述 網(wǎng)絡(luò)技術(shù)研究綜述