基于三角形子图的复杂网络过滤压缩算法

吴 涛,任淑霞,张书博

(天津工业大学 计算机科学与技术学院,天津 300387)

0 概述

目前,复杂网络的规模逐渐增大,有些网络包含数百万甚至数十亿的节点和边,这给复杂网络的理解和分析带来极大挑战,若不进行压缩,网络中的节点和边将会非常密集,人们很难从中获取有用信息。因此,学者们开始关注复杂网络的压缩问题[1],并从不同的角度设计基于节点、基于社区和基于边的压缩方法。

文献[2]提出一种基于节点重要性评价指标的压缩算法,该算法通过删除非重要性节点和与之相连的边来压缩网络,但其采用keep-One和keep-All策略来补充重要节点及边,这会引入新的节点和边,不满足原网络结构的要求。文献[3]利用k-core的概念提出CABK算法,该算法去掉网络中的k-壳节点,将剩下节点集合中具有相同k-core值的核节点作为相似节点进行合并,从而达到压缩网络的目的。文献[4]从随机中心性、度中心性、相对节点重要性、PageRank、中介中心性这5个方面提出5种压缩方案。但是,上述方案的缺点是删除节点和边后未补充网络,造成网络信息丢失。

文献[5]提出一种以网络社区为压缩对象的SNC算法,该算法在保证社区间关联的前提下,以保留社区中重要节点的方式来压缩网络。文献[6]提出一种基于非重要节点拆分融合的网络层次压缩算法,该算法将网络中的非重要性节点块拆分融合到相邻的节点块中,实现对网络结构的快速压缩。

文献[7]提出一种基于边的压缩算法,其将原始网络划分成2个团体,每个团体只由一棵树来保存路径结构,这大幅减少了网络中的边数量,但缺点是只对网络中的边进行约减,而节点数量没有改变,不利于网络分析。文献[8]提出一种自组织的边缘捆绑算法,该算法在不减少网络节点和边的前提下,将相邻的边捆绑成束来对边进行压缩。

上述算法主要从复杂网络的节点、社区等角度来设计压缩算法。文献[9]基于多尺度几何分析中的显微镜策略,提出一种网络压缩策略,实现网络数据及结构的稀疏表示。文献[10]基于三角形结构提出一种Bound_tri算法,该算法从节点出发,通过构建三角形集合来对网络进行压缩,但其缺点是需要同时访问邻接矩阵和邻接列表,导致算法执行时间增加,且Bound_tri算法以度作为选择标准来降低计算规模,具有片面性,不符合网络的实际情况。

虽然研究人员已经从不同角度提出了复杂网络压缩方法,但如何缩短压缩时间、提高压缩率和保持原网络的结构仍然是有待解决的问题。为此,本文提出基于三角形子图的复杂网络过滤压缩算法。为缩短压缩时间并提高压缩率,在计算三角形子图集合前,提出一种节点重要性排序算法NRSA,以选出高、低重要性节点并进行过滤。利用三角形子图来保留复杂网络的结构,以边为迭代对象,列出边两端的节点及共同节点集组成三角形子图集合,在此基础上,解析三角形子图集合以完成网络压缩。

1 节点重要性排序

1.1 相关技术

LeaderRank[11]是一种节点重要性排序算法,该算法在原网络的基础上增加一个节点g,将g与所有节点相连接,得到一个强连接的新网络。算法首先给除节点g之外的N个节点分配1个单位的LR值(LLR),接着将1个单位的LR值分配给与N个节点直接相连的邻居节点,这一过程根据式(1)不断迭代,直至达到稳定状态。

(1)

1.2 NRSA算法

LeaderRank算法主要依赖节点的邻居节点来给其分配LR值,这种计算方式仅考虑节点的局部重要性,而忽略节点在网络结构中的全局重要性。

由图1可以看出,节点4的邻居节点明显多于节点7,LeaderRank算法每次迭代分配给节点4的LR值大于节点7,因此,LeaderRank算法认为节点4的重要性高于节点7。但是,从网络的整体结构来看,节点7作为连接3个不同节点群的中间节点,其在整个网络结构中最重要。为综合考虑节点的局部重要性和全局重要性,本文采用邻度来反映节点影响力大小并作为全局重要性的衡量指标。

图1 简单无向网络示意图

定义1(邻度) 设vi是网络G中的一个节点,邻度是G中vi的所有邻居节点vj的度的总和,记为AdjDe(vi),计算公式如下:

AdjDe(vi)=∑De(vj)

(2)

定义2(节点影响力) 设vi是网络G中的一个节点,节点vi的影响力是G中vi的邻度和本身度之和,记为Node_Ef(vi),计算公式如下:

Node_Ef(vi)=AdjDe(vi)+De(vi)

(3)

(4)

式(4)表明:

1)ai为与节点vi相连的邻接节点,邻接节点个数越多,节点vi的排序值就会越高,符合直观判断;

2)vj的节点影响力越大,vi所得的vj的LR值就会越大,vi在网络结构中就越重要。

NRSA算法步骤如下:

1)使用LeaderRank算法计算节点的LR值。

2)通过式(2)、式(3)计算节点vi的邻度,并得出节点vi的节点影响力Node_Ef(vi)。

3)根据得到的节点vi的LR值和Node_Ef(vi),使用式(4)计算得出节点vi的排序值,并通过离差标准化将结果映射到[0,1]区间上。

2 复杂网络过滤压缩算法

2.1 三角形子图

三角形子图[12]是复杂网络中一种特别的3-连通子图。在复杂网络G=(V,E)中,可以用TΔ=(vΔ,eΔ)表示含有3个节点和3条边的三角形子图,即TΔ〈a,b,c〉={vΔ={a,b,c}⊂v,eΔ={(a,b),(a,c),(b,c)}⊂e}。对于拥有e条边的复杂网络而言,计算三角形子图所需的时间为O(e3/2)[13],说明三角形子图能在有效时间内被计算出来。

2.2 三角形子图集合

传统三角形子图计算算法是节点迭代算法,其对象是网络中的节点。而本文算法是一种边迭代算法,算法从复杂网络中任意选取一条边,搜索边两端节点的邻接列表,检查其中是否存在共同节点,最后将它们与共同节点集构成三角形子图集合。例如,选取的边为(a,b),边两端节点的邻接列表分别为:Adj(a)={w,h,m,n},Adj(b)={w,h,m,n,l,d}。a、b节点的共同邻接节点为Adj(a)∩Adj(b)={w,h,m,n}。因此,三角形子图集合为:,,,。边迭代算法的伪代码如下:

算法1边迭代算法

输入复杂网络G(V,E)

输出三角形子图集合Triangle_list

Begin

Triangle_list=∅;

for (a,b) in E: //迭代复杂网络的每条边

If (Adj(a) ∩ Adj(b) != ∅):

Node_list = Adj(a) ∩ Adj(b) //节点邻接列表的共

//同节点

End if

For w in Node_list:

Triangle_list.add()//组成三角形子图,并添

//加到三角形子图集合中

End for

End for

End

2.3 三角形子图压缩算法

复杂网络中通常有上万甚至几百万个节点或者边,如果直接将列出三角形子图集合的算法应用到复杂网络的压缩中,算法不仅执行效率较低,而且需要极高的代价才能完全列出所有三角形子图。因此,在复杂网络中降低列出三角形子图的代价是网络压缩的关键。

由图2可以看出,节点重要性值的分布十分不均匀,多数节点的重要性非常低,小部分节点的重要性很高。特别地,高重要性与低重要性节点之间含有的共同邻接节点非常少,但寻找它们之间的三角形子图却占用大量的计算时间。因此,在计算三角形子图前过滤掉高、低重要性节点,可以减小计算规模,且能避免较高的计算代价,从而得到高效的三角形子图集合。本文将带过滤性质的三角形子图压缩算法定义为NIIET(Node Importance In Edge Triangle)。NIIET算法在压缩时只需要访问邻接列表,邻接列表中包含边的方向性,可应用于有向图和无向图。

图2 节点重要性统计结果

图3是一个包含8个节点、16条边的简单无向网络图,其中,线上数字表示线的编号。如表1、表2所示,边迭代算法可以得到一个包含42个三角形的三角形子图集合,会产生27条边的冗余。假如存储一个三角形子图的边需要2个单位,则会产生54个单位的冗余。因此,可以通过过滤掉高、低重要性节点来降低三角形子图集合的冗余,从而提高压缩算法的效率。

图3 原始网络结构

表1 原始网络节点重要性统计结果

表2 原始网络三角形子图个数

由表1、表2可知,NRSA算法计算出的低重要性节点为节点7、高重要性节点为节点4。此时低重要性节点标准low_percent=15%,高重要性节点标准high_percent=85%。图4所示为已经过滤掉高、低重要性节点后的网络,运用NIIET算法得到的三角形子图数量仅为15,如表3所示。三角形子图集合中仅包含7条冗余的边,表明过滤掉高、低重要性节点后,能以较小的计算代价得到一个具有较少冗余的三角形子图集合,并能依据三角形子图集合解析出一个压缩率较高的网络。

图4 节点过滤后的网络

表3 过滤后网络三角形子图个数

2.4 NIIET算法步骤

NIIET算法步骤如下:

输入复杂网络G(V,E),G的邻接列表AdjG

输出复杂网络G′(V′,E′),三角形子图集合Trangle_list

1)输入复杂网络G(V,E),采用NRSA算法计算出节点的重要性值。

2)设置low_percent和high_percent的百分比。

3)根据百分比筛选出低重要性节点集合low_nodelist和高重要性节点集合high_nodelist。

4)遍历边E,如果边两端的节点vi和vj位于低或者高重要性节点集合中,则从与它们相连节点的邻接列表中过滤掉vi和vj。

5)遍历边E,如果AdjG(vi)与AdjG(vj)相交,则三角形子图集合Trangle_list由节点vi和vj以及它们的共同节点集构成。

6)解析三角形子图集合Trangle_list,并构建出复杂网络G′(V′,E′)。

7)输出G′(V′,E′)和Trangle_list。

3 实验结果与分析

本文分别进行节点重要性和网络压缩分析,并选用6种真实网络来进行实验,分别为Zachary[14]、Football[15]、Neural[15]、Netscience[16]、Polblogs[15]以及Youtube[17]。网络参数由Gephi软件统计得出,如表4所示。实验的运行环境为Intel(R)Core(TM)2 Quad CPU Q8300@2.50 GHz,内存为16 GB,64位Win10的PC。

表4 不同网络的参数统计

3.1 节点重要性实验

为证明NRSA算法的合理性,本文使用SIR模型[18]对PageRank、LeaderRank和NRSA算法在Neural网络中进行传播实验。选取传播时间步为40,主要观察随着时间的变化,SIR模型中I(感染)状态的节点个数占网络总节点数的比例lin的变化情况。选取NRSA、LeaderRank、PageRank算法的前10%和20%的节点作为感染节点进行传播,Neural网络的感染实验结果如图5所示。图5中SIR模型的感染率Infect_rate为0.35,免疫率Res_rate为0.15。图5(a)、图5(b)是NRSA算法与LeaderRank算法的对比结果。从中可以看出,NRSA算法中lin的最高值均超过LeaderRank算法,并都接近0.8,说明NRSA算法选出的节点在相同时间步内传播的深度高于LeaderRank算法。从时间步上来看,在5～40时间步内,由于节点都从S(易感染)状态转变到I(感染)状态,而免疫率一直不变,2种算法的lin值差距不大。但从5～10时间步内的结果可得,NRSA算法的斜率高于LeaderRank算法,说明NRSA算法挑选出的节点的传播速度明显快于LeaderRank算法。综上,NRSA算法选出的节点要比LeaderRank算法选出的节点更为合理。同理,从图5(c)、图5(d)可以看出,NRSA算法的性能更优于PageRank算法。

图5 Neural网络传播仿真结果

3.2 压缩实验

压缩实验主要从节点选择标准和压缩效率这2个部分进行分析。由于NIIET算法采用过滤的方式来降低计算规模,因此需要分析高、低重要性节点选择标准对压缩结果的影响。本文将NIIET算法与Bound_tri、Node_iterator[19]、Edge_iterator_hash[20]、CABK算法从压缩率[5]、压缩时间和信息量保持率[21]等方面进行压缩分析。

3.2.1 节点选择标准的影响分析

节点选择标准的影响分析具体如下:

1)低重要性节点选择标准分析

在本文实验中,采用式(5)来分别计算节点压缩率和边压缩率。

(5)

其中,|V|和|V′|表示压缩前后的节点数量,|E|和|E′|表示压缩前后的边数量。

设置低重要性节点选择标准的范围为low_percent=[10%,30%],仿真节点压缩率、边压缩率与选择标准之间的关系,结果如图6所示。从图6可以看出,低重要性节点选择标准对点集压缩率和边集压缩率的影响非常小,原因是低重要性节点与其他节点之间的连接关系较少,使得这类节点不能构成三角形子图,从而不能参与三角形子图的计算。因此,低重要性节点选择标准对复杂网络压缩的影响可以忽略。

图6 低重要性节点选择标准分析

2)高重要性节点选择标准分析

高重要性节点选择标准直接影响NIIET算法的压缩率及压缩时间,并且压缩得到的三角形子图数量也会受此影响。因此,设置高重要性节点的选择标准范围为high_percent=[70%,90%],实验结果如图7所示。高重要性节点的选择标准设定越高,计算出的三角形子图数量也越多。但是,过多的三角形子图会导致压缩时间变长,因此,本文设置一个合适的过滤标准来提高压缩效率并减少压缩时间。从图7(a)、图7(b)中可以看出,在过滤标准的范围为[75%,85%]时,三角形子图的数量变化趋势不是很大,对应在图7(a)上的区间为[1,2],此范围内压缩率之间相差不大,即压缩率相对稳定,可以得到一个较平衡的三角形子图集合。

图7 高重要性节点选择标准分析

3.2.2 压缩效率对比分析

对压缩后的复杂网络进行量化估计,本文设置高重要性选择标准为high_percent=80%,低重要性选择标准为low_percent=10%,压缩效果对比如图8所示。由图8(a)、图8(b)可以得出,Node_iterator和Edge_iterator_hash的压缩率明显低于NIIET算法。原因是Node_iterator和Edge_iterator_hash算法需要网络中所有节点和边参与计算,它们虽能获得较多的三角形子图,但占用太多的压缩时间,压缩率较低。NIIET算法在压缩时间和压缩率上优于Bound_tri算法,由于Bound_tri算法在压缩前需访问邻接矩阵来确定节点之间的连边关系,然后修改邻接列表来减少网络规模,这种方式极大地增加了时间成本。此外,邻接矩阵会重复确认相连的节点,使计算后的集合中包含重复的三角形子图,导致Bound_tri算法的压缩率低于NIIET算法。

图8 4种算法压缩效果对比

此外,CABK算法依据节点的k-core值和阈值ks来处理节点,该方式所需的压缩时间远小于在网络中寻找三角形子图。但是,CABK算法的压缩率取决于阈值ks,通常情况下,ks选取的是k-core的平均值。若复杂网络中各节点的k-core值与ks相差不大,则CABK算法的压缩率要远低于NIIET算法。如Football数据集,各节点的k-core值与阈值ks相近,能处理的节点相对较少,导致压缩率低于0.1。而NIIET算法能在不同的数据集中列出三角形子图集合,因此,其不存在数据集的限制问题。

从图8(c)可以看出,经NIIET算法压缩后,网络的总信息量有所减少,但仍能保持在50%～70%,说明压缩后的网络还保留着原网络的大部分信息和结构,压缩结果合理且可信。

4 结束语

复杂网络规模的不断扩大使得用户难以从中获取有价值的信息。因此,本文提出一种过滤压缩算法NIIET,该算法以边为迭代对象,通过列出边两端的节点以及它们所拥有的共同节点集来对复杂网络进行压缩。在计算三角形子图集合之前,本文设计NRSA算法来选出高、低重要性节点,以过滤掉高、低重要性节点的方式来降低计算规模。实验结果表明,NRSA算法在无向和有向网络中的排序结果均合理且有效,NIIET算法的压缩率优于Node_iterator等算法,且其压缩后的网络仍能保持很高的信息量和大部分网络结构。下一步将从节点所处的位置、节点对网络功能的影响等不同角度,探究新的节点重要性排序方法,并基于三角形子图结构和复杂网络的k-core等其他性质,提出一种改进的复杂网络压缩算法。