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

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