第18卷第3期复杂系统与复杂性科学Vol.18No.3 2021年9月COMPLEX SYSTEMS AND COMPLEXITY SCIENCE Sep.2021
文章编号：16723813(2021)03001508；DOI：10.13306,/j.1672-3813.2021.03.003
周丽娜，李发旭，巩云超，胡枫
(青海师范大学a.计算机学院；b.青海省藏文信息处理与机器翻译重点实验室；
c.藏语智能信息处理及应用国家重点实验室，西宁810008.)
摘要：将K-shell指标扩展到超网络中，避免了超网络中超度较大、但位于超网络边 缘位置的节点对挖掘关键节点带来的影响。由于K-shell方法的局限性，导致节点
排序结果过于粗糙。针对这一问题，结合超度和Kshell(k)值利用欧式距离公式提
出识别超网络关键节点的k d指标，并利用蛋白复合物超网络进行验证。实验证明，
k d指标能够准确有效地识别超网络中的关键节点.
关键词：超图；超网络；关键节点;K-shell分解；—
中图分类号：TP39;N949文献标识码:A
Identification Methods of Vital Nodes Based on K-shell in Hypernetworks
ZHOU Lina,LI Faxu,GONG Yunchao,HU Feng
(a.Computer College; b.'I'ibctan Information Processing and Machine Translation Key Laboratory of Qinghai Province;
c.’I'he State Key Laboratory of Tibetan Intelligent Information Processing and Application,
转子动平衡
Qinghai Normal University,Xining810008,China.)
Abstract：In this paper,the K-shell index is extended to the hypernet.work to avoid the influence
of the nodes with larger hyperdegree but.located at the edge of the hypernetwork on the mining of
vital nodes.Due to the limitation of K-shell method,the result,of node sorting is too rough.In
order to solve this problem,this paper proposes a k(complex K-shell and degree)index to iden
tify the vital nodes of the hypernetwork by combining the hyperdegree and K-shell(k d)value and
using the Euclidean distance formula,and verifies it.by using the protein complex hypernetwork.
Experiments show that,k d index can accurately and effectively identify the vital nodes in the hy-
pernet.work.
Keywords：hypergraph；hypernet.work;vital node;K-shell decomposition；k d
0引言
近年来，复杂网络中关键节点识别问题引起了越来越多学者的广泛关注17］。识别关键节点对研究网络的各种功能特性及网络实际应用至关重要。任何一个网络中，一定存在一个或几个节点在网络中具有重要地位，若删除这些节点，网络可能在拓扑结构和稳定性方面受到较大程度的影响［1］.例如在生物体的传染病网络中，控制一个或几个传染源能够保护整个体［5］；在谣言传播网络中，通过控制超级传播者就能抑制事态发展［6］；在电力网络中，保护重要传输节点能够防止电网的灾难性中断［7］。因此，关键节点识别问题具有重大的理论研究意义
收稿日期:20200829；修回日期：20210112
石墨保护套基金项目：国家自然科学基金(61663041)；青海科技计划项目(2018ZJ718)
第一作者：周丽娜(1993)，女，山东淄博人，硕士研究生，主要研究方向为超网络理论及应用。
通信作者：胡枫(1970)，女，青海民和人，博士，教授，主要研究方向为复杂网络、超网络理论及应用。
-16-复杂系统与复杂性科学2021年9月
和应用价值。
最近二十年间人们对复杂网络的研究呈爆炸式增长，在真实网络结构复杂性方面获得了重大突破80］。网络科学在物理、数学、生物、计算机和社会科学等众多学科具有广泛的应用前景，它成功吸引了各领域研究者的持续关注。随着网络科学研究从宏观的统计规律转变为微观元素在网络结构和功能中扮演的不同角［11］，使得识别动态过程中有影响的节点对理解网络结构和功能至关重要。关键节点是指那些能够在更大程度上影响网络结构与功能的特殊节点。到目前为止，人们根据所研究的具体问题，提出了多种的关键节点识别方法，川等［12］把H指数引入到复杂网络中度量节点的重要性，给出了H运算展示度、H指数和核数之间的关系，并证明在同步及异步更新条件下，节点的H指数经H运算迭代收敛于K—核；Li等［13］提出了一种综合考虑节点邻居信息和路径信息的引力模型来评估网络节点的重要性。卢鹏丽等山］基于图熵并结合节点的介数及其邻接度提出介度熵，用来识别网络中的重要节点。李亚飞等［15］基于中国航路网结构提出基于改航可达性的关键航路点识别算法。此外，不少学者依据现有中心性指标提出针对某种网络模型的关键节点识别方法，陈诗等⑷对时序网络中的关键节点识别方法进行了系统的回顾，并详细分析各种方法的优缺点。常见的中心性指标可以从基于邻居节点、基于路径、基于特征向量和基于节点移除或收缩这4个角度出发，挖掘网络的关键节点23］。Kitsak等［16］从新的视角提出利用依赖整个网络位置思想的K-shell算法识别复杂网络中的重要节点，分析得出K-shell分解法可以比度、介数更准确地识别重要节点。但K-shell分解法得出的重要节点过于粗粒化，即多个节点具有相同的k值，因此很多学者对K-shell算法进行了改进。Zeng等［17］考虑了节点的剩余度和耗尽度，提出混合度分解(MDD)方法；王凯莉等［8］基于节点自身k值
与其多阶邻居的k值，提出多阶邻居壳数的向量中心性(MKV)方法，对网络中节点重要性进行区分。Yu等［19］提出了一种对最小度节点进行剪枝的分解方法，并证明了最低次分解(LDD)是著名K核分解的一个细分。黄丽亚等［20］提出用加权K阶传播数法衡量网络中节点的重要性。
随着网络规模的日益扩大和连接的复杂多变，基于普通图的复杂网络已经不能很好地描述真实网络或真实系统的所有特征®23］，因此超网络应运而生［22］。超网络作为研究复杂系统与复杂性问题的新方法，继复杂网络研究成为热潮后，超网络研究开始受到关注，并被广泛运用于解决实际问题⑵26］。无论是普通网络还是超网络，评估节点的重要性并发现重要节点是网络分析和系统科学领域值得研究的问题。例如，在科研合作超网络中，哪位作者的文章最权威？蛋白质相互作用超网络中，哪类蛋白质必不可少？在疾病传播超网络中，谁是超级传播者等等。
目前复杂网络中挖掘关键节点的指标很多，但超网络中却较少。Estrada等［22］扩展复杂网络中子图中心性和聚类系数的定义到超网络上，并用这两种指标识别出了3类现实超网络中的核心节点。胡枫等［27］利用复合参数的方法识别出了蛋白复合物超网络中的关键蛋白。王雨等［28］从超网络角度出发研究科研合作超网络中作者的重要性问题，综合多方面因素，提出了重要度指标D'。单而芳等［29］讨论了超网络中心性测度的一类方法一一广义Position值。孙琳等［30］基于超网络理论对上海交通轨道网络进行识别关键节点的实证研究。超度作为度量超网络中节点重要性的通用指标，计算简单、时间复杂度低，属于局部性指标，因此存在一定局限性，当网络中出现某个节点超度值较高，
但其邻居节点的关联度并不高，此时超度便不能准确挖掘重要节点。子图中心性和聚类系数的时间复杂度较高，不适用于大规模网络。针对上述问题，本文将基于网络位置思想的K-shell指标应用到超网络中，对超网络中各节点进行了重要性划分，该指标时间复杂度低且考虑到了网络的全局信息。但利用K-shell指标划分了大量重要性相同的节点，为了弥补此弊端，我们对K-shell的划分方法进一步做了改进，提出了k d指标识别超网络中的关键节点。
1相关工作
1.1超网络相关概念
超网络分为基于超图的超网络和基于网络的超网络［31］.本文研究的是基于超图的超网络。Berge［32］首次给
出了超图的概念，设V={v v2,•••,▽”}是一个有限集；若e,=1,2,…，”)，且U e,=V，则称二元关系H=
线性驱动器i=1
(V,E)为超图，其中v(=1,2,…，”)称为超图的顶点—((=1,2,…，”)称为超图的超边。超图H=(V,E)的邻接矩阵A(H)是一个N X N的对称方阵，其元素j为同时包含顶点v和v的超边数量，对角线元素为0。关联矩阵B(H)是一个NXM的矩阵，如果顶点v在超边e，中，则b,=1，否则为0.
第18卷第3期周丽娜，等：基于K-shcll的超网络关键节点识别方法・17・1.2超网络的拓扑指标
超网络中节点度等同于普通图中度的定义，即为节点的连边数，即k H(i)=Y a j=Y j。节点，的超度
t=1t=1
记为d H(i)，表示包含节点，的超边数，即d H(i)=Y b j.超边超度e H()定义为超边e』中包含的节点个数,
j=1
即e H()=Y b i。
i=1
12K-shell算法
K-shell算法是图算法中的一种经典算法，用以计算每个节点的核数。该算法将网络划分为从核心到边缘的不同层次，具体划分过程为：首先，将网络中度为1的节点及其连边删除；其次，删除后网络中将出现新的度为1的节点，继续删除新出现的度为1节点及其连边；最后，重复上述操作直到网络中不
再新出现度为1的节点为止。此时所有被删除的节点构成第一层，即1-shell，节点的—值为1。以此类推，进一步得到更高的壳，直至网络中的所有节点都被赋予—值。图1为3-shell分解过程示例图。人脸抓拍系统
a普通图Z5例b1-shell图c2-shell图d3-shell图
图13-shell分解示例图
Fig.l3-shell decomposition
2基于超网络的K-shell算法
2.1K-shell算法在超网络中的基本思想及分解过程
在超网络中，节点超度表示包含该节点的超边数，通常认为超度大的节点重要性高，但超度仅是衡量
节点重要性的局部性指标，忽略了超网络全局信息对节点重要性的影响。本文将基于复杂网络位置思想的K-shell指标扩展到超网络中，提出超网络的K-shell分解算法。算法步骤为：1)删除超网络中超度为1的所有节点，删除超度为1的节点后若网络中存在超边超度为1的超边，则删除此超边；重复此过程，直到网络中不存在超度为1的节点及超边，所有被删除的节点—值为1;2)重复上述操作，删除超网络中所有超度值不大于2的节点和超度为1的超边，此时，所有被删除节点的—值为2；3)以此类推，直到超网络中所有节点都被赋予—值。
如图2所示超网络的3-shell分解过程示意图，图2b~图2d为1-shell、-shell和3-shell分解图。
a超网络示例图b1-shell分解图c2-shell分解图d3-shell分解图
图2超网络的3shell分解过程示例图
Fig.23-shell decomposition process of hypernetwork
-18 -复杂系统与复杂性科学2021年9月
图2a 为图1a 中添加超边以后的超网络图，在图1a 中删除k 值为1的节点后，其余节点的度值均大于1. 继续删除度值为2的节点，即删除节点5以及与它相连的两条边，则节点1与节点2的度值均变为3.与复杂网 络不同，如图2a 所示，删除超网络中节点7和节点8后，所在超边的超度变为1，依据超网络的K-shell 算法删除 这条超边.删除节点9和节点10及其所在的超边后，继续删除网络中超度变为1的节点6，删除该节点后，超边 的超度为2，因此保留该超边.综上所述，复杂网络中删除一个节点时与之相连的边同时删除；而超网络中，只有 当超边中只剩一个节点，即超边超度为1时，才删除此超边.
分析图2a 中，超度最大的节点4、节点14，其超度值为5 ，由K-shell 算法得到节点4的k d 值为3，节点14的 k d 值为1.表明节点14位于网络的边缘位置，虽然超度值最大但并不是重要节点.因此，利用超度刻画超网络 中的重要节点并不完全准确.但由K-shell 算法最终分解得到多个重要节点，导致节点的排序结果过于粗糙，如 图2d 所示.为了解决此问题，本文进行了改进.
23 改进的超网络K-shell 算法
超度作为一种局部性指标，侧重衡量节点对网络的直接影响力；而K-shell 算法基于整个网络位置的思
陶瓷手链想, 为全局度量.综合考虑两种指标的性质，利用欧式距离公式定性计算超网络中关键节点的核度值.则超网络中 节点，的核度中心度k d (t)定义为
k d (i ) =y d H (i ) +k d (i )
(1 )其中,h (,)表示节点i 的超度k ( i )表示节点i 的k d 值.
由图2可知,K-shell 指标划分的节点1和4同等重要，但是k d 指标分离出节点4为示例网络的重要节点. 表1为图1中的节点在3种指标超度k 、k d 的重要性排序结果.针对图2超网络中k d =3的两个节点，不难发 现节点4明显比节点1重要，节点4的邻居节点的超度大于节点1。相比于其他节点，节点4位于超网络核心位 置的节点连接的超边数量更多，传播影响力更大.从图2可知，节点14位于网络的边缘位置.若删除超度最大 的节点14，网络最大连通分支数为0. 92；删除k d 值最大的节点4，则网络的最大连通分支数为0.78。显然，节点 4比节点14处在网络更重要的位置.
3实证分析
3.1示例超网络分析
为了验证本文算法的有效性和正确性.对图2示例网络进行分析，通过删除节点形成的子网络数目及子图 规模大小反映算法的正确性.当删除节点后生成的子图数量越多、子图最大规模越小时，关键节点
识别算法的准 确性越高.表2为按照节点重要性排序逐一删除节点后得到的子图数及子图最大规模.图3以删除节点数为横 坐标，以删除节点后得到的子图数与子图规模为纵坐标，展示不同指标之间的差异.
表1不同指标对示例超网络的排序结果表2节点被删除后的子图数及子图最大规模Tab.2 The number of subgraphs and the maximum size of
example hyper-network
subgraphs after deleting nodes Tab.1 Sorting results of different indicators for Rank Hyper-degree k d k d
删除节点Hyper-degree 子图k d k d 14,41,4
子图数子图 最大规模子图数子图 最大规模子图数最大规模212,3141
1141172153
5,6others 12
210311210336453642,,25,6
44334435others 2,3
532343262233226127222222
8others 8121212
9
000000由图3知，删除第一个节点后k d 算法得到的子图数较大且子图最大规模较小.由k d 算法得到的子图规模 在删除第4个节点后，一直处于最低位置.综上可知，k d 核度中心性指标测度网络节点的重要性是有效且可行 的.为了进一步验证k d 指标的有效性，本文针对蛋白复合物超网络中关键蛋白进行识别.
3.2数据来源
蛋白复合物数据来自数据库 CORUM(Comprehensive Resource of Mammalian Protein Complexes)[33].该自动点火器
第18卷第3期周丽娜，等：基于Kshcll 的超网络关键节点识别方法19数据库包含2 314个人类蛋白质节点以及它们之间相互作用形成的1 342个复合物超边。这些复合物大多由 3〜4个蛋白质组成。此外，
最大的复合物包含143个蛋白质，而最小的复合物仅有一个蛋白质。在蛋白质复合物 超网络中，节点的超度表示包含该蛋白质的复合物的个数，也是判断蛋白质是否是关键蛋白的重要依据。
3.3实验结果分析
将超网络中的K-shell 算法应用于蛋白复合物超网络，从而得到所有蛋白质节点的K-shell 值与超度的关 系，结果如图4所示。
图3节点被删除后子图数与子图规模变化情况
Fig.2 The number of subgraphs and the size of subgraphs after deleting nodes
图4中横轴表示K-shell 值，处于同一竖线上的蛋白质具有相同的—值。纵轴的超度表示该蛋白质复合物 的数目。此超网络中，超度值小于10的节点，—值大部分小于5，占总节点的80%左右，说明大多数蛋白质构成 的复合物数量较少。节点360与节点361的—值为29，处于网络的中心位置，是网络的关键节点。文献［34］以 介数和节点度为中心测度分析蛋白质在网络中的位置，提出关键蛋白倾向于位于网络的中心位置。—值越高代 表节点越趋于网络的中心位置。蛋白复合物超网络中节点360与36
1的—值最大、处于网络的中心位置，为蛋 白复合物超网络中的关键蛋白。由CORUM 数据库可知，这两个蛋白质结合在一起参与生成的复合物数量占大 多数。在生物学中,HDAC 蛋白对细胞染体的结构修饰和基因表达调控发挥着重要的作用，是具有条件依赖 性的必需基因，而节点360的蛋白ID 是HDAC1 ，节点361的蛋白ID 是HDAC2.由此可知，超网络的K-shell 算法能较为准确地识别网络中的关键节点。
由图4知，—值小的节点与其超度值呈线性分 布，剩余节点分布则较为分散。例如，节点71的超 度值大于节点497，但节点71的—值却小于节点
497的—值。节点437的超度值仅次于节点360, 但是它们的—值相差甚大；节点437的—值为11 ,
位于超网络拓扑结构的中间位置，因此，蛋白复合物 超网络中不存在节点超度值大，却处于网络边缘位
置的节点。节点792,920和921的超度值与—值 均为21，但比较超度与—值的节点排名相差较大， 如节点792，根据超度值排名位于第14位，根据—值排名位于第6位。若将上述蛋白质移除，至少有21种复合 物无法形成，从而影响细胞的生物学功能，甚至使生物体无法存活，因此这些蛋白质是构成此类复合物的必需蛋 白质。
由于蛋白质及其相互关系的复杂性，且不同的指标代表不同的特性，单个指标一般只能从某一方面反映节点 的部分信息。超度表示该蛋白质参与构成的复合物的数量;K-shell 反映蛋白质在网络中的位置关系，节点度表 示蛋白质之间的联系程度。文献［35］中生物学上通过对S.cerevisiae 和E.Coil 的移除分析已经证实，关键蛋白通 常比其他蛋白具有更多的交互数量。经文献［7］分析节点939是超网络的关键节点，该节点的节点度最大，具有 更多的交互数量。文献［36］提出蛋白质处于网络越核心的位置，进化越慢并且越有可能是关键蛋白。而K-shell 算法识别出多个蛋白质同时位于网络的中心位置，为了进一步识别出蛋白复合物超网络中的关键蛋白，本文利用 k d 指标对超网络中的关键蛋白进行识别。0 123456789 101112131415161718192021222321252627282930K-shellfi 50
4020
47
71°497 ::J 曲170536010i i !
,；图4 超度与K-shell 值的散点图Fig.4 Scatter diagram of hyper-degree and
K-shell
