基于三角形子图的复杂网络过滤压缩算法
发布时间：2021-08-15 06:23
为高效地挖掘和分析复杂网络,提出一种基于三角形子图的复杂网络过滤压缩算法NIIET。设计一种节点重要性排序算法NRSA选取高、低重要性节点并进行过滤,以降低计算规模并缩短压缩时间。列出边两端的节点及其共同节点集组成三角形子图集合,在此基础上,解析三角形子图集合完成复杂网络压缩。实验结果表明,NRSA算法的排序结果合理且可靠,相对Nodeiterator算法,NIIET算法能够缩短压缩时间,提高压缩率,且能保留原网络的大部分结构和信息。
【文章来源】：计算机工程. 2020,46(05)北大核心CSCD
【文章页数】：8 页
【部分图文】：
简单无向网络示意图
由图2可以看出,节点重要性值的分布十分不均匀,多数节点的重要性非常低,小部分节点的重要性很高。特别地,高重要性与低重要性节点之间含有的共同邻接节点非常少,但寻找它们之间的三角形子图却占用大量的计算时间。因此,在计算三角形子图前过滤掉高、低重要性节点,可以减小计算规模,且能避免较高的计算代价,从而得到高效的三角形子图集合。本文将带过滤性质的三角形子图压缩算法定义为NIIET(Node Importance In Edge Triangle)。NIIET算法在压缩时只需要访问邻接列表,邻接列表中包含边的方向性,可应用于有向图和无向图。图3是一个包含8个节点、16条边的简单无向网络图,其中,线上数字表示线的编号。如表1、表2所示,边迭代算法可以得到一个包含42个三角形的三角形子图集合,会产生27条边的冗余。假如存储一个三角形子图的边需要2个单位,则会产生54个单位的冗余。因此,可以通过过滤掉高、低重要性节点来降低三角形子图集合的冗余,从而提高压缩算法的效率。
图3是一个包含8个节点、16条边的简单无向网络图,其中,线上数字表示线的编号。如表1、表2所示,边迭代算法可以得到一个包含42个三角形的三角形子图集合,会产生27条边的冗余。假如存储一个三角形子图的边需要2个单位,则会产生54个单位的冗余。因此,可以通过过滤掉高、低重要性节点来降低三角形子图集合的冗余,从而提高压缩算法的效率。表1 原始网络节点重要性统计结果Table 1 Statistic results of original network node importance 节点 重要性值 节点 重要性值 4 1.000 000 000 00 2 0.630 033 038 70 0 0.772 326 740 38 6 0.424 424 327 58 1 0.772 326 740 38 5 0.195 828 400 67 3 0.763 622 551 24 7 0.000 000 000 00
【参考文献】：
期刊论文
[1]基于LeaderRank和节点相似性的多标签传播重叠社团挖掘算法[J]. 王林,饶仁杰. 计算机系统应用. 2018(06)
[2]基于非重要节点拆分融合的网络层次压缩算法[J]. 李政廉,吉立新,黄瑞阳,刘树新. 计算机辅助设计与图形学学报. 2018(02)
[3]基于节点中心性的时变复杂网络布局算法[J]. 周弦,梁霄,黄廷磊. 系统工程与电子技术. 2017(10)
[4]科研合作网络中知识源中心性对知识扩散效率的影响[J]. 涂静,杨中华,张志清. 情报理论与实践. 2017(05)
[5]一种有效的基于三角结构的复杂网络节点影响力度量模型[J]. 韩忠明,陈炎,李梦琪,刘雯,杨伟杰. 物理学报. 2016(16)
[6]基于k-core的大规模复杂网络压缩布局算法[J]. 李甜甜,卢罡,许南山,郭俊霞. 计算机工程. 2016(05)
[7]具有时滞的SIR计算机病毒传播模型[J]. 胡宝安,李兵,李亚玲. 计算机工程. 2016(05)
[8]图数据表示与压缩技术综述[J]. 张宇,刘燕兵,熊刚,贾焰,刘萍,郭莉. 软件学报. 2014(09)
[9]基于社区节点重要性的社会网络压缩方法[J]. 李泓波,张健沛,杨静,白劲波,初妍,张乐君. 北京大学学报(自然科学版). 2013(01)
[10]基于多尺度几何分析的复杂网络压缩策略[J]. 王晓华,杨新艳,焦李成. 电子与信息学报. 2009(04)
硕士论文
[1]基于压缩与聚类分析的复杂网络可视化技术研究[D]. 仇桦.江苏大学 2017
本文编号：3344033
【文章来源】：计算机工程. 2020,46(05)北大核心CSCD
【文章页数】：8 页
【部分图文】：
简单无向网络示意图
由图2可以看出,节点重要性值的分布十分不均匀,多数节点的重要性非常低,小部分节点的重要性很高。特别地,高重要性与低重要性节点之间含有的共同邻接节点非常少,但寻找它们之间的三角形子图却占用大量的计算时间。因此,在计算三角形子图前过滤掉高、低重要性节点,可以减小计算规模,且能避免较高的计算代价,从而得到高效的三角形子图集合。本文将带过滤性质的三角形子图压缩算法定义为NIIET(Node Importance In Edge Triangle)。NIIET算法在压缩时只需要访问邻接列表,邻接列表中包含边的方向性,可应用于有向图和无向图。图3是一个包含8个节点、16条边的简单无向网络图,其中,线上数字表示线的编号。如表1、表2所示,边迭代算法可以得到一个包含42个三角形的三角形子图集合,会产生27条边的冗余。假如存储一个三角形子图的边需要2个单位,则会产生54个单位的冗余。因此,可以通过过滤掉高、低重要性节点来降低三角形子图集合的冗余,从而提高压缩算法的效率。
图3是一个包含8个节点、16条边的简单无向网络图,其中,线上数字表示线的编号。如表1、表2所示,边迭代算法可以得到一个包含42个三角形的三角形子图集合,会产生27条边的冗余。假如存储一个三角形子图的边需要2个单位,则会产生54个单位的冗余。因此,可以通过过滤掉高、低重要性节点来降低三角形子图集合的冗余,从而提高压缩算法的效率。表1 原始网络节点重要性统计结果Table 1 Statistic results of original network node importance 节点 重要性值 节点 重要性值 4 1.000 000 000 00 2 0.630 033 038 70 0 0.772 326 740 38 6 0.424 424 327 58 1 0.772 326 740 38 5 0.195 828 400 67 3 0.763 622 551 24 7 0.000 000 000 00
【参考文献】：
期刊论文
[1]基于LeaderRank和节点相似性的多标签传播重叠社团挖掘算法[J]. 王林,饶仁杰. 计算机系统应用. 2018(06)
[2]基于非重要节点拆分融合的网络层次压缩算法[J]. 李政廉,吉立新,黄瑞阳,刘树新. 计算机辅助设计与图形学学报. 2018(02)
[3]基于节点中心性的时变复杂网络布局算法[J]. 周弦,梁霄,黄廷磊. 系统工程与电子技术. 2017(10)
[4]科研合作网络中知识源中心性对知识扩散效率的影响[J]. 涂静,杨中华,张志清. 情报理论与实践. 2017(05)
[5]一种有效的基于三角结构的复杂网络节点影响力度量模型[J]. 韩忠明,陈炎,李梦琪,刘雯,杨伟杰. 物理学报. 2016(16)
[6]基于k-core的大规模复杂网络压缩布局算法[J]. 李甜甜,卢罡,许南山,郭俊霞. 计算机工程. 2016(05)
[7]具有时滞的SIR计算机病毒传播模型[J]. 胡宝安,李兵,李亚玲. 计算机工程. 2016(05)
[8]图数据表示与压缩技术综述[J]. 张宇,刘燕兵,熊刚,贾焰,刘萍,郭莉. 软件学报. 2014(09)
[9]基于社区节点重要性的社会网络压缩方法[J]. 李泓波,张健沛,杨静,白劲波,初妍,张乐君. 北京大学学报(自然科学版). 2013(01)
[10]基于多尺度几何分析的复杂网络压缩策略[J]. 王晓华,杨新艳,焦李成. 电子与信息学报. 2009(04)
硕士论文
[1]基于压缩与聚类分析的复杂网络可视化技术研究[D]. 仇桦.江苏大学 2017
本文编号：3344033
本文链接：https://www.wllwen.com/kejilunwen/yysx/3344033.html
