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

(青海師范大學 a.計算機學院；b.青海省藏文信息處理與機器翻譯重點實驗室；c.藏語智能信息處理及應用國家重點實驗室，西寧 810008)

0 引言

1 相關工作

1.1 超網(wǎng)絡相關概念

1.2 超網(wǎng)絡的拓撲指標

1.3 K-shell算法

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

圖1 3-shell分解示例圖

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

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

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

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

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

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

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

2.2 改進的超網(wǎng)絡K-shell算法

(1)

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

表1 不同指標對示例超網(wǎng)絡的排序結果

3 實證分析

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

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

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

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

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

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

3.3 實驗結果分析

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

圖4 超度與K-shell值的散點圖

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

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

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

4 結論