周丽娜，李发旭，巩云超，胡 枫

(青海师范大学 a.计算机学院；b.青海省藏文信息处理与机器翻译重点实验室；c.藏语智能信息处理及应用国家重点实验室，西宁 810008)

0 引言

1 相关工作

1.1 超网络相关概念

1.2 超网络的拓扑指标

1.3 K-shell算法

K-shell算法是图算法中的一种经典算法，用以计算每个节点的核数。该算法将网络划分为从核心到边缘的不同层次，具体划分过程为：首先,将网络中度为1的节点及其连边删除；其次，删除后网络中将出现新的度为1的节点，继续删除新出现的度为1节点及其连边；最后，重复上述操作直到网络中不再新出现度为1的节点为止。此时所有被删除的节点构成第一层，即1-shell，节点的ks值为1。以此类推，进一步得到更高的壳，直至网络中的所有节点都被赋予ks值。图1为3-shell分解过程示例图。

图1 3-shell分解示例图

2 基于超网络的K-shell算法

2.1 K-shell算法在超网络中的基本思想及分解过程

在超网络中，节点超度表示包含该节点的超边数，通常认为超度大的节点重要性高，但超度仅是衡量节点重要性的局部性指标，忽略了超网络全局信息对节点重要性的影响。本文将基于复杂网络位置思想的K-shell指标扩展到超网络中，提出超网络的K-shell分解算法。算法步骤为：1)删除超网络中超度为1的所有节点，删除超度为1的节点后若网络中存在超边超度为1的超边，则删除此超边；重复此过程，直到网络中不存在超度为1的节点及超边，所有被删除的节点ks值为1；2)重复上述操作，删除超网络中所有超度值不大于2的节点和超度为1的超边，此时，所有被删除节点的ks值为2；……