不确定图上的Top-k稠密子图挖掘算法

发布时间：2017-10-10 11:03

  本文关键词：不确定图上的Top-k稠密子图挖掘算法

  更多相关文章： 不确定图 top-k稠密子图 期望稠密度 分支界限搜索 数据挖掘

【摘要】：该文研究了从不确定图上挖掘top-k稠密子图的问题.由于图数据具有内生不确定性,确定图上稠密子图的定义和挖掘算法在不确定图上均不适用.因此,该文提出了不确定图上期望稠密度的概念,并给出了其在多项式时间内的计算方法.基于此,该文定义了不确定图中导出子图之间的一种偏序关系.利用该偏序关系,将不确定图中的导出子图有效地组织成一棵搜索树.该文严格证明了此搜索树中可以完整无重复地覆盖不确定图上的所有导出子图.据此,该文提出了针对此搜索树的一种分支界限搜索算法DS,用于精确挖掘top-k稠密子图.该文还提出了不相交top-k稠密子图的概念,并给出了一种基于束搜索的启发式近似搜索算法LS.在多组数据集上的实验结果表明,文中提出的DS算法具有很高的效率和很好的扩展性,可用于处理大规模图数据.启发式近似搜索算法LS可以快速发现不相交top-k稠密子图.
【作者单位】： 哈尔滨工业大学计算机科学与技术学院;
【关键词】： 不确定图 top-k稠密子图 期望稠密度 分支界限搜索 数据挖掘
【基金】：国家自然科学基金(61173023,61532015)资助
【分类号】：TP311.13
【正文快照】： 博士研究生,主要研究方向为图数据管理、数据库.E-mail:rongzhumr@gmail.com.邹兆年,男,1979年生,博士,副教授,中国计算机学会(CCF)会员,主要研究方向为数据库、数据挖掘.李建中,男,1950年生,教授,博士生导师,主要研究领域为数据库、无线传感器网络.1引言近年来,在科研和应用

【相似文献】

中国期刊全文数据库 前10条

1 王映龙;杨s，

本文编号：1005983