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

• 作者: 朱鎔 李建中 邹兆年
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 不确定图 top-k 稠密子图 期望稠密度 分支界限搜索 数据挖掘
• 年，卷（期）: 2016,（8）
• 所属期刊栏目: 数据挖掘、机器学习与类脑智能
• 页码范围: 1570-1582
• 页数: 13页
• 分类号: TP311
• 字数: 12006字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2016.01570

摘要

该文研究了从不确定图上挖掘 top-k 稠密子图的问题．由于图数据具有内生不确定性，确定图上稠密子图的定义和挖掘算法在不确定图上均不适用．因此，该文提出了不确定图上期望稠密度的概念，并给出了其在多项式时间内的计算方法．基于此，该文定义了不确定图中导出子图之间的一种偏序关系．利用该偏序关系，将不确定图中的导出子图有效地组织成一棵搜索树．该文严格证明了此搜索树中可以完整无重复地覆盖不确定图上的所有导出子图．据此，该文提出了针对此搜索树的一种分支界限搜索算法 DS，用于精确挖掘 top-k 稠密子图．该文还提出了不相交 top-k 稠密子图的概念，并给出了一种基于束搜索的启发式近似搜索算法 LS．在多组数据集上的实验结果表明，文中提出的 DS 算法具有很高的效率和很好的扩展性，可用于处理大规模图数据．启发式近似搜索算法 LS可以快速发现不相交 top-k 稠密子图．

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李建中	哈尔滨工业大学计算机科学与技术学院	237	6003	33.0	72.0
2	邹兆年	哈尔滨工业大学计算机科学与技术学院	17	244	9.0	15.0
3	朱鎔	哈尔滨工业大学计算机科学与技术学院	3	26	3.0	3.0