基于鄰層傳播的相對(duì)重要節(jié)點(diǎn)挖掘方法

趙 娜，李 杰，王 劍，彭西陽(yáng)，景 銘，聶永杰，郁 湧*

(1. 云南大學(xué)軟件學(xué)院 昆明 650091；2. 云南大學(xué)云南省軟件工程重點(diǎn)實(shí)驗(yàn)室 昆明 650091；3. 云南電網(wǎng)有限責(zé)任公司電力科學(xué)研究院 昆明 650217；4. 昆明理工大學(xué)信息工程及自動(dòng)化學(xué)院 昆明 650504)

分析復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)重要性，是一個(gè)被廣泛關(guān)注且具有重要意義的研究方向。目前，節(jié)點(diǎn)重要性的研究方法主要是針對(duì)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)做全局排序，以判斷節(jié)點(diǎn)重要性[1-3]。然而，“相對(duì)于一個(gè)或一組特定的節(jié)點(diǎn)，網(wǎng)絡(luò)中哪些節(jié)點(diǎn)是最重要的?”這類(lèi)問(wèn)題顯示了節(jié)點(diǎn)的相對(duì)重要性、局部重要性同樣具有較強(qiáng)的現(xiàn)實(shí)意義，尤其是當(dāng)網(wǎng)絡(luò)的規(guī)模非常大的時(shí)候。解決這類(lèi)問(wèn)題的一種典型辦法就是先量化一個(gè)節(jié)點(diǎn)相對(duì)于一個(gè)已知重要節(jié)點(diǎn)的重要性(稱(chēng)為相對(duì)重要性，有時(shí)也稱(chēng)為接近性或者相似性)，再計(jì)算一個(gè)節(jié)點(diǎn)相對(duì)已知的重要節(jié)點(diǎn)集的重要性，從而找到相對(duì)重要節(jié)點(diǎn)，即相對(duì)重要節(jié)點(diǎn)挖掘[4]。如在罪犯關(guān)系網(wǎng)絡(luò)中，通過(guò)已知罪犯查找其余罪犯[5-7]；在蛋白質(zhì)網(wǎng)絡(luò)中，通過(guò)已知致病基因查找未知致病基因[8]，或通過(guò)已知染病節(jié)點(diǎn)查找或預(yù)測(cè)風(fēng)險(xiǎn)節(jié)點(diǎn)[9]；在傳染病網(wǎng)絡(luò)中，可針對(duì)已知感染人員，優(yōu)先找出易感人群進(jìn)行治療、隔離，有效防止病毒的傳播和擴(kuò)散；在電力網(wǎng)絡(luò)中，通過(guò)已知重要斷路器或發(fā)電單元找出相對(duì)重要的斷路器、發(fā)電單元等進(jìn)行保護(hù)，可有效防止由相繼故障引起的大范圍停電?？梢?jiàn)，挖掘網(wǎng)絡(luò)中的相對(duì)重要節(jié)點(diǎn)具有重要的應(yīng)用價(jià)值。

1 相對(duì)重要節(jié)點(diǎn)挖掘算法研究現(xiàn)狀

相對(duì)重要節(jié)點(diǎn)挖掘的工作可以追溯到文獻(xiàn)[10]在2000 年提出的一種個(gè)性化的變種HITS 算法研究工作。其后，文獻(xiàn)[11-12]分別提出了個(gè)性化變種PageRank 算法，開(kāi)始更多地考慮網(wǎng)絡(luò)中節(jié)點(diǎn)的相對(duì)重要性。2003 年，文獻(xiàn)[13]定義了相對(duì)重要節(jié)點(diǎn)挖掘算法的通用框架，還明確提出了網(wǎng)絡(luò)中節(jié)點(diǎn)的相對(duì)重要性是相對(duì)于一個(gè)或一組指定的特定節(jié)點(diǎn)集的重要性。隨后相對(duì)重要節(jié)點(diǎn)的算法不斷被提出。文獻(xiàn)[14]提出了路徑概率求和的方法，該方法將節(jié)點(diǎn)s相對(duì)于最近鄰居節(jié)點(diǎn)s′的重要性定義為隨機(jī)游走過(guò)程中從節(jié)點(diǎn)s跳到節(jié)點(diǎn)s′的概率。文獻(xiàn)[15]提出集群粒子傳播法來(lái)評(píng)價(jià)節(jié)點(diǎn)的相對(duì)重要性。文獻(xiàn)[16]采用最短距離本身作為相對(duì)重要性衡量指標(biāo)，文獻(xiàn)[17]采用最短路徑距離的P范數(shù)的倒數(shù)作為相對(duì)重要性衡量指標(biāo)。文獻(xiàn)[18]在介數(shù)中心性的基礎(chǔ)上提出了信賴(lài)值的方法查找犯罪網(wǎng)絡(luò)中的其余罪犯。盡管相對(duì)重要性挖掘方法已有一些成果，但仍存在諸多問(wèn)題，如方法的效率和準(zhǔn)確性有待提高；在不同網(wǎng)絡(luò)上，方法的參數(shù)也需要明確如何選取等。

2 基于鄰層傳播的相對(duì)重要節(jié)點(diǎn)挖掘方法

在現(xiàn)實(shí)生活中，人類(lèi)遺傳病通常由多種致病基因(含未知和已知的基因)引起，由于它們導(dǎo)致相同或相似的疾病表型，因此未知的致病基因與已知的致病基因功能相關(guān)性越強(qiáng)，即某一基因與已知致病基因有越多的關(guān)聯(lián)，該基因?yàn)橹虏』虻母怕试酱骩19]。基于此思想，本文提出一個(gè)新的基于鄰層傳播(neighbor layout diffuse, NLD)的方法來(lái)挖掘相對(duì)重要節(jié)點(diǎn)，該算法的核心思想是：在網(wǎng)絡(luò)中，與已知重要節(jié)點(diǎn)連接越多的節(jié)點(diǎn)，該節(jié)點(diǎn)與已知重要節(jié)點(diǎn)具有的共同特征越多，其為已知重要節(jié)點(diǎn)的相對(duì)重要節(jié)點(diǎn)的概率越大。

2.1 問(wèn)題定義

對(duì)于由N個(gè)節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)G(V,E)，其中，N1個(gè) 節(jié)點(diǎn)構(gòu)成重要節(jié)點(diǎn)集V1，N2個(gè)節(jié)點(diǎn)構(gòu)成非重要節(jié)點(diǎn)集V2。 重要節(jié)點(diǎn)集V1=R∪U，其中R是已知重要節(jié)點(diǎn)集，U是未知重要節(jié)點(diǎn)集。

本文的工作是：基于已知重要節(jié)點(diǎn)集R，分析目標(biāo)節(jié)點(diǎn)集T=V-R中任意節(jié)點(diǎn)t相對(duì)于已知重要節(jié)點(diǎn)集R的重要性，最終找出目標(biāo)節(jié)點(diǎn)集T中top-k個(gè)相對(duì)重要節(jié)點(diǎn)，并對(duì)結(jié)果進(jìn)行AUC、準(zhǔn)確率和召回率分析。

2.2 NLD 算法中的分層

NLD 算法分為分層和傳播兩個(gè)步驟，傳播是在分層的基礎(chǔ)上進(jìn)行的。分層是將已知重要節(jié)點(diǎn)作為第一層，放入集合L1，將第一層節(jié)點(diǎn)的鄰居節(jié)點(diǎn)作為第二層，放入集合L2，將第二層節(jié)點(diǎn)的鄰居節(jié)點(diǎn)(不在第一層)作為第三層，放入集合L3，以此類(lèi)推，直到將所有節(jié)點(diǎn)進(jìn)行分層，得到分層結(jié)果Layer={L1,L2,···,Lm}。

2.3 NLD 算法的傳播

在上述分層過(guò)程完成后，算法進(jìn)入傳播步驟。NLD 算法的傳播采用相對(duì)重要性分?jǐn)?shù)值來(lái)量化節(jié)點(diǎn)重要性的傳播情況。分層后，只有第一層節(jié)點(diǎn)為已知重要節(jié)點(diǎn)，且相鄰兩層的節(jié)點(diǎn)間有鏈接。設(shè)第一層的相對(duì)重要性分?jǐn)?shù)值為1，其他節(jié)點(diǎn)的值為0。第一次傳播時(shí)，由于第二層節(jié)點(diǎn)與第一層節(jié)點(diǎn)有鏈接，因此將第一層節(jié)點(diǎn)的相對(duì)重要性分?jǐn)?shù)值通過(guò)鏈接傳給第二層，即將第一層節(jié)點(diǎn)的重要性傳給第二層，第二層任意節(jié)點(diǎn)與第一層節(jié)點(diǎn)聯(lián)系越多，被傳給的值就越多，即被傳給的重要性越大。第二次傳播時(shí)，把第二層節(jié)點(diǎn)作為傳播源，第二層節(jié)點(diǎn)通過(guò)鏈接會(huì)傳給相鄰的第三層，同時(shí)會(huì)回傳給相鄰的第一層，以此類(lèi)推。需要說(shuō)明的是回傳影響的僅是上一層，而下一層的節(jié)點(diǎn)值往往小于上一層的，所以回傳的值會(huì)更小，回傳不會(huì)影響整體的排序結(jié)果，并且能對(duì)上一層節(jié)點(diǎn)的相對(duì)重要性進(jìn)行區(qū)分。NLD 算法描述如下：令傳播輪數(shù)為S，初始時(shí)，S=0，令已知重要節(jié)點(diǎn)集R中任意節(jié)點(diǎn)r的相對(duì)重要性分?jǐn)?shù)值Zr(0)=1，目標(biāo)節(jié)點(diǎn)集T中的任意節(jié)點(diǎn)t的相對(duì)重要性分?jǐn)?shù)值Zt(0)=0。

第一輪傳播時(shí)，S=1，對(duì)于第一層中任意節(jié)點(diǎn)i，其相對(duì)重要性分?jǐn)?shù)Zi(0)≠0 ，將Zi(0)/k傳遞給鄰居，k為節(jié)點(diǎn)度數(shù)；第二輪傳播時(shí)，S=2，對(duì)于第二層中任意節(jié)點(diǎn)i，其相對(duì)重要性分?jǐn)?shù)Zi(1)≠0，將Zi(1)/k傳遞給鄰居，以此類(lèi)推，當(dāng)S=m-1 時(shí)，網(wǎng)絡(luò)中任意節(jié)點(diǎn)i的相對(duì)重要分?jǐn)?shù)Zi(S)≠0，停止傳播。對(duì)于任意節(jié)點(diǎn)i，相對(duì)重要性分?jǐn)?shù)值Zi(S)的公式表示如下：

傳播結(jié)束后，比較所有節(jié)點(diǎn)的相對(duì)重要性分?jǐn)?shù)值，相對(duì)重要性分?jǐn)?shù)值越大的越可能是相對(duì)重要節(jié)點(diǎn)。

2.4 方法示例

以圖1 所示的網(wǎng)絡(luò)為例，說(shuō)明鄰層傳播算法的計(jì)算過(guò)程。

圖1 示例網(wǎng)絡(luò)

把圖中節(jié)點(diǎn)按順序編號(hào)為[1, 2, 3, 4, 5, 6, 7, 8,9, 10]。設(shè)節(jié)點(diǎn)1 為已知重要節(jié)點(diǎn)。首先根據(jù)已知重要節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)進(jìn)行分層。節(jié)點(diǎn)1 屬于第一層，節(jié)點(diǎn)2, 3, 4 屬于第二層，節(jié)點(diǎn)5, 6, 7, 8 屬于第三層，節(jié)點(diǎn)9, 10 屬于第四層。

初始時(shí)，根據(jù)節(jié)點(diǎn)編號(hào)順序，節(jié)點(diǎn)對(duì)應(yīng)的相對(duì)重要性分?jǐn)?shù)值為[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]。經(jīng)過(guò)第一輪傳播后，各節(jié)點(diǎn)對(duì)應(yīng)的相對(duì)重要性分?jǐn)?shù)值為[1, 0.333 3, 0.333 3, 0.333 3, 0, 0, 0, 0, 0, 0]。

經(jīng)過(guò)第二輪傳播后，各節(jié)點(diǎn)對(duì)應(yīng)的相對(duì)重要性分?jǐn)?shù)值為[1.388 9, 0.333 3, 0.333 3, 0.333 3, 0.277 8,0.111 1, 0.111 1, 0.111 1, 0, 0]。

經(jīng)過(guò)第三輪傳播后，各節(jié)點(diǎn)對(duì)應(yīng)的相對(duì)重要性分 數(shù) 值 為[1.388 9, 0.463 0, 0.425 9, 0.5, 0.277 8,0.166 7, 0.148 1, 0.111 1, 0.037 0, 0.092 6]。

此時(shí)，所有節(jié)點(diǎn)都有了相對(duì)重要性分?jǐn)?shù)值，傳播結(jié)束。然后，根據(jù)相對(duì)重要性分?jǐn)?shù)值對(duì)節(jié)點(diǎn)進(jìn)行排序。從示例網(wǎng)絡(luò)的計(jì)算結(jié)果可得，對(duì)于節(jié)點(diǎn)1，相對(duì)重要節(jié)點(diǎn)可能性的順序應(yīng)為4, 2, 3, 5, 6, 7, 8,10, 9。

3 實(shí) 驗(yàn)

3.1 數(shù)據(jù)集

實(shí)驗(yàn)采用了4 個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集，忽略網(wǎng)絡(luò)連邊的權(quán)重與方向，分別是：

1) 國(guó)際航空網(wǎng)絡(luò)[20]，節(jié)點(diǎn)為國(guó)家，邊代表兩個(gè)國(guó)家有航線(xiàn)，SARS 病毒爆發(fā)早期傳播到的國(guó)家為重要節(jié)點(diǎn)集。

2) 人類(lèi)蛋白質(zhì)相互作用網(wǎng)絡(luò)PPI[21]，節(jié)點(diǎn)代表蛋白質(zhì)，邊代表蛋白質(zhì)之間存在相互作用，重要節(jié)點(diǎn)集是心臟病基因翻譯的蛋白質(zhì)。

3) Human 人類(lèi)蛋白質(zhì)相互作用網(wǎng)絡(luò)[22]，節(jié)點(diǎn)代表人類(lèi)蛋白質(zhì)，邊代表蛋白質(zhì)之間存在相互作用，人類(lèi)蛋白激酶這類(lèi)蛋白質(zhì)為重要節(jié)點(diǎn)集。

4) Mouse 小鼠蛋白質(zhì)相互作用網(wǎng)絡(luò)[22]，節(jié)點(diǎn)代表小鼠蛋白質(zhì)，邊代表蛋白質(zhì)之間存在相互作用，小鼠蛋白激酶這類(lèi)蛋白質(zhì)為重要節(jié)點(diǎn)集。

以上網(wǎng)絡(luò)數(shù)據(jù)集的基本拓?fù)涮卣魅绫? 所示。

表1 網(wǎng)絡(luò)基本拓?fù)涮卣?/p>

其中N表示網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)，N′表示網(wǎng)絡(luò)中重要節(jié)點(diǎn)個(gè)數(shù)，M表示網(wǎng)絡(luò)的邊數(shù)，K表示網(wǎng)絡(luò)平均度，C表示網(wǎng)絡(luò)平均聚類(lèi)系數(shù)。

3.2 評(píng)價(jià)指標(biāo)

3.3 實(shí)證比較

圖2 網(wǎng)絡(luò)的AUC 結(jié)果

對(duì)比不同的算法可知，KSmar 的結(jié)果會(huì)把距離所有已知重要節(jié)點(diǎn)更近的節(jié)點(diǎn)的相對(duì)重要性分?jǐn)?shù)調(diào)高。通過(guò)Ksmar 的公式KS=[TP+T2P+····+TkP]也可看出，轉(zhuǎn)移概率矩陣會(huì)給k步內(nèi)已知重要節(jié)點(diǎn)所能到達(dá)的節(jié)點(diǎn)賦予重要分?jǐn)?shù)，k越小時(shí)，所獲得的相對(duì)重要分?jǐn)?shù)越高。PPR 是PageRank 的改進(jìn)方法，在無(wú)向圖中，對(duì)于度大的節(jié)點(diǎn)往往會(huì)獲得更多的相對(duì)重要性分?jǐn)?shù)。PHITS 是HITS 算法的改進(jìn)，在無(wú)向圖中，已知重要節(jié)點(diǎn)是權(quán)威節(jié)點(diǎn)也是中心節(jié)點(diǎn)，因此它往往給已知重要節(jié)點(diǎn)的鄰居更高的重要性分?jǐn)?shù)。NLD 則會(huì)給每層共同鄰居越多的節(jié)點(diǎn)更多的重要性分?jǐn)?shù)。在SARS 網(wǎng)絡(luò)中，SARS 爆發(fā)的國(guó)家與某個(gè)國(guó)家有越多的航班，該國(guó)家成為下一個(gè)爆發(fā)的國(guó)家的可能性更大，這符合NLD 的思想，因此NLD 在SARS 網(wǎng)絡(luò)上表現(xiàn)的較好。對(duì)于PPI網(wǎng)絡(luò)，某一基因與已知致病基因有越多的關(guān)聯(lián)，該基因?yàn)橹虏』虻母怕试酱骩19]，符合NLD 的思想，因此在PPI 網(wǎng)絡(luò)上表現(xiàn)也較好。

表2 不同的方法在4 個(gè)網(wǎng)絡(luò)的平均準(zhǔn)確率

表3 不同的方法在4 個(gè)網(wǎng)絡(luò)的平均召回率

從實(shí)驗(yàn)的數(shù)據(jù)集來(lái)看，總體而言，NLD 方法優(yōu)于其他方法，這說(shuō)明NLD 在相對(duì)重要節(jié)點(diǎn)挖掘方面具備準(zhǔn)確性與適用性。由于這些方法的優(yōu)劣一定程度上取決于網(wǎng)絡(luò)結(jié)構(gòu)本身，根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)確定研究方法這也是今后研究的一個(gè)問(wèn)題。

4 結(jié) 束 語(yǔ)

本文提出了一種挖掘相對(duì)重要節(jié)點(diǎn)的方法——NLD，該方法基于與越多已知重要節(jié)點(diǎn)關(guān)聯(lián)，其為相對(duì)重要節(jié)點(diǎn)的概率越大的假設(shè)。本文將NLD與已有的挖掘相對(duì)重要節(jié)點(diǎn)較好的方法KSmar、PPR、PHITS 進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果證明NLD 在一定程度優(yōu)于這些方法。同時(shí)，NLD 方法也為網(wǎng)絡(luò)信息挖掘提供了新思路。在今后的工作中仍然有很多問(wèn)題值得深入研究：1) 現(xiàn)有的各種度量網(wǎng)絡(luò)中節(jié)點(diǎn)相對(duì)重要性的指標(biāo)，比如路徑長(zhǎng)度的倒數(shù)、介數(shù)等，它們之間是否具有一定的聯(lián)系。2) 現(xiàn)實(shí)世界中雖然很多網(wǎng)絡(luò)都可以抽象為復(fù)雜網(wǎng)絡(luò)，但針對(duì)不同網(wǎng)絡(luò)設(shè)計(jì)其適用的挖掘算法仍是亟待研究的。

本文研究工作得到昆明市衛(wèi)健委項(xiàng)目(2020-09-04-112)的資助，在此表示感謝。