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

Complex Network Filtering and Compression Algorithm Based on Triangle Subgraph

作　　者：吴涛[1] 任淑霞[1] 张书博 WU Tao;REN Shuxia;ZHANG Shubo(School of Computer Science and Technology,Tiangong University,Tianjin 300387,China)

机构地区：[1]天津工业大学计算机科学与技术学院,天津300387

出　　处：《计算机工程》2020年第5期70-77,共8页Computer Engineering

基　　金：国家自然科学基金(61403278)。

摘　　要：为高效地挖掘和分析复杂网络,提出一种基于三角形子图的复杂网络过滤压缩算法NIIET。设计一种节点重要性排序算法NRSA选取高、低重要性节点并进行过滤,以降低计算规模并缩短压缩时间。列出边两端的节点及其共同节点集组成三角形子图集合,在此基础上,解析三角形子图集合完成复杂网络压缩。实验结果表明,NRSA算法的排序结果合理且可靠,相对Node_iterator算法,NIIET算法能够缩短压缩时间,提高压缩率,且能保留原网络的大部分结构和信息。In order to efficiently excavate and analyze the complex network,this paper proposes NIIET,a new filtering and compression algorithm for complex network based on triangle subgraph.NRSA,a node importance ranking algorithm is designed to select nodes with high and low importance,which are then filtered to reduce computing scale and compression time.The nodes at both ends of the edge and their common nodes are listed to form the triangle subgraph set.On this basis,the compression of complex network is accomplished by analyzing the triangle subgraph set.Experimental results show that the ranking of NRSA algorithm is reasonable and reliable.Compared with the Node_iterator algorithm,the NIIET algorithm can shorten the compression time,improve compression rate and retain most of the structure and information of the original network.

关 键 词：复杂网络 节点重要性排序 三角形子图 过滤压缩 SIR模型 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]