介度中心和PageRank算法應用場景分析

王 敏，曹寶香，王 蕾，馮曉兵

（1．曲阜師范大學信息科學與工程學院，山東 日照276800；2．中國科學院計算技術研究所計算機體系結構國家重點實驗室，北京100190）

1 概述

復雜網絡中的關鍵點發(fā)現(xiàn)在實際應用中有著重要的意義。在復雜網絡中總有一些節(jié)點比較重要，例如網絡中的關鍵服務器、Web網絡中用戶最感興趣的網頁，以及社交網絡中的意見領袖等，這些節(jié)點稱為網絡中的關鍵節(jié)點。復雜網絡中的關鍵節(jié)點發(fā)現(xiàn)在實際應用中有著深遠意義，例如通過保護網絡中的關建服務器免受病毒或者黑客的攻擊可以防止網絡的癱瘓；搜索引擎可以根據(jù)用戶感興趣的網頁提供一系列網頁；微博中普通用戶可以根據(jù)用戶在某個領域的影響力關注專家，獵頭公司也可以找到合適的人才等。介度中心（betweenness centrality）算法和PageRank算法是評判網絡節(jié)點重要程度時廣泛使用的關鍵點發(fā)現(xiàn)算法［1－2］。一般按照需求選擇合適的關鍵點發(fā)現(xiàn)算法。隨著社會的發(fā)展，網絡呈現(xiàn)出多元化的發(fā)展趨勢，如何在特定應用場景下選取合適的關鍵點發(fā)現(xiàn)算法成為目前要解決的重要問題，需要分析關鍵點發(fā)現(xiàn)算法的應用場景。

本文在常用的7個類型網絡中選取16個真實數(shù)據(jù)集進行測試，分析2種關鍵點集合的差異，確定算法的應用場景。這7個網絡類型分別是社交網絡、通信網絡、Web網絡、路徑網絡、P2P拓撲網絡、共作者網絡以及蛋白質網絡。首先分別計算介度中心算法和PageRank算法在這16個真實數(shù)據(jù)集上得到的關鍵點集合。然后統(tǒng)計這2種關鍵點集合在網絡上的位置，根據(jù)它們的不同分布分析2種算法的應用場景。

2 相關工作

目前國內外的相關工作主要集中在某個特定場景下分析關鍵點發(fā)現(xiàn)算法的關系，比較有代表性的是文獻［3］基于共作者網絡DBLP提出的合理衡量作者貢獻度的指標，文中指出PageRank值相對于其他指標，如度、介度中心等可以更合理地評價出每位作者的貢獻程度。由于在DBLP網絡中評價作者的貢獻度時，一般根據(jù)他在本領域內的影響力，需要使用PageRank算法，因此該結論與本文分析得到的結論一致。

介度中 心［4］定 義 為 BC（v）＝ ∑s，t∈V（σst（v）／σst），即經過節(jié)點v的最短路徑個數(shù)所占的比例。節(jié)點的介度中心值越高表明該節(jié)點的關鍵路徑的條數(shù)越多，對其他節(jié)點的影響越大。PageRank算法［5］是Google公司提出的用來計算網頁相對于搜索引擎中其他網頁的重要程度，通過網絡的超鏈接關系來確定一個頁面的等級，將對頁面的鏈接看成是投票，指示了網頁的重要性。這2種算法定義的不同在實際應用中表現(xiàn)為關鍵點集合的不同，需要根據(jù)2種關鍵點集合來確定算法的應用場景。

分析這2種關鍵點算法的應用場景時，首先，需要確定這2種關鍵點集合是不一致的。然后，根據(jù)2種關鍵點集合的差異分析算法的應用場景。

3 2種算法應用場景的分析方法

3．1 社區(qū)分布分析

Dolphins［6］是生活在新西蘭峽灣的62個海豚之間相互聯(lián)系的數(shù)據(jù)集。圖1是按照每個點的介度中心值畫出的圖（只大體畫了不同家族之間的聯(lián)系而且只標示排名靠前的節(jié)點的ID），節(jié)點越大表明該節(jié)點的介度中心值越大，并且將生活在同一個家族的海豚畫在了一起。同樣，圖2是按照每個節(jié)點的PageRank值畫出的海豚圖。圖1、圖2表明，通過介度中心算法得到的關鍵點集合（top2）有｛13，7｝和通過PageRank算法得到的關鍵點集合top2有｛2，8｝是不相同的，介度中心值高的海豚13除了與本家族的海豚有聯(lián)系外還與其他家族的海豚有聯(lián)系，PageRank值最高的海豚2一般與本家族的海豚有聯(lián)系，與外部聯(lián)系相對較少。

從Dolphins的實例來看，PageRank值和介度中心值的不同體現(xiàn)在2種關鍵點集合所處的網絡位置上。介度中心值高的點處在社區(qū)邊緣，負責整個家族的聯(lián)系，對整個網絡的影響較大。PageRank值較高的點一般不與其他社區(qū)聯(lián)系，是社區(qū)內部被熟知的節(jié)點。這2種關鍵點的關系類似于某公司中部門的領導（介度中心值高）與秘書（PageRank值高）。因此，可以從在社區(qū)的分布上來分析PageRank算法和介度中心算法的應用場景。

3．2 關鍵點集合一致性分析

為了比較實際應用中高介度中心值的節(jié)點集合bc＿topk與高PageRank值的節(jié)點集合pagerank＿topk的差異，采用了2種評價指標，分別是topk逆序對［7］和topk集合覆蓋率［7］。

為了保證制劑價格的平穩(wěn)過渡及患者可接受性，公立醫(yī)院在制定制劑市場調節(jié)價格過程中，大多繼續(xù)堅持彌補合理生產成本支出并獲得合理利潤原則制定價格，主要有以下幾種做法：

（1）topk逆序對

一個逆序對的定義為：｛（u，v）｜rankbc（u）＞rankpagerank（v）and rankbc（v）＜rankpagerank（u）｝，表示介度中心值排名前k個點相對于PageRank值的排名變化情況。bc＿topk的逆序對數(shù)越多表明介度中心值高的前k個點與pagerank值高的前k個點的差別越大。

（2）topk集合覆蓋率

假設x為bc＿topk與pagerank＿topk相交的元素的個數(shù)，那么bc＿topk或者pagerank＿topk的集合覆蓋率表示為（x／k）×100%，集合覆蓋率越高表明2種關鍵點集合相同的節(jié)點數(shù)越高，topk集合覆蓋率可以結合topk逆序對共同分析2種關鍵點集合的差異。

表1是介度中心值較高的前10個海豚對應的PageRank值的排名以及PageRank值高的前10個海豚所對應的介度中心值的排名。表2分別統(tǒng)計了dolphins網絡中介度中心值高的top1，top5，top10相對于PageRank值排名逆序對和集合覆蓋率情況，介度中心值最高的節(jié)點PageRank值的排名為16，是由于節(jié)點13的介度中心值排名為1，而PageRank值排名為17，變化數(shù)為16。bc＿top5的逆序對數(shù)達到了68，集合覆蓋率只有20%，說明PageRank算法得到的關鍵點集合和介度中心算法得到的關鍵點集合相差較大。

表1 介度中心值排名與PageRank值排名的對應關系

表2 topk相對于PageRank值排名的逆序對及覆蓋率1

3．3 關鍵點集合網絡位置分布差異分析

Dolphins的實例表明，PageRank值和介度中心值的差異可以體現(xiàn)在所在的不同網絡位置上，可以根據(jù)2種關鍵點集合在網絡中的不同位置確定其應用場景。在復雜網絡分析時，常用的一個概念就是社區(qū)，可以根據(jù)2種關鍵點在社區(qū)分布上的不同來分析其應用場景，為了區(qū)分所在社區(qū)的不同位置，引入社區(qū)親和度的概念，用公式描述為：

其中，Ai表示節(jié)點u連接到社區(qū)i的邊數(shù)；Ei表示節(jié)點u連接到其他社區(qū)的邊數(shù)；ku表示節(jié)點u的度，節(jié)點u連接的社區(qū)越多，而且與其他社區(qū)相連的邊越多，cross（u）的值越小，不與其他社區(qū)相連的點的cross值為1。

P（crossv）＝（x／k）×100%

其中，x表示關鍵點集合中社區(qū)親和度小于v的點數(shù)；k表示關鍵點集合；p（v）越大說明關鍵點集合的跨社區(qū)分布概率越大，集合的社區(qū)親和度越低。

表3是Dolphins中k分別取10，20，50時bc＿topk和pagerank＿topk的社區(qū)分布（crossv＜0）情況，介度中心值高的節(jié)點跨社區(qū)分布概率要高于PageRank值高的節(jié)點，是網絡中有重要影響力的點，PageRank高的節(jié)點多與社區(qū)內部的點聯(lián)系，因此在尋找海豚家族的領導者時，可用介度中心算法，尋找家族的秘書時可用PageRank算法。

表3 2種關鍵點集合的跨社區(qū)分布概率 %

3．4 真實應用中的數(shù)據(jù)集

本文所采用的實驗環(huán)境為Intel Xeon E5645的機器，Linux 2．6．32，GCC版本4．1．2，編譯優(yōu)化選項為－O3，單核執(zhí)行。表4是測試數(shù)據(jù)集，來自于實際應用中的7個類型的網絡（社會網絡、通信網絡、路徑網、P2P網絡、Web網、共作者網、蛋白質網）中的16個真實數(shù)據(jù)集。在這16個真實數(shù)據(jù)集上分析了2種算法的應用場景。

表4 測試數(shù)據(jù)集

4 實驗過程與結果分析

4．1 關鍵點集合一致性實驗

2種關鍵點集合是不一致的。按照不同圖中高介度中心值集合相對于高PageRank值集合的覆蓋率可以將測試數(shù)據(jù)集中的圖分成3類，第1類覆蓋率在60%以上；第2類覆蓋率低于60%，高于40%；第3類測試圖的覆蓋率幾乎為0。

表5是高介度中心值topk集合相對于PageRank值排名的變化，以及與PageRank值topk集合覆蓋率的實驗結果，從每個圖的top100來看，逆序對數(shù)在10 000以上的圖占了75%，雖然第1類圖的覆蓋率較高，但是逆序對數(shù)都達到了上萬，順序一致性較差，所以這2種關鍵點集合不是一致的。

表5 topk相對于PageRank值排名的逆序對以及覆蓋率2

4．2 關鍵點集合網絡位置分布差異實驗

分別統(tǒng)計了介度中心值高的點以及PageRank值高的點的社區(qū)分布情況（一般是社區(qū)親和度小于0的分布），如表6所示，介度中心值高的節(jié)點社區(qū)親和度較小，跨社區(qū)概率高于PageRank值高的點。

表6 2種關鍵點集合的跨社區(qū)分布概率 %

4．3 實驗結果分析

不同圖中高介度中心值與高PageRank值的覆蓋率的分類與社區(qū)分布情況相對應。覆蓋率60%以上的圖中，2種關鍵點的社區(qū)分布情況相似，重合的點數(shù)較多；覆蓋率在40%～60%的圖中，介度中心值較高的點跨社區(qū)分布率多于PageRank值高的點，2種集合的覆蓋率相對降低了一些；覆蓋率幾乎為0的測試圖中，介度中心值高的節(jié)點的社區(qū)分布完全不同于PageRank值高的節(jié)點的社區(qū)分布，兩者幾乎沒有重合的部分。

（1）覆蓋率在60%以上的測試圖

圖3是DouBan中不同關鍵點跨社區(qū)分布情況，2種關鍵點集合在社區(qū)分布上差異較小，2種關鍵點跨社區(qū)分布的概率都比較大，所以兩者之間會有很多相互重合的點。

圖3 DouBan網中2種關鍵點集合的跨社區(qū)分布概率

（2）覆蓋率在40%～60%之間的測試圖

圖4是Wiki－Vote中不同關鍵點跨社區(qū)分布情況，top20覆蓋率較高，2種關鍵點集合的分布情況相似，隨著覆蓋率降低，高介度中心值點跨社區(qū)概率要高于高PageRank值的點。

圖4 Wiki－Vote網中2種關鍵點集合的跨社區(qū)分布概率

（3）覆蓋率幾乎為0的測試圖

USA－roadBAY中的PageRank值高的點一般都不跨社區(qū)，而介度中心值高的點的跨社區(qū)概率要遠高于PageRank值高的節(jié)點，所以2種集合相同的點數(shù)比較少，如圖5所示。

圖5 路徑網中2種關鍵點集合的跨社區(qū)分布概率

5 算法應用場景

介度中心算法的關鍵點分布在社區(qū)邊緣，連接其他社區(qū)，對整個網絡影響較大，適用于尋找整個網絡重要節(jié)點的應用場景；PageRank算法的關鍵點分布在社區(qū)內部，是社區(qū)內活躍度較高的點，適用于尋找某領域或者部門中被廣泛熟知節(jié)點的應用場景。表7總結了2種關鍵點集合在16個真實應用中的含義。

表7 不同關鍵點在測試數(shù)據(jù)中的含義

例如在DBLP中，在評價每位作者的貢獻度時需要根據(jù)作者在研究領域內發(fā)表的文章數(shù)量和質量，而不是根據(jù)是否跨領域研究，在某一研究領域內有突出貢獻的作者也可能在其他研究領域也有貢獻，這就是在DBLP中2種關鍵點集合相同率較高的原因。因此，在評價作者貢獻度的應用場景下就要用PageRank算法，這與文獻［5］在該應用場景下得到的結論一致。

6 結束語

為了在實際應用中選擇合適的關鍵點發(fā)現(xiàn)算法，本文通過分析介度中心算法和PageRank算法得到的關鍵點集合在網絡位置上的差異，得出這2種算法各自適用的應用場景。在尋找對整個網絡影響力較大的關鍵點時需要使用介度中心算法，在尋找某個領域內熟知度較高的關鍵點時需要使用PageRank算法。隨著復雜網絡的發(fā)展，網絡的規(guī)模越來越大，算法的運行時間也較長。因此，下一步工作將從并行［21－22］和 近 似 等［23－25］角 度，研 究 如 何 降 低算法的運行時間。

［1］Page L，Brin S，Motwani R．The PageRank Citation Ranking：Bringing Order to the Web［EB／OL］．（2001－10－30）．http：／／www－diglib．stanford．edu／diglib／pub．

［2］Brandes U．A Faster Algorithm for Betweenness Centrality［J］．Journal of Mathematical Sociology，2001，25（2）：163－177．

［3］Madduri K，Ediger D，Jiang K，et al．A Faster Parallel Algorithm and Efficient Multithreaded Implementations for Evaluating Betweenness Centrality on Massive Datasets［C］／／Proceedings of IEEE International Sym－posium on Parallel and Distributed Processing．Washington D．C．，USA：IEEE Press，2009：1－8．

［4］Haveliwala T．Efficient Computation of PageRank［EB／OL］．（2001－10－30）．http：／／www－diglib．stanford．edu／diglib／pub．

［5］Liu Xiaoming，Bollen J，Nelson M L，et al．Coauthorship Networks in the Digital Library Research Community ［J］． Information Processing ＆Management，2005，41（6）：1462－1480．

［6］Lusseau D，Schneider K，Boisseau O J．Learning to Discover Social Circles in Ego Networks［C］／／Proceedings of Conference on Neural Information Processing Systems．South Lake Tahoe，USA：［s．n．］，2012：548－556．

［7］王 敏，王 蕾，馮曉兵，等．基于頂點加權的介度中心近似算法［C］／／中國高性能計算學術年會論文集．廣州：［出版者不詳］，2014：160－170．

［8］Nelson D L，McEvoy C L，Schreiber T．A．The University of South Florida Word Association，Rhyme，and Word Fragment Norms［EB／OL］．（1999－12－30）．http：／／www．usf．edu／FreeAssociation．

［9］Tang Lei，Liu Huan．Relational Learning via Latent Social Dimensions［C］／／Proceedings of the 15th ACM SIGKDD Conference on Knowledge Discovery and Data Mining．New York，USA：ACM Press，2009：817－826．

［10］Lei Tang，Liu Huan．Scalable Learning of Collective Behavior Based on Sparse Social Dimensions［C］／／Proceedings of the 18th ACM Conference on Information and Knowledge Management．New York，USA：ACM Press，2009：1－33．

［11］Leskovec J， Kleinberg J， Faloutsos C． Graph Evolution：Densification and Shrinking Diameters［EB／OL］．（2007－07－28）．http：／／arxiv．org／abs／physics．

［12］Klimmt B，Yang Yiming．Introducing the Enron Corpus［C］／／Proceedings of the 1st Conference on Email and Anti－Spam．Mountain View，USA：［s．n．］，2004：1－2．

［13］Delling D，Holzer M，Müller K，et al．Highperformance Multi－level Graphs［J］／／Proceedings of the 9th Discrete Mathematics and Theoretical Computer Science Implementation Challenge Workshop on Shortest Paths．Piscataway，USA：［s．n．］，2006：709－736．

［14］Bast H，F(xiàn)unke S，Matijevic D．Transit——Ultrafast Shortest－path Queries with Linear－time Preprocessing［C］／／Proceedings of the 9th Discrete Mathematics and Theoretical Computer Science Implementation Challenge Workshop on Shortest Paths．Piscataway，USA：［s．n．］，2006：1－17．

［15］Ripeanu M，F(xiàn)oster I，Iamnitchi A．Mapping the Gnutella Network：Properties of Large－scale Peer－to－Peer Systems and Implications for System Design［J］．IEEE Internet Computing Journal，2002，6（1）：1－12．

［16］Leskovec J，Lang K，Dasgupta A，et al．Community Structure in Large Networks［EB／OL］．（2008－10－08）．http：／／arxiv．org／abs／0810．1355．

［17］Albert R，Jeong H，Barabasi A L．Diameter of the World－wide Web［EB／OL］．（1999－09－10）．http：／／arxiv．org／abs／cond－mat／9907038．

［18］Yang Jaewon，Leskovec J．Defining and Evaluating Network Communities Based on Ground－truth［C］／／Proceedings of the 12th International Conference on Data Mining．Washington D．C．，USA：IEEE Press，2012：1－10．

［19］Goh K I，Cusick M E，Valle D，et al．The Human Disease Network［EB／OL］．（2007－05－22）．http：／／www．pnas．org／cgi／doi／10．1073／pnas．0701361104．

［20］Sun Shiwei，Ling Lunjiang，Zhang Nan．Topological Structure Analysis of the Protein－protein Interaction Network in Budding Yeast ［J］．Nucleic Acids Research，2003，31（9）：2443－2450．

［21］涂登彪，譚光明，孫凝暉，無鎖同步的細粒度并行介度中心算法［J］．軟件學報，2011，22（5）：986－995．

［22］平 宇，向 陽，張 波．基于 Mapreduce的并行PageRank算法的實現(xiàn)［J］．計算機工程，2014，40（9）：124－129．

［23］王鐘斐，王 彪．基于錨文本相似度的PageRank改進算法［J］．計算機工程，2010，36（24）：258－260．

［24］王德廣，周志剛，梁 旭．PageRank算法的分析及其改進［J］．計算機工程，2010，36（17）：291－293．

［25］姚 琳，劉 文．一種基于本體的PageRank算法的改進策略［J］．計算機工程，2009，35（6）：50－51，54．