大规模网络图中4节点子图数量快速估计算法

• 作者: 孙雨 李国栋 覃遵颖 陶敬 齐怀睿
• 来源期刊: 西安交通大学学报
• 关键词: 网络图 采样算法 子图数量估计
• 年，卷（期）: 2018,（12）
• 页码范围: 57-62
• 页数: 6页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.7652/xjtuxb201812009

摘要

针对大规模网络图中存在的大量4节点子图数量难以精确统计分析的问题,提出了一种大规模网络图中4节点子图数量快速估计算法(SmartMoss).该算法通过随机变量方差分析技术对比3路径采样算法(3PS)和中心3路径采样算法(C3PS)两种前沿算法的估计误差得出其各自不同的适用范围,进而通过计算被测网络图权重密度分布与误差实时选择使用3PS算法或C3PS算法对网络图中4节点子图进行快速采样,通过采样比例混合3PS算法与C3PS算法的估计结果实现对网络图中各4节点子图出现数量的快速估计.实验结果表明,在同等估计误差下提出的Smart-Moss算法比已有3PS算法和C3PS算法快10倍以上.SmartMoss算法可以实现对大规模网络图中4节点子图数量进行快速准确的估计,同时为网络社团演化和恶意代码检测等实际应用提供一定的理论参考.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李国栋	西安交通大学智能网络与网络安全教育部重点实验室	18	107	5.0	10.0
5	孙雨	西安交通大学智能网络与网络安全教育部重点实验室	2	14	1.0	2.0
9	覃遵颖	西安交通大学智能网络与网络安全教育部重点实验室	7	6	1.0	2.0
13	齐怀睿	西安交通大学电子与信息工程学院	1	0	0.0	0.0