计算机工程 ›› 2020, Vol. 46 ›› Issue (5): 70-77.doi: 10.19678/j.issn.1000-3428.0054035

• 人工智能与模式识别 • 上一篇    下一篇

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

吴涛, 任淑霞, 张书博   

  1. 天津工业大学 计算机科学与技术学院, 天津 300387
  • 收稿日期:2019-02-27 修回日期:2019-04-19 发布日期:2020-05-08
  • 作者简介:吴涛(1995-),男,硕士研究生,主研方向为数据挖掘、复杂网络;任淑霞,副教授、博士;张书博,硕士研究生。
  • 基金项目:
    国家自然科学基金(61403278)。

Complex Network Filtering and Compression Algorithm Based on Triangle Subgraph

WU Tao, REN Shuxia, ZHANG Shubo   

  1. School of Computer Science and Technology, Tiangong University, Tianjin 300387, China
  • Received:2019-02-27 Revised:2019-04-19 Published:2020-05-08

摘要: 为高效地挖掘和分析复杂网络,提出一种基于三角形子图的复杂网络过滤压缩算法NIIET。设计一种节点重要性排序算法NRSA选取高、低重要性节点并进行过滤,以降低计算规模并缩短压缩时间。列出边两端的节点及其共同节点集组成三角形子图集合,在此基础上,解析三角形子图集合完成复杂网络压缩。实验结果表明,NRSA算法的排序结果合理且可靠,相对Node_iterator算法,NIIET算法能够缩短压缩时间,提高压缩率,且能保留原网络的大部分结构和信息。

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

Abstract: 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.

Key words: complex network, node importance ranking, triangle subgraph, filtering and compression, SIR model

中图分类号: