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

覃遵颖 1; 孙雨 1; 李国栋 1; 2; 齐怀睿 3; 陶敬 1; 2

doi:10.7652/xjtuxb201812009

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2025-05-08

- 大规模网络图中4节点子图数量快速估计算法
- A Fast Mining Algorithm for 4-Node Graphlets in Large Graphs
- 西安交通大学学报 2018年52卷第12期页码：57-62
- 作者机构：
  
  1. 西安交通大学智能网络与网络安全教育部重点实验室,西安,710049
  2. 西安交通大学网络信息中心,西安,710049
- 作者简介：
- 基金信息：
  
  : 2017-10-28。作者简介: 覃遵颖(1985-),女,工程师;陶敬(通信作者),男,高级工程师,硕士生导师。基金项目: 深圳市基础研究计划资助项目(JCYJ20160229195940462);陕西省自然科学基础研究计划资助项目(2016JQ6034,2017JM6095);浙江省自然科学基金资助项目(LGG18F020016)
- DOI：10.7652/xjtuxb201812009
  中图分类号： TP301.6
- 网络首发：2018-12-10，
  
  纸质出版：2018
- 稿件说明：
移动端阅览
覃遵颖 1, 孙雨 1, 李国栋 1, 等. 大规模网络图中4节点子图数量快速估计算法[J]. 西安交通大学学报, 2018,52(12):57-62.

A Fast Mining Algorithm for 4-Node Graphlets in Large Graphs[J]. 2018, 52(12): 57-62.
覃遵颖 1, 孙雨 1, 李国栋 1, 等. 大规模网络图中4节点子图数量快速估计算法[J]. 西安交通大学学报, 2018,52(12):57-62. DOI： 10.7652/xjtuxb201812009.

A Fast Mining Algorithm for 4-Node Graphlets in Large Graphs[J]. 2018, 52(12): 57-62. DOI： 10.7652/xjtuxb201812009.

摘要

针对大规模网络图中存在的大量4节点子图数量难以精确统计分析的问题

提出了一种大规模网络图中4节点子图数量快速估计算法(SmartMoss)。该算法通过随机变量方差分析技术对比3路径采样算法(3PS)和中心3路径采样算法(C3PS)两种前沿算法的估计误差得出其各自不同的适用范围

进而通过计算被测网络图权重密度分布与误差实时选择使用3PS算法或C3PS算法对网络图中4节点子图进行快速采样

通过采样比例混合3PS算法与C3PS算法的估计结果实现对网络图中各4节点子图出现数量的快速估计。实验结果表明

在同等估计误差下提出的SmartMoss算法比已有3PS算法和C3PS算法快10倍以上。SmartMoss算法可以实现对大规模网络图中4节点子图数量进行快速准确的估计

同时为网络社团演化和恶意代码检测等实际应用提供一定的理论参考。

Abstract

A fast method(SmartMoss)for efficiently estimating the frequencies of 4-node graph-lets in large-scale networks is proposed to address the challenge of exactly counting the frequencies of 4-node graphlets occurring in large-scale networks. SmartMoss compares the estimation errors of the two state-of-the-art algorithms

3PS(3-Path Sampling)and C3PS(Center 3-Path Sampling)

through random variables variance analysis to obtain their different application ranges

and then selects either 3PS algorithm or C3PS algorithm for 4-node graphlets sampling by calculating the distribution of network weight densities and real-time errors

to achieve quick estimation of the frequencies of 4-node graphlets by combing the estimation results of 3PS and C3PS based on the sampling proportions. Experimental results show that SmartMoss is more than 10 times faster than the state-of-the-art algorithms 3PS and C3PS under the same estimation error. SmartMoss efficiently and accurately estimates the frequencies of 4-node graph-lets for large network graphs

and provides theoretical reference for practical applications such as network community evolution and malicious code detection.

关键词

Keywords

references

SHAI S, RON M, SHMOOLIK M, et al. Network motifs in the transcriptional regulation network of escherichia coli [J]. Nature Genetics, 2002, 31(1): 64-68.

谢莹, 吴建国, 李炜, 等. 基于gSpan算法的未知化合物毒性预测 [J]. 合肥工业大学学报(自然科学版), 2007, 30(10): 1278-1280.

XIE Ying, WU Jianguo, LI Wei, et al. Predicting the toxicity of unknown chemicals based on gSpan algorithm [J]. Journal of Hefei University of Technology(Natural Science), 2007, 30(10): 1278-1280.

CHUN H, KWAK H, EOM Y H, et al. Comparison of online social relations in terms of volume vs interaction: a case study of Cyworld [C]∥Proceedings of the ACM SIGCOMM Conference on Internet Measurement. New York, USA: ACM, 2008: 57-70.

KUNEGIS J, LOMMATZSCH A, BAUCKHAGE C. The slashdot zoo: mining a social network with negative edges [C]∥Proceedings of the 18th International Conference on World Wide Web. New York, USA: ACM, 2009: 741-750.

ZHAO Junzhou, LUI J C S, TOWSLEY D, et al. Empirical analysis of the evolution of follower network: a case study on Douban [C]∥Proceedings of the 2011 IEEE Conference on Computer Communications Workshops. Piscataway, NJ, USA: IEEE, 2011: 941-946.

UGANDER J, BACKSTROM L, KLEINBERG J. Subgraph frequencies: mapping the empirical and extremal geography of large graph collections [C]∥Proceedings of the 22nd Inlernational Conference on World Wide Web. New York, USA: ACM, 2013: 1307-1318.

严玉良, 董一鸿, 何贤芒, 等. Fsmbus: 一种基于spark的大规模频繁子图挖掘算法 [J]. 计算机研究与发展, 2015, 52(8): 1768-1783.

YAN Yuliang, DONG Yihong, HE Xianmang, et al. FSMBUS: a frequent subgraph mining algorithm in single large-scale graph using spark [J]. Journal of Computer Research and Development, 2015, 52(8): 1768-1783.

栾华, 周明全, 付艳. 多核处理器上的频繁图挖掘方法 [J]. 计算机研究与发展, 2015, 52(12): 2844-2856.

LUAN Hua, ZHOU Mingquan, FU Yan. Frequent graph mining on multi-core processor [J]. Journal of Computer Research and Development, 2015, 52(12): 2844-2856.

PINAR Y, VISHWANATHAN S V N. Deep graph kernels [C]∥Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2015: 1365-1374.

CHEN K, WANG P, LEE Y, et al. Finding unknown malice in 10 seconds: mass vetting for new threats at the Google-play scale [C]∥Proceedings of the Usenix Conference on Security Symposium. New York, USA: USENIX Association, 2015: 659-674.

GASCON H, YAMAGUCHI F, ARP D, et al. Structural detection of android malware using embedded call graphs [C]∥Proceedings of the 2013 ACM Workshop on Artificial Intelligence and Security. New York, USA: ACM, 2013: 45-54.

SHEN Tong, ZHONGYANG Yibing, XIN Zhi, et al. Detect android malware variants using component based topology graph [C]∥Proceedings of the 2014 13th IEEE International Conference on Trust, Security and Privacy in Computing and Communications. New York, USA: ACM, 2014: 406-413.

WANG Pinghui, LUI J C S, RIBEIRO B, et al. Efficiently estimating motif statistics of large networks [J]. ACM Transactions on Knowledge Discovery from Data, 2014, 9(2): 1-27.

JHA M, SESHADHRI C, PINAR A. Path sampling: a fast and provable method for estimating 4-vertex subgraph counts [C]∥Proceedings of the 24th International Conference on World Wide Web. New York, USA: ACM, 2015: 495-505.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

三塔合一间接空冷系统结构参数对夏季运行特性的影响研究

超临界二氧化碳向心透平轮背间隙内风阻损失及流动特性研究

扇贝仿生密封腔室内超临界二氧化碳泄漏流湍动能耗散机理研究

离子液体改性燃料的电流体动力学效应研究

混合电解槽阵列协同的风光耦合制氢系统双层多目标优化