一种基于Hadoop的大规模Internet频繁闭图挖掘算法  

A Frequent Closed Graph Mining Algorithm in Large Scale Internet Based on Hadoop

作　　者：张岩庆[1] 陆余良[1] 杨国正[1] 朱凯龙 

机构地区：[1]电子工程学院网络工程系,安徽合肥230037

出　　处：《四川大学学报（工程科学版）》2016年第4期136-143,共8页Journal of Sichuan University (Engineering Science Edition)

基　　金：国家自然科学基金资助项目(61503394;61405248);安徽省青年科学基金资助项目(1408085QF131;1508085QF121)

摘　　要：针对当前单机模式下频繁闭图挖掘算法无法处理大规模Internet数据集的问题,通过改进Apriori算法,提出基于Hadoop的迭代式频繁闭图挖掘算法AMR(Apriori based on MapReduce)。首先将动态网络的边集存储在键值表中,并设计了序列化子图编码方案以确保频繁子图的唯一性;然后提出了一种传递子图编码的通信机制,通过整合每个分片的支持度得到全局支持度,从而确保了频繁闭图的准确性;最后通过剪枝得到动态网络的频繁闭图。将AMR算法分别运用于国家级和AS级Internet的动态网络中。结果表明,频繁闭图能够准确表征Internet骨干网络的拓扑结构,说明AMR算法能够快速且有效地挖掘大规模动态网络的频繁闭图。The existing frequent closed graph（FCG） mining methods under standalone mode can not process massive Internet datasets. By improving the Apriori algorithm, an iterative algorithm AMR （ Apriori based on MapReduce） was proposed to mine FCGs of large scale dynamic networks based on Hadoop. First of all, the edge sets of dynamic networks were stored in the key-value table, and a serial- ized subgraph coding mechanism was designed to ensure the uniqueness of frequent subgraphs （FSG）. Secondly, a communication mech- anism was proposed to pass subgraph codes, and to ensure the accuracy of FCG,local supports in each partition were aggregated to a global one. Finally, FCGs were achieved by pruning the FSGs. AMR was used in the dynamic networks of both country and AS level In- teruet. Experimental results showed that FCG can accurately characterize the topology of backbone Interuet, thus verifying the efficiency and effectiveness of AMR in mining FCG of large scale dynamic networks.

关 键 词：降级结构 无干扰 架构细化 策略细化 

分 类 号：TP393.4[自动化与计算机技术—计算机应用技术]