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

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

1 概述

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

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

2 相關(guān)工作

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

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

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

3 2種算法應(yīng)用場景的分析方法

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

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

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

3．2 關(guān)鍵點集合一致性分析

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

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

（1）topk逆序?qū)?/p>

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

（2）topk集合覆蓋率

假設(shè)x為bc＿topk與pagerank＿topk相交的元素的個數(shù)，那么bc＿topk或者pagerank＿topk的集合覆蓋率表示為（x／k）×100%，集合覆蓋率越高表明2種關(guān)鍵點集合相同的節(jié)點數(shù)越高，topk集合覆蓋率可以結(jié)合topk逆序?qū)餐治?種關(guān)鍵點集合的差異。

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

表1 介度中心值排名與PageRank值排名的對應(yīng)關(guān)系

表2 topk相對于PageRank值排名的逆序?qū)案采w率1

3．3 關(guān)鍵點集合網(wǎng)絡(luò)位置分布差異分析

Dolphins的實例表明，PageRank值和介度中心值的差異可以體現(xiàn)在所在的不同網(wǎng)絡(luò)位置上，可以根據(jù)2種關(guān)鍵點集合在網(wǎng)絡(luò)中的不同位置確定其應(yīng)用場景。在復(fù)雜網(wǎng)絡(luò)分析時，常用的一個概念就是社區(qū)，可以根據(jù)2種關(guān)鍵點在社區(qū)分布上的不同來分析其應(yīng)用場景，為了區(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表示關(guān)鍵點集合中社區(qū)親和度小于v的點數(shù)；k表示關(guān)鍵點集合；p（v）越大說明關(guān)鍵點集合的跨社區(qū)分布概率越大，集合的社區(qū)親和度越低。

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

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

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

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

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

4 實驗過程與結(jié)果分析

4．1 關(guān)鍵點集合一致性實驗

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

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

表5 topk相對于PageRank值排名的逆序?qū)σ约案采w率2

4．2 關(guān)鍵點集合網(wǎng)絡(luò)位置分布差異實驗

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

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

4．3 實驗結(jié)果分析

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

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

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

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

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

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

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

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

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

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

5 算法應(yīng)用場景

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

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

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

6 結(jié)束語

為了在實際應(yīng)用中選擇合適的關(guān)鍵點發(fā)現(xiàn)算法，本文通過分析介度中心算法和PageRank算法得到的關(guān)鍵點集合在網(wǎng)絡(luò)位置上的差異，得出這2種算法各自適用的應(yīng)用場景。在尋找對整個網(wǎng)絡(luò)影響力較大的關(guān)鍵點時需要使用介度中心算法，在尋找某個領(lǐng)域內(nèi)熟知度較高的關(guān)鍵點時需要使用PageRank算法。隨著復(fù)雜網(wǎng)絡(luò)的發(fā)展，網(wǎng)絡(luò)的規(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］王 敏，王 蕾，馮曉兵，等．基于頂點加權(quán)的介度中心近似算法［C］／／中國高性能計算學(xué)術(shù)年會論文集．廣州：［出版者不詳］，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］．軟件學(xué)報，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．