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

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