基于子图交互关系的网络结构增强算法

胡 雯，马 闯，张海峰*

(1. 安徽大学数学科学学院 合肥 230601；2. 安徽大学互联网学院 合肥 230601)

近年来，网络科学作为一门新兴交叉学科得到越来越多的关注。现实世界中许多真实系统都可以基于网络框架进行理解，如生物网络系统[1-2]、社会网络系统[3-4]、交通网络系统[5-6]等。挖掘网络的结构信息可以帮助我们更深入地了解这些系统并加以应用，因此如何发展有效的方法挖掘网络的结构信息有着重要的科学价值和广泛的应用前景。如识别网络上的关键点用于疾病控制和舆情扩散[7-9]、相对关键节点的识别用于罪犯挖掘和致病基因查找[10]、链路预测用于好友推荐和应对网络攻击[11]、社团划分用于潜在客户挖掘和社交网络角色检测[12]以及动力学分析用于通信安全和疫情分析[13-14]等。

现有的网络结构分析方法大多是基于网络的浅层结构开展的，仅考虑节点对之间是否有联系，使用的网络结构信息都是有限的，这些基于浅层结构的分析方法会造成很多深层的、隐藏的信息丢失，而结构信息的缺失会导致真实网络的内在联系无法被完整地反映。真实网络具有很多不同种类的子图，子图捕捉了网络中特定的局部连接模式，这些子图的大小、类型、属性都会影响网络的结构与功能，因此很多学者开展了关于网络子图的研究。如文献[15] 研究了大型稀疏网络中子图频率与网络结构的联系，发现利用不同子图出现的频率可挖掘网络的局部密集结构。文献[16] 在大肠杆菌的转录调控网络中发现不同的子图结构在整个网络中对应的功能是特定的，进而研究网络不同结构的子图捕获网络局部聚集信息的差异性。文献[17] 将三角形结构的频繁子图应用于图聚类，发现利用子图结构能更有效地实现网络的社团检测。文献[18]研究不确定图的数据挖掘，提出一种基于期望支持阈值来寻找不确定图的频繁子图的方法。文献[19]提出一种基于子图的近似图匹配技术，在生物网络中高效地搜索具有相似功能的细胞实体。

以上基于子图的数据挖掘研究仅仅考虑了子图自身的一些属性，没有考虑子图之间的交互关系。实际上，如何有效地构建子图间的交互关系来实现网络的结构增强，并用于后续的结构挖掘任务具有重要的意义。最近文献[20] 选择网络中不同的子图结构作为节点，分别构造了不同阶数的子图网络(subgraph network, SGN)，实现了子图之间的交互，并发现子图网络的集成可以增强后续一系列图分类算法。基于SGN 提取的特征补充了原始网络的结构特征，可以更深入地挖掘网络结构信息，然而构建SGN 的过程是复杂的，并且构造更高阶的SGN需要知道低一阶SGN 的结构。基于此，本文提出了两种不需要构造SGN 的赋权方法，直接从原始网络中挖掘出子图之间的交互信息，在实现结构增强的同时也大大降低了算法复杂度。主要思想是基于不同阶数SGN 的构建过程，提出两种加权方法将SGN 的结构信息在原始网络中以边权值的形式表现出来，一种是将一阶子图网络(first-order subgraph network, SGN(1))节点的属性作为原始网络对应边的权重，构造一阶加权网络；另一种是将二阶子图网络(second-order subgraph network, SGN(2))节点集合中包含原始网络同一条边的所有节点属性综合起来作为这条边的权重，构造二阶加权网络。SGN(1)和SGN(2)考虑了两种最基本的子图结构：边和开三角结构，因此本文提出的两种赋权方法以权重的形式分别体现的是边和开三角结构的交互关系，既保留了原始网络的结构信息，又补充了特定子图的交互信息，实现了网络结构增强。为了验证本文提出的两种加权方法在后续结构挖掘任务中的有效性，本文定义了两个基于加权网络的中心性指标识别真实网络中的关键节点。实验结果表明，在关键点识别问题研究中，基于加权网络的中心性指标比经典的度中心性、接近性中心性、介数中心性、特征向量中心性、K-Shell 中心性、LeaderRank以及显著性中心性都具有更好的性能。

1 子图网络

本文在给网络赋权的过程中涉及不同阶数SGN 的概念及对应的构造方法，因此先介绍这些概念和构造过程。

1.1 SGN 的定义

给定一个无向无权网络G(V,E)，其中V={vi|i=1,2,···,N}表示节点集合，节点数为N，E⊆(V×V)表示边的集合，E中元素(vi,vj)满足(vi,vj)=(vj,vi)，i,j=1,2,···,N。定义G的子图gi=(Vi,Ei)，其中gi⊆G，当且仅当Vi⊆V且Ei⊆E。

1.2 SGN 的构造过程

网络中最基本的子图是边和三角结构，它们在大多数网络中出现的频率较高，不会造成子图网络过于稀疏的情况，并且相比于边结构，三角结构也可以补充更多网络局部结构的信息，利于更高阶子图网络的构造，因此本文选择这两种子图分别构造SGN(1)和SGN(2)。本文研究都是基于无向网络，边的情况只有一种(如图1a)，三角结构的情况有两种，分别为开三角结构(如图1b)和闭三角结构(如图1c)[21]，在构造SGN(2)的过程中只考虑更为简单的开三角结构，并将开三角结构中度为2 的节点记为顶点。接下来分别介绍SGN(1)和SGN(2)的构造过程。

图1 子图示意图

1.2.1 SGN(1)的构造过程

给定原始网络G(V,E)，基于边构造相应的SGN(1)，记为G′(V′,E′)。SGN(1)的节点集合为原始网络的边，如果两条边在原始网络有共同端点则相应的节点在SGN(1)中有连边。这里以图2a 的原始网络举例说明SGN(1)的构造过程，依次提取原始网络的边作为SGN(1)的节点，如SGN(1)中标签为(3,4)和(2,4) 的节点分别表示原始网络的边(v3,v4)和(v2,v4)，这两条边包含相同的端点v4，那么SGN(1)中这两个节点有连边。按照这样的构造方法，最终得到相应的SGN(1)，如图2b 所示。

1.2.2 SGN(2)的构造过程

给定原始网络，基于SGN(1)构造相应的SGN(2)，用G′′(V′′,E′′)表示。SGN(2)考虑更高一阶的子图，即开三角结构作为节点集合，构造出SGN(1)之后进一步提取SGN(1)的边以获得开三角结构，如果两个开三角包含相同的边则相应的节点在SGN(2)中有连边(需要注意的是，如果以两个开三角是否包含共同节点作为连边条件会导致子图网络过于稠密，反而不利于挖掘网络的结构信息)。图2d 就是基于图2b 构造的SGN(2)，SGN(2)中标签为(1,2,4)的节点表示原始网络节点v1、v2、v4组成的开三角，标签为(1,2,4) 和(1,2,3) 的两个节点包含共同的边(v1,v2)，那么这两个节点之间有连边。通过这样的构造方法，最终得到节点数为6，边数为9 的SGN(2)，如图2d 所示。

图2 SGN(1)和SGN(2)的构造过程以及对原始网络的赋权过程

2 基于SGN 的加权网络

文献[20]定义了SGN 的构造方法之后通过子图网络的结构信息以及原始网络的结构信息进行图分类，这种方法需要对新构造的SGN 进行结构分析，有较高的复杂度，尤其在原始网络边数很多的情况下，SGN(1)的规模会很大，并且SGN(2)是基于SGN(1)构造的，算法复杂度会更高。那么是否有方法既能反映不同阶子图信息又不需要添加太多额外的复杂度？基于此，本文根据SGN(1)和SGN(2)的拓扑结构对原始网络进行赋权，以权值的形式表现子图之间的交互关系，得到的加权网络分别记为一阶加权网络和二阶加权网络。

2.1 一阶加权网络的构造

首先介绍基于SGN(1)的赋权方法，SGN(1)的每一个节点分别代表G的每一条边，那么可以选择SGN(1)节点的度作为G中相应边的权重，这个权重表示与这条边有相同端点的其他边的数目，即与这条边有交互的边数，基于此方法得到的加权网络即为一阶加权网络。

以图2b 的SGN(1)为例介绍一阶加权网络的赋权过程，即计算出SGN(1)中每个节点的度作为对应边的权重。如标签为(1,2) 的节点度为2，那么给对应边(v1,v2)赋权重为2，表示G中有两条边(v1,v3)、 (v2,v4)与这条边包含共同的端点，给G中每条边都赋权之后，得到对应的一阶加权网络，如图2c 所示。

2.2 二阶加权网络的构造

二阶加权网络基于SGN(2)对G进行赋权，SGN(2)中的节点集合由G中 的开三角结构构成。要给G中的某一条边赋权，先在SGN(2)的节点集合中找出包含这条边的所有开三角结构，选择这些节点的度的总和作为权重，权重也代表与这条边相关的开三角结构有交互的开三角的数目，基于此得到的加权网络即为二阶加权网络。

以图2d 的SGN(2)为例介绍二阶加权网络的赋权过程，给G的边(v1,v3)赋权，在SGN(2)中找出包含边(v1,v3)的3 个节点，标签分别为(1,2,3)、(1,3,4)、(1,3,5)，这3 个节点的度分别为3、4、3，计算它们的总和10 即为边(v1,v3)的权重。按同样的方法给所有边赋权，最终得到对应的二阶加权网络，如图2e 所示。

从式(2)和式(5)可以发现，一旦知道子图网络SGN 的定义规则以及赋权方式，那么并不需要把子图网络构造出来并加以分析，可以直接利用原始网络节点的度得到两种加权网络，显然运算复杂度会大大降低。

3 实验与结果

为了表明本文定义的赋权方法可以包含更深层次的网络结构信息，本文以网络的关键点识别作为研究对象。为此定义加权网络节点的强度作为新的中心性指标，然后与原始网络上的一些中心性指标进行比较，判断该中心性指标能否更好地刻画节点的重要性。

3.1 数据集

本文在8 个真实网络中进行了关键点识别问题的研究，这8 个真实网络分别是Email[22]、TAP[23]、Yeast[24]、CA-GrQc1[25]、Rt-alwefaq[26]、Rt-obama[26]、Power[27]、Y2H[28]。表1 为网络的基本信息，其中N为节点数，M为边数，＜k＞为平均度，βc=＜k＞/＜k2＞为传播阈值。

3.2 中心性指标

本文考虑一阶加权网络和二阶加权网络中节点的强度分别定义了两个新的中心性指标，一阶子图网络中心性(first-order subgraph network centrality,SGN1)和二阶子图网络中心性(second-order subgraph network centrality, SGN2)：

表1 网络的基本信息

特征向量中心性(eigenvector centrality, EC)[32]考虑节点的邻居数以及节点邻居的重要性，节点i的特征向量中心性定义为：

式中，xj表示节点j的重要性；Ai j=(ai j)N×N是网络的邻接矩阵；c是比例常数。

K-Shell 中心性(KS)[33]是基于节点度的一种粗粒度划分，节点的核数代表了其在网络中的深度，越深层的节点重要性越高。其步骤为：1) 删去网络中度为1 的节点，残差图中出现度为1 的节点继续删除，直至剩余网络中没有度为1 的节点，此时，所有删去节点记为1-shell；2) 使用递归的方法删去网络中度为2 的节点，记为2-shell，依次下去直至网络中所有节点被删除。

LeaderRank(LR)[34]是基于游走的中心性指标，LR 主要用于有向网络，对于无向网络，首先将无向网络中的无向边理解为有向网络中的双向连接，然后添加一个背景节点g与网络中的所有节点进行双向连接，考虑了节点邻居的重要性，节点i在t时刻的得分为：

式中，wi j表示边(i,j)的权重；惩罚因子α(α ≥1)表示对大度节点进行惩罚。

3.3 评价指标

本文以SIR(susceptible-infected-recovered)传播模型[36]评估网络中每个节点的重要性，得到每个节点作为源头时所感染的范围，定义感染范围的比例为节点的重要性。为了评估某一个节点的传播能力，将这个节点预先设为感染态，其他节点均为易感态进行传播，设SIR 传播模型的感染概率为 β，恢复概率为1，直到网络中不存在感染态节点就终止SIR 传播过程。在此过程中，节点的感染范围反映了节点的重要性，感染范围越大就代表该节点重要性越大。

用Kendall Rank 相关系数[37]τ来评价基于中心性指标的节点重要性排名(记为X)与节点在SIR 传播模型的真实传播能力排名(记为Y)的相关性，记X,Y中第i(1 ≤i ≤N)个值分别为Xi,Yi。如果X,Y中的元素满足Xi＞Xj且Yi＞Yj，或者满足Xi＜Xj且Yi＜Yj，则表明X,Y中这两对元素一致；如果Xi＜Xj且Yi＞Yj，或者Xi＞Xj且Yi＜Yj，则表明这两对元素不一致；如果Xi=Xj或Yi=Yj则表明这两对元素既不是一致的也不是不一致的，定义Kendall Rank 相关系数τ为：式中，C是X,Y中拥有一致性的元素对数；D是X,Y中拥有不一致性的元素对数。

定义M值[38]来量化节点重要性排名X的分辨率：

式中，Nc表示在排名中处于同一等级c的节点数；M(X)取值在0～1 之间，M(X)越大表示排名X的分辨率越高，当M(X)=1时表示X中所有排名都处于不同等级，M(X)=0表示X中所有排名都处于同一等级。

另外定义ε(p)[33]量化中心性指标在识别网络中有影响力的传播者方面的性能：

式中，p是网络规模N的比例(p∈[0,1])，定义每个节点作为源头所感染范围的比例为节点的扩散效率；L(p)是中心性最高的pN个节点的平均扩散效率；Leff(p)是扩散效率最高的pN个节点的平均扩散效率；ε(p)量化了具有最高中心性的pN个节点的平均感染范围与SIR 传播过程中最优的pN个节点的平均感染范围的接近程度，ε(p)越小表示中心性指标越能准确识别网络中有影响力的节点。

3.4 结果与分析

本文在真实网络中，将新定义的两个中心性指标SGN1、SGN2，与已有的DC、CC、BC、EC、KS、LR、DIC 这7 个中心性指标进行了对比实验。图3 比较了基于中心性指标的节点排名与不同传播率下的SIR 传播模型的真实排名的Kendall Rank 相关系数τ，实验结果取500 次平均。结果表明，除了在Power 网络中，SGN1 和SGN2 指标仅次于LR 指标，在其他7 个网络中，本文基于子图定义的两种新的中心性指标优于其他7 种中心性指标，能更好地识别网络中有影响力的节点。

此外还比较了SGN1、SGN2 和DC、CC、BC、EC、KS、LR、DIC 的M值，表2 表明M(SGN1)、M(SGN2)、M(CC)、M(EC)、M(DIC)的数值非常接近1，说明这5 种指标有很好的分辨率，并且优于M(DC)、M(BC)、M(KS)、M(LR)，但由图3 可知本文定义的中心性指标SGN1、SGN2 在衡量网络的节点重要性方面效果要优于CC、EC、DIC。

图3 真实网络中不同中心性指标的τ值比较

对于每一个真实网络，设置SIR 模型的感染概率β ＞〈k〉/(〈k2〉-〈k〉)，恢复概率为1，SIR 传播模型的传播范围取500 次平均。定义网络规模比例p在0.01～0.20 之间等距取20 个值，在真实网络中比较了SGN1、SGN2 和DC、CC、BC、EC、KS、LR、DIC 这7 种中心性指标对应的ε(p)。图4的结果表明本文的中心性指标SGN1 和SGN2 对应的ε(p)在大部分的网络中最优，且中心性指标SGN1和SGN2 对应的ε(p)都接近0，所以SGN1 和SGN2在识别网络中有影响力的节点方面总体优于DC、CC、BC、EC、KS、LR、DIC 指标。

图4 真实网络中不同中心性指标的ε(p)比较

表2 不同中心性指标的M 值比较

4 结 束 语

综上所述，本文考虑了如何用特定子图间的交互关系来实现网络结构增强，进而可以更有效地执行结构挖掘方面的任务。基于SGN 的构造过程将子图的结构信息以权重的形式在原始网络中表现出来，直接对原始网络进行赋权得到一阶加权网络和二阶加权网络。然后在加权网络中定义新的中心性指标SGN1 和SGN2，并与原始网络的7 个中心性指标DC、CC、BC、EC、KS、LR、DIC 进行比较。通过研究发现，这两种赋权方式可以更准确地识别网络中的关键节点。因此利用子图交互关系的赋权方法既能挖掘网络的深层次结构，又能大大降低运算复杂度。