基于K-shell的超網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法

周麗娜，李發(fā)旭，鞏云超，胡 楓

(青海師范大學(xué) a.計(jì)算機(jī)學(xué)院；b.青海省藏文信息處理與機(jī)器翻譯重點(diǎn)實(shí)驗(yàn)室；c.藏語智能信息處理及應(yīng)用國(guó)家重點(diǎn)實(shí)驗(yàn)室，西寧 810008)

0 引言

1 相關(guān)工作

1.1 超網(wǎng)絡(luò)相關(guān)概念

1.2 超網(wǎng)絡(luò)的拓?fù)渲笜?biāo)

1.3 K-shell算法

K-shell算法是圖算法中的一種經(jīng)典算法，用以計(jì)算每個(gè)節(jié)點(diǎn)的核數(shù)。該算法將網(wǎng)絡(luò)劃分為從核心到邊緣的不同層次，具體劃分過程為：首先,將網(wǎng)絡(luò)中度為1的節(jié)點(diǎn)及其連邊刪除；其次，刪除后網(wǎng)絡(luò)中將出現(xiàn)新的度為1的節(jié)點(diǎn)，繼續(xù)刪除新出現(xiàn)的度為1節(jié)點(diǎn)及其連邊；最后，重復(fù)上述操作直到網(wǎng)絡(luò)中不再新出現(xiàn)度為1的節(jié)點(diǎn)為止。此時(shí)所有被刪除的節(jié)點(diǎn)構(gòu)成第一層，即1-shell，節(jié)點(diǎn)的ks值為1。以此類推，進(jìn)一步得到更高的殼，直至網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都被賦予ks值。圖1為3-shell分解過程示例圖。

圖1 3-shell分解示例圖

2 基于超網(wǎng)絡(luò)的K-shell算法

2.1 K-shell算法在超網(wǎng)絡(luò)中的基本思想及分解過程

在超網(wǎng)絡(luò)中，節(jié)點(diǎn)超度表示包含該節(jié)點(diǎn)的超邊數(shù)，通常認(rèn)為超度大的節(jié)點(diǎn)重要性高，但超度僅是衡量節(jié)點(diǎn)重要性的局部性指標(biāo)，忽略了超網(wǎng)絡(luò)全局信息對(duì)節(jié)點(diǎn)重要性的影響。本文將基于復(fù)雜網(wǎng)絡(luò)位置思想的K-shell指標(biāo)擴(kuò)展到超網(wǎng)絡(luò)中，提出超網(wǎng)絡(luò)的K-shell分解算法。算法步驟為：1)刪除超網(wǎng)絡(luò)中超度為1的所有節(jié)點(diǎn)，刪除超度為1的節(jié)點(diǎn)后若網(wǎng)絡(luò)中存在超邊超度為1的超邊，則刪除此超邊；重復(fù)此過程，直到網(wǎng)絡(luò)中不存在超度為1的節(jié)點(diǎn)及超邊，所有被刪除的節(jié)點(diǎn)ks值為1；2)重復(fù)上述操作，刪除超網(wǎng)絡(luò)中所有超度值不大于2的節(jié)點(diǎn)和超度為1的超邊，此時(shí)，所有被刪除節(jié)點(diǎn)的ks值為2；3)以此類推，直到超網(wǎng)絡(luò)中所有節(jié)點(diǎn)都被賦予ks值。

如圖2所示超網(wǎng)絡(luò)的3-shell分解過程示意圖，圖2b～圖2d為1-shell、2-shell和3-shell分解圖。

圖2 超網(wǎng)絡(luò)的3-shell分解過程示例圖

圖2a為圖1a中添加超邊以后的超網(wǎng)絡(luò)圖，在圖1a中刪除ks值為1的節(jié)點(diǎn)后，其余節(jié)點(diǎn)的度值均大于1。繼續(xù)刪除度值為2的節(jié)點(diǎn)，即刪除節(jié)點(diǎn)5以及與它相連的兩條邊，則節(jié)點(diǎn)1與節(jié)點(diǎn)2的度值均變?yōu)?。與復(fù)雜網(wǎng)絡(luò)不同，如圖2a所示，刪除超網(wǎng)絡(luò)中節(jié)點(diǎn)7和節(jié)點(diǎn)8后，所在超邊的超度變?yōu)?，依據(jù)超網(wǎng)絡(luò)的K-shell算法刪除這條超邊。刪除節(jié)點(diǎn)9和節(jié)點(diǎn)10及其所在的超邊后，繼續(xù)刪除網(wǎng)絡(luò)中超度變?yōu)?的節(jié)點(diǎn)6，刪除該節(jié)點(diǎn)后，超邊的超度為2，因此保留該超邊。綜上所述，復(fù)雜網(wǎng)絡(luò)中刪除一個(gè)節(jié)點(diǎn)時(shí)與之相連的邊同時(shí)刪除；而超網(wǎng)絡(luò)中，只有當(dāng)超邊中只剩一個(gè)節(jié)點(diǎn)，即超邊超度為1時(shí)，才刪除此超邊。

分析圖2a中，超度最大的節(jié)點(diǎn)4、節(jié)點(diǎn)14，其超度值為5，由K-shell算法得到節(jié)點(diǎn)4的ks值為3，節(jié)點(diǎn)14的ks值為1。表明節(jié)點(diǎn)14位于網(wǎng)絡(luò)的邊緣位置，雖然超度值最大但并不是重要節(jié)點(diǎn)。因此，利用超度刻畫超網(wǎng)絡(luò)中的重要節(jié)點(diǎn)并不完全準(zhǔn)確。但由K-shell算法最終分解得到多個(gè)重要節(jié)點(diǎn)，導(dǎo)致節(jié)點(diǎn)的排序結(jié)果過于粗糙，如圖2d所示。為了解決此問題，本文進(jìn)行了改進(jìn)。

2.2 改進(jìn)的超網(wǎng)絡(luò)K-shell算法

(1)

其中，dH(i)表示節(jié)點(diǎn)i的超度，ks(i)表示節(jié)點(diǎn)i的ks值。

表1 不同指標(biāo)對(duì)示例超網(wǎng)絡(luò)的排序結(jié)果

3 實(shí)證分析

3.1 示例超網(wǎng)絡(luò)分析

為了驗(yàn)證本文算法的有效性和正確性。對(duì)圖2示例網(wǎng)絡(luò)進(jìn)行分析，通過刪除節(jié)點(diǎn)形成的子網(wǎng)絡(luò)數(shù)目及子圖規(guī)模大小反映算法的正確性。當(dāng)刪除節(jié)點(diǎn)后生成的子圖數(shù)量越多、子圖最大規(guī)模越小時(shí)，關(guān)鍵節(jié)點(diǎn)識(shí)別算法的準(zhǔn)確性越高。表2為按照節(jié)點(diǎn)重要性排序逐一刪除節(jié)點(diǎn)后得到的子圖數(shù)及子圖最大規(guī)模。圖3以刪除節(jié)點(diǎn)數(shù)為橫坐標(biāo)，以刪除節(jié)點(diǎn)后得到的子圖數(shù)與子圖規(guī)模為縱坐標(biāo)，展示不同指標(biāo)之間的差異。

表2 節(jié)點(diǎn)被刪除后的子圖數(shù)及子圖最大規(guī)模

圖3 節(jié)點(diǎn)被刪除后子圖數(shù)與子圖規(guī)模變化情況

3.2 數(shù)據(jù)來源

蛋白復(fù)合物數(shù)據(jù)來自數(shù)據(jù)庫CORUM(Comprehensive Resource of Mammalian Protein Complexes)[33]。該數(shù)據(jù)庫包含2 314個(gè)人類蛋白質(zhì)節(jié)點(diǎn)以及它們之間相互作用形成的1 342個(gè)復(fù)合物超邊。這些復(fù)合物大多由3～4個(gè)蛋白質(zhì)組成。此外，最大的復(fù)合物包含143個(gè)蛋白質(zhì)，而最小的復(fù)合物僅有一個(gè)蛋白質(zhì)。在蛋白質(zhì)復(fù)合物超網(wǎng)絡(luò)中，節(jié)點(diǎn)的超度表示包含該蛋白質(zhì)的復(fù)合物的個(gè)數(shù)，也是判斷蛋白質(zhì)是否是關(guān)鍵蛋白的重要依據(jù)。

3.3 實(shí)驗(yàn)結(jié)果分析

將超網(wǎng)絡(luò)中的K-shell算法應(yīng)用于蛋白復(fù)合物超網(wǎng)絡(luò)，從而得到所有蛋白質(zhì)節(jié)點(diǎn)的K-shell值與超度的關(guān)系，結(jié)果如圖4所示。

圖4 超度與K-shell值的散點(diǎn)圖

圖4中橫軸表示K-shell值，處于同一豎線上的蛋白質(zhì)具有相同的ks值。縱軸的超度表示該蛋白質(zhì)復(fù)合物的數(shù)目。此超網(wǎng)絡(luò)中,超度值小于10的節(jié)點(diǎn)，ks值大部分小于5，占總節(jié)點(diǎn)的80%左右，說明大多數(shù)蛋白質(zhì)構(gòu)成的復(fù)合物數(shù)量較少。節(jié)點(diǎn)360與節(jié)點(diǎn)361的ks值為29，處于網(wǎng)絡(luò)的中心位置，是網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)。文獻(xiàn)[34]以介數(shù)和節(jié)點(diǎn)度為中心測(cè)度分析蛋白質(zhì)在網(wǎng)絡(luò)中的位置，提出關(guān)鍵蛋白傾向于位于網(wǎng)絡(luò)的中心位置。ks值越高代表節(jié)點(diǎn)越趨于網(wǎng)絡(luò)的中心位置。蛋白復(fù)合物超網(wǎng)絡(luò)中節(jié)點(diǎn)360與361的ks值最大、處于網(wǎng)絡(luò)的中心位置，為蛋白復(fù)合物超網(wǎng)絡(luò)中的關(guān)鍵蛋白。由CORUM數(shù)據(jù)庫可知，這兩個(gè)蛋白質(zhì)結(jié)合在一起參與生成的復(fù)合物數(shù)量占大多數(shù)。在生物學(xué)中，HDAC蛋白對(duì)細(xì)胞染色體的結(jié)構(gòu)修飾和基因表達(dá)調(diào)控發(fā)揮著重要的作用，是具有條件依賴性的必需基因，而節(jié)點(diǎn)360的蛋白ID是HDAC1，節(jié)點(diǎn)361的蛋白ID是HDAC2。由此可知，超網(wǎng)絡(luò)的K-shell算法能較為準(zhǔn)確地識(shí)別網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。

由圖4知，ks值小的節(jié)點(diǎn)與其超度值呈線性分布，剩余節(jié)點(diǎn)分布則較為分散。例如，節(jié)點(diǎn)71的超度值大于節(jié)點(diǎn)497，但節(jié)點(diǎn)71的ks值卻小于節(jié)點(diǎn)497的ks值。節(jié)點(diǎn)437的超度值僅次于節(jié)點(diǎn)360，但是它們的ks值相差甚大；節(jié)點(diǎn)437的ks值為11，位于超網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的中間位置，因此，蛋白復(fù)合物超網(wǎng)絡(luò)中不存在節(jié)點(diǎn)超度值大，卻處于網(wǎng)絡(luò)邊緣位置的節(jié)點(diǎn)。節(jié)點(diǎn)792，920和921的超度值與ks值均為21，但比較超度與ks值的節(jié)點(diǎn)排名相差較大，如節(jié)點(diǎn)792，根據(jù)超度值排名位于第14位，根據(jù)ks值排名位于第6位。若將上述蛋白質(zhì)移除，至少有21種復(fù)合物無法形成，從而影響細(xì)胞的生物學(xué)功能，甚至使生物體無法存活，因此這些蛋白質(zhì)是構(gòu)成此類復(fù)合物的必需蛋白質(zhì)。

圖6 ks值與超度與排名之差

4 結(jié)論