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

doi:10.19678/j.issn.1000-3428.0054035

摘要/Abstract

摘要： 为高效地挖掘和分析复杂网络，提出一种基于三角形子图的复杂网络过滤压缩算法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

中图分类号:

TP391

吴涛, 任淑霞, 张书博. 基于三角形子图的复杂网络过滤压缩算法[J]. 计算机工程, 2020, 46(5): 70-77.

WU Tao, REN Shuxia, ZHANG Shubo. Complex Network Filtering and Compression Algorithm Based on Triangle Subgraph[J]. Computer Engineering, 2020, 46(5): 70-77.

https://www.ecice06.com/CN/Y2020/V46/I5/70

图/表 12

20200513200940

20200513200944

20200513200949

20200513200954

20200513200958

20200513201003

20200513201007

20200513201011

20200513201015

20200513201022

20200513201025

20200513201030

参考文献

[1] ZHANG Yu,LIU Yanbing,XIONG Gang,et al.Survey on succinct representation of graph data[J].Journal of Software,2014,25(9):1937-1952.(in Chinese)张宇,刘燕兵,熊刚,等.图数据表示与压缩技术综述[J].软件学报,2014,25(9):1937-1952.
[2] GILBERT A C,LEVCHENKO K.Compressing network graphs[C]//Proceedings of the 10th ACM Conference on KDD.New York,USA:ACM Press,2004:15-29.
[3] LI Tiantian,LU Gang,XU Nanshan,et al.Compressing layout algorithm for large complex network based on k-core[J].Computer Engineering,2016,42(5):308-312.(in Chinese)李甜甜,卢罡,许南山,等.基于k-core的大规模复杂网络压缩布局算法[J].计算机工程,2016,42(5):308-312.
[4] YAN J,ZHANG Z.Compressing big graph data:a relative node importance approach[C]//Proceedings of Conference on Wireless Communications and Signal Processing.Washington D.C.,USA:IEEE Press,2017:1-6.
[5] LI Hongbo,YANG Jing,BAI Jinbo,et al.Social network compression based on the importance of the community nodes[J].Acta Scientiarum Naturalium Universitatis Pekinensis,2013,49(1):117-125.(in Chinese)李泓波,杨静,白劲波,等.基于社区节点重要性的社会网络压缩方法[J].北京大学学报(自然科学版),2013,49(1):117-125.
[6] LI Zhenglian,JI Lixin,HUANG Ruiyang,et al.Hierarchical network compression algorithm based on splitting and merging unimportant nodes[J].Journal of Computer-Aided Design and Computer Graphics,2018,30(2):244-253.(in Chinese)李政廉,吉立新,黄瑞阳,等.基于非重要节点拆分融合的网络层次压缩算法[J].计算机辅助设计与图形学学报,2018,30(2):244-253.
[7] TOMÁS F,MOTWANI R.Clique partitions,graph compression and speeding-up algorithms[J].Journal of Computer and System Sciences,1995,51(2):261-272.
[8] HOLTEN D,WIJK J J V.Force-directed edge bundling for graph visualization[J].Computer Graphics Forum,2009,28(3):983-990.
[9] WANG Xiaohua,YANG Xinyan,JIAO Licheng.Compression of complex networks based on multiscale geometric analysis[J].Journal of Electronics and Information Technology,2009,31(4):968-972.(in Chinese)王晓华,杨新艳,焦李成.基于多尺度几何分析的复杂网络压缩策略[J].电子与信息学报,2009,31(4):968-972.
[10] ZHANG L,XU C,QIAN W,et al.Common neighbor query-friendly triangulation-based large-scale graph compression[M].Berlin,Germany:Springer,2014.
[11] WANG Lin,RAO Renjie.Multi-label propagation algorithm for overlapping community detection based on LeaderRank and node similarity[J].Computer Systems Applications,2018,27(6):146-150.
[12] HAN Zhongming,CHEN Yan,LI Mengqi,et al.An efficient node influence metric based on triangle in complex networks[J].Acta Physica Sinica,2016,65(16):168901.
[13] HU X,TAO Y,CHUNG C W.I/O-efficient algorithms on triangle listing and counting[J].ACM Transactions on Database Systems,2014,39(4):1-30.
[14] ZHU Z,LIN S,CUI K,et al.Network topology layout algorithm based on community detection of complex networks[J].Journal of Computer-Aided Design and Computer Graphics,2011,23(11):1808-1815.
[15] ZHOU Xian,LIANG Xiao,HUANG Tinglei.Time-varying complex network layout algorithm based on node centrality[J].Systems Engineering and Electronics,2017,39(10):2346-2352.
[16] TU Jing,YANG Zhonghua,ZHANG Zhiqing.Influence of knowledge source centrality on knowledge diffusion efficiency in S&T collaboration network[J].Information Studies:Theory and Application,2017(5):80-85.(in Chinese)涂静,杨中华,张志清.科研合作网络中知识源中心性对知识扩散效率的影响[J].情报理论与实践,2017(5):80-85.
[17] TANG Lei,LIU Huan.Uncovering cross-dimension group structures in multi-dimensional networks[C]//Proceedings of SDM Workshop on Analysis of Dynamic Networks.New York,USA:ACM Press,2009:568-575.
[18] HU Baoan,LI Bing,LI Yaling.SIR computer virus propagation model with time delay[J].Computer Engineering,2016,42(5):168-172.(in Chinese)胡宝安,李兵,李亚玲.具有时滞的SIR计算机病毒传播模型[J].计算机工程,2016,42(5):168-172.
[19] LATAPY M.Main-memory triangle computations for very large(sparse (power-law)) graphs[J].Theoretical Computer Science,2008,407(1/2/3):458-473.
[20] SCHANK T,WAGNER D.Finding,counting and listing all triangles in large graphs,an experimental study[J].Lecture Notes in Computer Science,2005,35(3):606-609.
[21] QIU Hua.Research on complex network visualization technology based on compression and cluster analysis[D].Zhenjiang:Jiangsu University,2017.(in Chinese)仇桦.基于压缩与聚类分析的复杂网络可视化技术研究[D].镇江:江苏大学,2017.

选择文件类型/文献管理软件名称

选择包含的内容