王 敏,曹寶香,王 蕾,馮曉兵
(1.曲阜師范大學(xué)信息科學(xué)與工程學(xué)院,山東 日照276800;2.中國(guó)科學(xué)院計(jì)算技術(shù)研究所計(jì)算機(jī)體系結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室,北京100190)
復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵點(diǎn)發(fā)現(xiàn)在實(shí)際應(yīng)用中有著重要的意義。在復(fù)雜網(wǎng)絡(luò)中總有一些節(jié)點(diǎn)比較重要,例如網(wǎng)絡(luò)中的關(guān)鍵服務(wù)器、Web網(wǎng)絡(luò)中用戶最感興趣的網(wǎng)頁(yè),以及社交網(wǎng)絡(luò)中的意見領(lǐng)袖等,這些節(jié)點(diǎn)稱為網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)在實(shí)際應(yīng)用中有著深遠(yuǎn)意義,例如通過保護(hù)網(wǎng)絡(luò)中的關(guān)建服務(wù)器免受病毒或者黑客的攻擊可以防止網(wǎng)絡(luò)的癱瘓;搜索引擎可以根據(jù)用戶感興趣的網(wǎng)頁(yè)提供一系列網(wǎng)頁(yè);微博中普通用戶可以根據(jù)用戶在某個(gè)領(lǐng)域的影響力關(guān)注專家,獵頭公司也可以找到合適的人才等。介度中心(betweenness centrality)算法和PageRank算法是評(píng)判網(wǎng)絡(luò)節(jié)點(diǎn)重要程度時(shí)廣泛使用的關(guān)鍵點(diǎn)發(fā)現(xiàn)算法[1-2]。一般按照需求選擇合適的關(guān)鍵點(diǎn)發(fā)現(xiàn)算法。隨著社會(huì)的發(fā)展,網(wǎng)絡(luò)呈現(xiàn)出多元化的發(fā)展趨勢(shì),如何在特定應(yīng)用場(chǎng)景下選取合適的關(guān)鍵點(diǎn)發(fā)現(xiàn)算法成為目前要解決的重要問題,需要分析關(guān)鍵點(diǎn)發(fā)現(xiàn)算法的應(yīng)用場(chǎng)景。
本文在常用的7個(gè)類型網(wǎng)絡(luò)中選取16個(gè)真實(shí)數(shù)據(jù)集進(jìn)行測(cè)試,分析2種關(guān)鍵點(diǎn)集合的差異,確定算法的應(yīng)用場(chǎng)景。這7個(gè)網(wǎng)絡(luò)類型分別是社交網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、Web網(wǎng)絡(luò)、路徑網(wǎng)絡(luò)、P2P拓?fù)渚W(wǎng)絡(luò)、共作者網(wǎng)絡(luò)以及蛋白質(zhì)網(wǎng)絡(luò)。首先分別計(jì)算介度中心算法和PageRank算法在這16個(gè)真實(shí)數(shù)據(jù)集上得到的關(guān)鍵點(diǎn)集合。然后統(tǒng)計(jì)這2種關(guān)鍵點(diǎn)集合在網(wǎng)絡(luò)上的位置,根據(jù)它們的不同分布分析2種算法的應(yīng)用場(chǎng)景。
目前國(guó)內(nèi)外的相關(guān)工作主要集中在某個(gè)特定場(chǎng)景下分析關(guān)鍵點(diǎn)發(fā)現(xiàn)算法的關(guān)系,比較有代表性的是文獻(xiàn)[3]基于共作者網(wǎng)絡(luò)DBLP提出的合理衡量作者貢獻(xiàn)度的指標(biāo),文中指出PageRank值相對(duì)于其他指標(biāo),如度、介度中心等可以更合理地評(píng)價(jià)出每位作者的貢獻(xiàn)程度。由于在DBLP網(wǎng)絡(luò)中評(píng)價(jià)作者的貢獻(xiàn)度時(shí),一般根據(jù)他在本領(lǐng)域內(nèi)的影響力,需要使用PageRank算法,因此該結(jié)論與本文分析得到的結(jié)論一致。
介度中 心[4]定 義 為 BC(v)= ∑s,t∈V(σst(v)/σst),即經(jīng)過節(jié)點(diǎn)v的最短路徑個(gè)數(shù)所占的比例。節(jié)點(diǎn)的介度中心值越高表明該節(jié)點(diǎn)的關(guān)鍵路徑的條數(shù)越多,對(duì)其他節(jié)點(diǎn)的影響越大。PageRank算法[5]是Google公司提出的用來計(jì)算網(wǎng)頁(yè)相對(duì)于搜索引擎中其他網(wǎng)頁(yè)的重要程度,通過網(wǎng)絡(luò)的超鏈接關(guān)系來確定一個(gè)頁(yè)面的等級(jí),將對(duì)頁(yè)面的鏈接看成是投票,指示了網(wǎng)頁(yè)的重要性。這2種算法定義的不同在實(shí)際應(yīng)用中表現(xiàn)為關(guān)鍵點(diǎn)集合的不同,需要根據(jù)2種關(guān)鍵點(diǎn)集合來確定算法的應(yīng)用場(chǎng)景。
分析這2種關(guān)鍵點(diǎn)算法的應(yīng)用場(chǎng)景時(shí),首先,需要確定這2種關(guān)鍵點(diǎn)集合是不一致的。然后,根據(jù)2種關(guān)鍵點(diǎn)集合的差異分析算法的應(yīng)用場(chǎng)景。
Dolphins[6]是生活在新西蘭峽灣的62個(gè)海豚之間相互聯(lián)系的數(shù)據(jù)集。圖1是按照每個(gè)點(diǎn)的介度中心值畫出的圖(只大體畫了不同家族之間的聯(lián)系而且只標(biāo)示排名靠前的節(jié)點(diǎn)的ID),節(jié)點(diǎn)越大表明該節(jié)點(diǎn)的介度中心值越大,并且將生活在同一個(gè)家族的海豚畫在了一起。同樣,圖2是按照每個(gè)節(jié)點(diǎn)的PageRank值畫出的海豚圖。圖1、圖2表明,通過介度中心算法得到的關(guān)鍵點(diǎn)集合(top2)有{13,7}和通過PageRank算法得到的關(guān)鍵點(diǎn)集合top2有{2,8}是不相同的,介度中心值高的海豚13除了與本家族的海豚有聯(lián)系外還與其他家族的海豚有聯(lián)系,PageRank值最高的海豚2一般與本家族的海豚有聯(lián)系,與外部聯(lián)系相對(duì)較少。
從Dolphins的實(shí)例來看,PageRank值和介度中心值的不同體現(xiàn)在2種關(guān)鍵點(diǎn)集合所處的網(wǎng)絡(luò)位置上。介度中心值高的點(diǎn)處在社區(qū)邊緣,負(fù)責(zé)整個(gè)家族的聯(lián)系,對(duì)整個(gè)網(wǎng)絡(luò)的影響較大。PageRank值較高的點(diǎn)一般不與其他社區(qū)聯(lián)系,是社區(qū)內(nèi)部被熟知的節(jié)點(diǎn)。這2種關(guān)鍵點(diǎn)的關(guān)系類似于某公司中部門的領(lǐng)導(dǎo)(介度中心值高)與秘書(PageRank值高)。因此,可以從在社區(qū)的分布上來分析PageRank算法和介度中心算法的應(yīng)用場(chǎng)景。
為了比較實(shí)際應(yīng)用中高介度中心值的節(jié)點(diǎn)集合bc_topk與高PageRank值的節(jié)點(diǎn)集合pagerank_topk的差異,采用了2種評(píng)價(jià)指標(biāo),分別是topk逆序?qū)Γ?]和topk集合覆蓋率[7]。
為了保證制劑價(jià)格的平穩(wěn)過渡及患者可接受性,公立醫(yī)院在制定制劑市場(chǎng)調(diào)節(jié)價(jià)格過程中,大多繼續(xù)堅(jiān)持彌補(bǔ)合理生產(chǎn)成本支出并獲得合理利潤(rùn)原則制定價(jià)格,主要有以下幾種做法:
(1)topk逆序?qū)?/p>
一個(gè)逆序?qū)Φ亩x為:{(u,v)|rankbc(u)>rankpagerank(v)and rankbc(v)<rankpagerank(u)},表示介度中心值排名前k個(gè)點(diǎn)相對(duì)于PageRank值的排名變化情況。bc_topk的逆序?qū)?shù)越多表明介度中心值高的前k個(gè)點(diǎn)與pagerank值高的前k個(gè)點(diǎn)的差別越大。
(2)topk集合覆蓋率
假設(shè)x為bc_topk與pagerank_topk相交的元素的個(gè)數(shù),那么bc_topk或者pagerank_topk的集合覆蓋率表示為(x/k)×100%,集合覆蓋率越高表明2種關(guān)鍵點(diǎn)集合相同的節(jié)點(diǎn)數(shù)越高,topk集合覆蓋率可以結(jié)合topk逆序?qū)餐治?種關(guān)鍵點(diǎn)集合的差異。
表1是介度中心值較高的前10個(gè)海豚對(duì)應(yīng)的PageRank值的排名以及PageRank值高的前10個(gè)海豚所對(duì)應(yīng)的介度中心值的排名。表2分別統(tǒng)計(jì)了dolphins網(wǎng)絡(luò)中介度中心值高的top1,top5,top10相對(duì)于PageRank值排名逆序?qū)图细采w率情況,介度中心值最高的節(jié)點(diǎn)PageRank值的排名為16,是由于節(jié)點(diǎn)13的介度中心值排名為1,而PageRank值排名為17,變化數(shù)為16。bc_top5的逆序?qū)?shù)達(dá)到了68,集合覆蓋率只有20%,說明PageRank算法得到的關(guān)鍵點(diǎn)集合和介度中心算法得到的關(guān)鍵點(diǎn)集合相差較大。
表1 介度中心值排名與PageRank值排名的對(duì)應(yīng)關(guān)系
表2 topk相對(duì)于PageRank值排名的逆序?qū)案采w率1
Dolphins的實(shí)例表明,PageRank值和介度中心值的差異可以體現(xiàn)在所在的不同網(wǎng)絡(luò)位置上,可以根據(jù)2種關(guān)鍵點(diǎn)集合在網(wǎng)絡(luò)中的不同位置確定其應(yīng)用場(chǎng)景。在復(fù)雜網(wǎng)絡(luò)分析時(shí),常用的一個(gè)概念就是社區(qū),可以根據(jù)2種關(guān)鍵點(diǎn)在社區(qū)分布上的不同來分析其應(yīng)用場(chǎng)景,為了區(qū)分所在社區(qū)的不同位置,引入社區(qū)親和度的概念,用公式描述為:
其中,Ai表示節(jié)點(diǎn)u連接到社區(qū)i的邊數(shù);Ei表示節(jié)點(diǎn)u連接到其他社區(qū)的邊數(shù);ku表示節(jié)點(diǎn)u的度,節(jié)點(diǎn)u連接的社區(qū)越多,而且與其他社區(qū)相連的邊越多,cross(u)的值越小,不與其他社區(qū)相連的點(diǎn)的cross值為1。
P(crossv)=(x/k)×100%
其中,x表示關(guān)鍵點(diǎn)集合中社區(qū)親和度小于v的點(diǎn)數(shù);k表示關(guān)鍵點(diǎn)集合;p(v)越大說明關(guān)鍵點(diǎn)集合的跨社區(qū)分布概率越大,集合的社區(qū)親和度越低。
表3是Dolphins中k分別取10,20,50時(shí)bc_topk和pagerank_topk的社區(qū)分布(crossv<0)情況,介度中心值高的節(jié)點(diǎn)跨社區(qū)分布概率要高于PageRank值高的節(jié)點(diǎn),是網(wǎng)絡(luò)中有重要影響力的點(diǎn),PageRank高的節(jié)點(diǎn)多與社區(qū)內(nèi)部的點(diǎn)聯(lián)系,因此在尋找海豚家族的領(lǐng)導(dǎo)者時(shí),可用介度中心算法,尋找家族的秘書時(shí)可用PageRank算法。
表3 2種關(guān)鍵點(diǎn)集合的跨社區(qū)分布概率 %
本文所采用的實(shí)驗(yàn)環(huán)境為Intel Xeon E5645的機(jī)器,Linux 2.6.32,GCC版本4.1.2,編譯優(yōu)化選項(xiàng)為-O3,單核執(zhí)行。表4是測(cè)試數(shù)據(jù)集,來自于實(shí)際應(yīng)用中的7個(gè)類型的網(wǎng)絡(luò)(社會(huì)網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、路徑網(wǎng)、P2P網(wǎng)絡(luò)、Web網(wǎng)、共作者網(wǎng)、蛋白質(zhì)網(wǎng))中的16個(gè)真實(shí)數(shù)據(jù)集。在這16個(gè)真實(shí)數(shù)據(jù)集上分析了2種算法的應(yīng)用場(chǎng)景。
表4 測(cè)試數(shù)據(jù)集
2種關(guān)鍵點(diǎn)集合是不一致的。按照不同圖中高介度中心值集合相對(duì)于高PageRank值集合的覆蓋率可以將測(cè)試數(shù)據(jù)集中的圖分成3類,第1類覆蓋率在60%以上;第2類覆蓋率低于60%,高于40%;第3類測(cè)試圖的覆蓋率幾乎為0。
表5是高介度中心值topk集合相對(duì)于PageRank值排名的變化,以及與PageRank值topk集合覆蓋率的實(shí)驗(yàn)結(jié)果,從每個(gè)圖的top100來看,逆序?qū)?shù)在10 000以上的圖占了75%,雖然第1類圖的覆蓋率較高,但是逆序?qū)?shù)都達(dá)到了上萬(wàn),順序一致性較差,所以這2種關(guān)鍵點(diǎn)集合不是一致的。
表5 topk相對(duì)于PageRank值排名的逆序?qū)σ约案采w率2
分別統(tǒng)計(jì)了介度中心值高的點(diǎn)以及PageRank值高的點(diǎn)的社區(qū)分布情況(一般是社區(qū)親和度小于0的分布),如表6所示,介度中心值高的節(jié)點(diǎn)社區(qū)親和度較小,跨社區(qū)概率高于PageRank值高的點(diǎn)。
表6 2種關(guān)鍵點(diǎn)集合的跨社區(qū)分布概率 %
不同圖中高介度中心值與高PageRank值的覆蓋率的分類與社區(qū)分布情況相對(duì)應(yīng)。覆蓋率60%以上的圖中,2種關(guān)鍵點(diǎn)的社區(qū)分布情況相似,重合的點(diǎn)數(shù)較多;覆蓋率在40%~60%的圖中,介度中心值較高的點(diǎn)跨社區(qū)分布率多于PageRank值高的點(diǎn),2種集合的覆蓋率相對(duì)降低了一些;覆蓋率幾乎為0的測(cè)試圖中,介度中心值高的節(jié)點(diǎn)的社區(qū)分布完全不同于PageRank值高的節(jié)點(diǎn)的社區(qū)分布,兩者幾乎沒有重合的部分。
(1)覆蓋率在60%以上的測(cè)試圖
圖3是DouBan中不同關(guān)鍵點(diǎn)跨社區(qū)分布情況,2種關(guān)鍵點(diǎn)集合在社區(qū)分布上差異較小,2種關(guān)鍵點(diǎn)跨社區(qū)分布的概率都比較大,所以兩者之間會(huì)有很多相互重合的點(diǎn)。
圖3 DouBan網(wǎng)中2種關(guān)鍵點(diǎn)集合的跨社區(qū)分布概率
(2)覆蓋率在40%~60%之間的測(cè)試圖
圖4是Wiki-Vote中不同關(guān)鍵點(diǎn)跨社區(qū)分布情況,top20覆蓋率較高,2種關(guān)鍵點(diǎn)集合的分布情況相似,隨著覆蓋率降低,高介度中心值點(diǎn)跨社區(qū)概率要高于高PageRank值的點(diǎn)。
圖4 Wiki-Vote網(wǎng)中2種關(guān)鍵點(diǎn)集合的跨社區(qū)分布概率
(3)覆蓋率幾乎為0的測(cè)試圖
USA-roadBAY中的PageRank值高的點(diǎn)一般都不跨社區(qū),而介度中心值高的點(diǎn)的跨社區(qū)概率要遠(yuǎn)高于PageRank值高的節(jié)點(diǎn),所以2種集合相同的點(diǎn)數(shù)比較少,如圖5所示。
圖5 路徑網(wǎng)中2種關(guān)鍵點(diǎn)集合的跨社區(qū)分布概率
介度中心算法的關(guān)鍵點(diǎn)分布在社區(qū)邊緣,連接其他社區(qū),對(duì)整個(gè)網(wǎng)絡(luò)影響較大,適用于尋找整個(gè)網(wǎng)絡(luò)重要節(jié)點(diǎn)的應(yīng)用場(chǎng)景;PageRank算法的關(guān)鍵點(diǎn)分布在社區(qū)內(nèi)部,是社區(qū)內(nèi)活躍度較高的點(diǎn),適用于尋找某領(lǐng)域或者部門中被廣泛熟知節(jié)點(diǎn)的應(yīng)用場(chǎng)景。表7總結(jié)了2種關(guān)鍵點(diǎn)集合在16個(gè)真實(shí)應(yīng)用中的含義。
表7 不同關(guān)鍵點(diǎn)在測(cè)試數(shù)據(jù)中的含義
例如在DBLP中,在評(píng)價(jià)每位作者的貢獻(xiàn)度時(shí)需要根據(jù)作者在研究領(lǐng)域內(nèi)發(fā)表的文章數(shù)量和質(zhì)量,而不是根據(jù)是否跨領(lǐng)域研究,在某一研究領(lǐng)域內(nèi)有突出貢獻(xiàn)的作者也可能在其他研究領(lǐng)域也有貢獻(xiàn),這就是在DBLP中2種關(guān)鍵點(diǎn)集合相同率較高的原因。因此,在評(píng)價(jià)作者貢獻(xiàn)度的應(yīng)用場(chǎng)景下就要用PageRank算法,這與文獻(xiàn)[5]在該應(yīng)用場(chǎng)景下得到的結(jié)論一致。
為了在實(shí)際應(yīng)用中選擇合適的關(guān)鍵點(diǎn)發(fā)現(xiàn)算法,本文通過分析介度中心算法和PageRank算法得到的關(guān)鍵點(diǎn)集合在網(wǎng)絡(luò)位置上的差異,得出這2種算法各自適用的應(yīng)用場(chǎng)景。在尋找對(duì)整個(gè)網(wǎng)絡(luò)影響力較大的關(guān)鍵點(diǎn)時(shí)需要使用介度中心算法,在尋找某個(gè)領(lǐng)域內(nèi)熟知度較高的關(guān)鍵點(diǎn)時(shí)需要使用PageRank算法。隨著復(fù)雜網(wǎng)絡(luò)的發(fā)展,網(wǎng)絡(luò)的規(guī)模越來越大,算法的運(yùn)行時(shí)間也較長(zhǎng)。因此,下一步工作將從并行[21-22]和 近 似 等[23-25]角 度,研 究 如 何 降 低算法的運(yùn)行時(shí)間。
[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]王 敏,王 蕾,馮曉兵,等.基于頂點(diǎn)加權(quán)的介度中心近似算法[C]//中國(guó)高性能計(jì)算學(xué)術(shù)年會(huì)論文集.廣州:[出版者不詳],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]涂登彪,譚光明,孫凝暉,無鎖同步的細(xì)粒度并行介度中心算法[J].軟件學(xué)報(bào),2011,22(5):986-995.
[22]平 宇,向 陽(yáng),張 波.基于 Mapreduce的并行PageRank算法的實(shí)現(xiàn)[J].計(jì)算機(jī)工程,2014,40(9):124-129.
[23]王鐘斐,王 彪.基于錨文本相似度的PageRank改進(jìn)算法[J].計(jì)算機(jī)工程,2010,36(24):258-260.
[24]王德廣,周志剛,梁 旭.PageRank算法的分析及其改進(jìn)[J].計(jì)算機(jī)工程,2010,36(17):291-293.
[25]姚 琳,劉 文.一種基于本體的PageRank算法的改進(jìn)策略[J].計(jì)算機(jī)工程,2009,35(6):50-51,54.