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

摘要

压缩复杂网络的数据对于可视化非常重要。基于复杂网络中的三角形子图结构，提出了基于三角形子图的复杂网络滤波压缩算法。该算法从边开始，列出边的节点及其共同节点集，形成三角形子图集，对三角形子图集进行解析，构造新的复杂网络来完成压缩。在计算三角子图集合之前，提出节点重要性排序算法，提取高重要性节点和低重要性节点，并对其进行过滤，以减少复杂网络的计算规模。实验结果表明，滤波压缩算法在提高压缩率的同时，保留了原始网络的信息;排序结果分析和SIR模型分析表明，节点重要性排序算法的排序结果具有准确性和合理性。

1.介绍

一些网络包含数百万甚至数十亿的节点和边，这给理解和分析复杂网络带来了新的挑战。如果不压缩，所呈现的点和边会非常密集，人们很难从网络中获取有用的信息。

学者开始关注复杂网络的压缩场[1并设计了许多方法来压缩复杂的网络。吉尔伯特(2]提出了一种基于节点重要性评价指标的节点压缩算法，该算法通过删除非关键节点和边缘来达到压缩网络的目的。缺点是采用keep-one和keep-all策略对重要节点和边进行补充，耗费大量时间。燕和张3.而其他的则受到了可以强调重要节点的中心性的启发。从随机中心性、度中心性、相对节点重要性、PageRank和中间中心性五个方面提出了5种压缩方案。缺点是删除节点和边缘，不考虑新网络的补充，导致网络信息的丢失。Zhang等[4]提出了一种基于三角形结构的bound_tri算法。该算法从节点开始，通过构造三角形集对网络进行压缩。缺点是需要同时访问邻接矩阵和邻接表，时间复杂度高，而bound_tri算法以程度作为选择准则，不符合网络的实际情况。

上述算法主要从节点开始，采用删除节点和合并节点的方式来实现对复杂网络的压缩。基于边缘，提出了基于三角形子图的复杂网络过滤和压缩算法。为了缩短压缩时间，提高压缩效率，在计算三角形子图集之前，本文提出节点影响作为全局重要性测度，并提出基于LeaderRank算法的节点重要性排序算法NRSA (node Rank Select) [5来提取高重要性节点和低重要性节点，并对它们进行过滤，以减少需要计算的复杂网络的规模。实验结果表明，NRSA算法的重要节点排序结果优于其他排序算法，压缩算法提高了压缩效率，并保留了原始网络的大部分信息。

2.NRSA算法

在LeaderRank算法中，跳跃到相邻节点的概率是根据每个节点的程度来计算的。计算方法只考虑了节点的局部重要性，忽略了整个网络的全局重要性。

从图中可以看出1即节点4比节点7有更多的邻接节点，且每次由LeaderRank算法迭代分配给节点4的LR值都大于节点7。因此，LeaderRank算法的结果是节点4比节点7更重要。但是从网络结构来看，节点7是连接三个不同的节点群的中间节点，在整个网络结构中应该是最重要的。为了综合考虑节点的局部重要性和全局重要性，使用邻接度来构造节点的影响力作为全局重要性。

定义1。Adjacent-degree:为网络G中的节点;邻接度为所有相邻节点度数之和，记为AdjDe。

定义2。节点影响:节点的影响邻接度的和和程度的 ．它被记录为Node_In ．

定义3。节点等级:NR的计算公式_我的节点如下: 方程3.显示(1)一个_我相邻节点是否与节点相连 ．相邻节点数量越多，节点NR值越高 ，满足直觉判断。(2)节点对节点的影响越大 ，的LR值越大获得的 ． 在网络结构中更为重要。
NRSA算法的步骤如下:（1）采用LeaderRank算法计算复杂网络节点的LR值（2）节点的邻接度的计算公式(1)和(2)，节点影响Node_Ef获得（3）使用方程(3.), LR_我价值和Node_Ef计算得到NR_我，使用偏差标准化将结果映射到[0,1]区间

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

３．１．Triangle-Subgraph

Triangle-subgraph [6是图数据连通子图中特殊的3连通子图。在复杂网络中G = (V，E）， 可以表示一个有三个节点和三条边的三角形子图:

对Ge边，计算三角形子图所需的时间为［7，表示三角形子图可以在一定时间内计算出来。

３.２．Triangle-Subgraph列表

列出三角形子图的传统方法是节点压缩算法[8］.本文提出的算法是一种边缘压缩算法。首先，从复杂网络中随机选取一条边，然后搜索与该边相连的两个节点的邻接表，检查它们是否有共同的邻接节点，最后将它们与共同的邻接节点组合成三角形子图集。例如，选中的边为(a, b)，与该边相连的节点邻接表为 和 ．结点a和b的公共相邻结点是 ．边(a, b)的所有三角形子图集合为

３．３．具有滤波特性的三角形子图压缩算法

从复杂网络的真实数据集Polblogs和Youtube的节点重要性值统计图，图2说明两图有一个重要的特征，即复杂网络中节点重要性值分布非常不均匀。此外，在高重要性节点和低重要性节点之间可以包含的常见相邻节点非常少。但是，在高重要性节点和低重要性节点之间寻找三角形子图会消耗大量的计算资源。因此，在计算三角子图之前，采用过滤高重要性节点和低重要性节点的方法来减少复杂网络中的数据量。

我们提出并定义了具有滤波特性的三角形子图压缩算法为NIIET(节点重要性边三角形)算法。NIIET算法在压缩复杂网络时，只需要访问复杂网络的邻接表。邻接表包含了边的方向性，可以应用于有向图和无向图的压缩。

数字3.是一个简单的无向网络图，包含16条边和8个节点。边缘压缩算法得到的结果如表所示1．它可以得到一个由42个三角形组成的三角形子图集，从而产生27条边的冗余。如果存储三角形子图的边需要2个单位，则需要存储54个单位的冗余。因此，通过过滤高重要性节点和低重要性节点，降低了三角形子图集的冗余度和压缩效率。

首先，NRSA算法计算得到的节点重要性如表所示2．接下来，设置低重要性节点标准low_percent = 15%，高重要性节点标准high_percent = 85%。低重要性节点为节点7，高重要性节点为节点4。最后，在列出三角形子图时，从其他节点的邻接表中过滤出包含节点7和节点4的信息。对高重要性节点和低重要性节点进行过滤后的网络如图所示4．计算结果见表3.．只有15个三角形子图，并且三角形子图集只包含7条冗余边。结果表明，通过对低重要性节点和高重要性节点进行滤波，可以得到一个具有较高压缩率的复杂网络。

3．4．niet算法的步骤

输入:复杂网络G（V，E)，邻接表输出:复杂网络G’（V '，E”), triangle-subgraph集trangle_list．(1)输入复杂的网络G（V，E)，并使用NRSA算法计算节点值;(2)设置low_percent和high_percent的百分比;(3)根据百分比得到低重要性节点集low_nodelist和高重要性节点集high_nodelist;(4)遍历的边缘E．如果节点和边缘两端位于low_nodelist或high_nodelist，则从邻接表中过滤出两个节点的信息和连接节点;(5)E.如果和AdjG相交，三角形子图集trangle_list由节点组成和以及它们共同的节点集;(6)解析三角形子图集trangle_list，构造新的复杂网络G”(V”,E”);(7)输出G”(V”,E')，三角形子图集trangle_list。

4.实验分析

本文分别对节点重要性实验和压缩实验进行了分析，选取Zachary [9[],足球10,神经10], Netscience [11], Polblogs [12和Youtube [13进行实验。

4．1.节点的重要性分析

为了进一步证明NRSA算法的合理性，SIR模型[14]用于传播神经网络中PageRank、LeaderRank和NRSA算法的节点重要性排序结果。lin的变化主要表现为SIR模型中处于I(感染)状态的节点数与网络中总节点数的比值。选择NRSA算法、LeaderRank算法和PageRank算法中排名前10%的节点和排名前20%的节点作为感染节点进行传播。神经网络感染实验结果如图所示5．

从图中可以看出5(一个)∼5 (b)， NRSA算法的lin的最大值超过了LeaderRank算法，两者都接近0.8。结果表明，NRSA算法选择的节点在同一时间步长内传播到比LeaderRank更高的深度。从上面的时间步来看，在5步和40步之间，两种算法的lin值相差不大。但从5-10周期可以看出，NRSA算法的斜率大于后者，说明NRSA算法选择的节点比LeaderRank算法的传播速度更快。一般来说，NRSA算法选择的节点比LeaderRank算法选择的节点更合理。同样，从图中NRSA算法和PageRank算法的比较可以看出5 (c)∼5 (d)， NRSA算法优于PageRank算法。

4．2．压缩实验分析

压缩实验分析主要从节点选择和压缩两部分进行。由于NIIET算法使用过滤来减小计算规模，因此选择重要性低和高的节点都会影响复杂网络的压缩结果。因此，有必要分析高重要性节点选择准则和低重要性节点选择准则对压缩结果的影响。同时，NIIET算法和bound_tri [4], edge_iterator_hash [15，和node_iterator [8]，用以从压缩率方面分析压缩效率[16]、压缩时间和信息保留率[17］.

4.2.1。准备节点选择准则对压缩结果的影响分析

(1)低重要性节点选择标准影响．方程(5)表示节点压缩比。具体公式如下:

在上述公式中，和压缩前后的节点数。

在本实验中，设置低重要性节点选择准则的范围为low_percent =[10%， 30%]，点压缩比与低重要性节点选择准则的关系如图所示6．可以看出，该准则对点集压缩率的影响很小，因为低重要性节点的节点与其他节点的连接关系很小，不能参与三角形子图的计算。因此，可以忽略低重要性节点选择准则对复杂网络压缩比的影响。

(2)高重要性节点选择标准影响．如图所示7 (b)，也增加了用复杂网络计算三角形子图的数量。但是，对于太多的三角形子图，需要计算的节点和边越多，压缩时间就越长。我们将考虑设置滤波准则来提高复杂网络的压缩效率和压缩时间。数据7(一)和7 (b)表明当过滤条件的范围为[75%，85%]时，过滤条件的范围不是很大。同时，对应的范围如图所示7(一)是(1，2，在此范围内压缩比相差不大，且压缩比相对稳定，从而得到三角形子图的平衡集。

4.2.2。压缩效率比较结果分析

对于压缩后的复杂网络的定量估计，本文以网络信息的保留率作为评价标准。同时设置实验的高重要性节点选择标准为high_percent = 85%，低重要性节点选择标准为low_percent = 10%。压缩效果对比图如图所示8．

通过观察图8(一个)，从压缩比的角度来看，由于node_iterator和edge_iterator_hash这两种压缩算法需要复杂网络中所有节点和边都参与到三角子图的计算中来，与前两种压缩算法相比，它们可以获得更多的三角子图，但压缩比是最低的。

同时，NIIET算法在压缩比上优于bound_tri算法。由于bound_tri算法在压缩前需要访问复杂网络的邻接矩阵，确定节点之间的边关系，然后访问和修改邻接表，压缩方法大大增加了时间复杂度。而且，邻接矩阵反复确认两个连接节点，导致计算出的三角形子图集中出现一个重复的三角形子图，降低了bound_tri算法的压缩比。

最后，从图中可以看出8 (b)NIIET算法过滤高重要性节点和低重要性节点，减少压缩时间，提高压缩率，但压缩后的网络仍能保持50%-70%的网络信息。结果表明，NIIET算法对网络信息量保持了良好的效果，压缩结果合理可信。

5.结论

本文提出了NIIET算法，该算法以边为迭代对象，通过列出三角形子图来压缩复杂网络。在计算三角形子图集之前，本文提出了NRSA算法计算高重要性节点和低重要性节点。通过过滤高重要性节点和低重要性节点来减小邻接表的大小。实验结果表明，NRSA算法是合理的。NIIET算法在压缩率上优于其他算法，压缩后的网络仍能保持较高的信息量，这足以说明压缩后的网络保留了复杂网络的大部分结构。

在下一阶段的工作中，本文将从两个方面着手:(1)从节点的位置角度出发，研究节点对网络功能的影响[18探讨节点重要性排序的新方法。(2)基于复杂网络的三角形子图结构等特性，提出新的复杂网络压缩算法。

数据可用性

如有要求，通讯作者将提供资料。

的利益冲突

作者声明他们没有利益冲突。

参考文献

1. 余张,Y.-B。刘国雄等，“图形数据的简洁表示研究综述”，软件学报，第9卷，1937-1952页，2014年。视图:谷歌学者
2. 吉尔伯特和列夫钦科，“压缩网络图”，在第十届美国计算机学会KDD会议LinkKDD研讨会论文集2004年，中国苏州。视图:谷歌学者
3. 严俊，“大图数据的压缩:一种相对节点重要性的方法”2017第九届无线通信与信号处理国际会议论文集， pp. 1-6，中国南京，2017年10月。视图:谷歌学者
4. 张磊，徐灿，钱伟，“基于共同近邻查询的三角形大规模图数据压缩”，出版Web信息系统工程2014， pp. 234-243，施普林格，柏林，德国，2014。视图:出版商的网站|谷歌学者
5. L. Wang和R. Rao，“基于LeaderRank和节点相似度的重叠社区检测多标签传播算法”，计算机系统应用第27卷第2期第6页，146-150页，2018。视图:谷歌学者
6. Z.-M。韩春燕，李梦琪，文磊，文杰。Yang，“复杂网络中基于三角形的有效节点影响度量”，《物理学报》，第65卷，第5期16日,2016年。视图:谷歌学者
7. M. Latapy，“大型(稀疏(幂律))图的主记忆三角形计算”，理论计算机科学，第407卷，第5期。1-3，第458-473页，2008。视图:出版商的网站|谷歌学者
8. a . Itai和M. Rodeh，《在图中寻找最小电路》，SIAM计算杂志，第7卷，第5期4、1978年。视图:出版商的网站|谷歌学者
9. “基于社区检测的复杂网络拓扑布局算法”计算机辅助设计与计算机图形学杂志，第23卷，第2期。11，第1808-1815页，2011。视图:谷歌学者
10. “基于节点中心性的时变复杂网络布局算法”，系统工程与电子学第39卷第3期10, pp. 2346-2352, 2017。视图:谷歌学者
11. 朱新民，“基于社区结构的影响力节点分析”，计算机应用研究第34卷第3期9、pp. 2582-2585, 2017。视图:谷歌学者
12. A. Lada和G. Natalie，“政治博客圈和2004年美国大选”，刊于第三届链路发现国际研讨会论文集，页36-43，纽约，纽约，美国，2005。视图:谷歌学者
13. 唐磊，“多维网络中跨维群结构的研究”，发表于动态网络分析SDM研讨会，第568-575页，Sparks, NV, USA, 2009。视图:谷歌学者
14. 王璐，“基于加权非线性方法的节点重要性测量”，《中国机械工程》，计算机应用研究， 2018年第5期。视图:谷歌学者
15. T. Schank和D. Wagner，“在大型图表中发现、计数和列出所有三角形，一项实验研究，”实验和高效算法，第3503卷，第606-609页，2005。视图:出版商的网站|谷歌学者
16. 张建军，杨建军，张林，“基于社区节点重要性的社交网络压缩”，《中国社交网络学报》，2014年第4期。北京大学自然科学学报，第49卷，第49期。1, pp. 117-125, 2013。视图:谷歌学者
17. h .周基于压缩聚类分析的复杂网络可视化技术研究，江苏大学，镇江，2017。
18. 陈晓龙，“复杂网络中节点排序研究综述”，科学通报，第59卷，第59期13，页1175,2014。视图:谷歌学者

版权

版权所有©2020任淑霞等。这是一篇发布在知识共享署名许可协议，允许在任何媒介上不受限制地使用、传播和复制，但必须正确引用原作。