基于大规模稀疏图的稠密子图挖掘算法研究

论文摘要

随着互联网数据量的增长以及用户交互模式的发展,各种元数据之间逐渐形成一张巨大的网络结构。图模型是数据库和数据挖掘领域常见的用来表示相互关联的元数据数据模型,许多实际应用离不开基于图模型的数据分析管理方法。现实世界的图数据不仅是稀疏的,而且由于节点度数的随机性而常常出现局部密度分布不均匀的特点。在局部密度较大的部分,元数据之间的关联度高于全局平均值,蕴涵的信息量较大,因此在实际的应用中具有较高的商业价值。基于大规模稀疏图的稠密子图挖掘具有重要的理论研究价值和现实意义。根据约束的类型和力度差异,可以定义很多种不同的稠密子图结构。本文从极大团和k边连接子图这两种密度约束力最强也是应用最广泛的稠密子图入手,研究在大规模稀疏图数据上这两种稠密子图挖掘算法的性能。现有的极大团枚举方法以树形搜索框架为主,在超高度数节点的局部会产生巨大的搜索空间从而成为算法的性能瓶颈。近来的研究尝试用并行化的计算方法来提高极大团枚举算法的速度。然而,如何进行最优图切分使得算法的总计算量最小以及如何处理数据冗余与负载均衡之间的矛盾是算法并行化过程中亟待解决的两个问题。本文对极大团枚举问题的研究主要探究稳定快速且具有良好可扩展性的新型算法框架。首先提出了一个两阶段计算框架——CMC算法,将直接计算所有极大团的目标转化为先计算包含极大团的、范围更大的候选团集合,再通过一次遍历构造一棵逆序字典树来从候选团中提取出所有的极大团。随后提出了位图转化和退化排序两个优化策略对CMC算法的时间和空间复杂度进行优化,使构造候选团的过程在稀疏图上具有线性时间复杂度,提取极大团的时间复杂度也降到最低。最后提出了一个快速且可扩展的并行极大团枚举算法,基于MapReduce框架分别对两个阶段的计算过程进行了并行化设计实现。现有的解决k边连接子图问题的方案分为精确算法和近似算法。前者主要通过迭代地搜索最小切割集来切分连接度小于k的子图,耗时非常长;后者基于s-t连接度理论近似地对全局k连接度的节点进行合并,计算结果的正确率有待提高。由于k边连接子图挖掘问题的搜索范围是不确定的,不能像极大团枚举问题那样通过并行化来提高计算速度,因此在尽量提高算法正确率的前提下缩短计算时间是研究k边连接子图挖掘问题面临的最大挑战。本文对k边连接子图挖掘问题的研究主要探索如何同时提高近似算法的正确率与计算速度。提出了一种局部k-ECC连接度检测的方法,在对全局k连接度的节点进行合并之前抽取局部的k-core结构并检测其局部的边连接度。为了提高连接度检测的准确性,提出了一种精确计算最大s-t流的算法。然后基于连接度检测的结果,提出了有效的分解树剪枝和最大化合并的策略,使得算法能够在较短的迭代次数内收敛。

论文目录

论文创新点

摘要

ABSTRACT

第一章引言

1.1 研究背景及意义

1.2 国内外研究现状

1.3 本文主要研究内容与结构

第二章极大团枚举问题

2.1 极大团枚举问题定义

2.2 极大团枚举算法综述

2.2.1 In-Memory算法

2.2.2 并行算法

2.3 存在的问题与难点

2.3.1 减少随机内存访问的开销

2.3.2 非均匀稀疏图上的算法瓶颈

2.3.3 大数据现状下的并行需求

2.4 本章小结

第三章两阶段极大团枚举算法

3.1 候选团

3.1.1 候选团的定义及存储结构

3.1.2 候选团构造算法

3.2 提取极大团

3.3 时间与空间优化

3.3.1 位图操作

3.3.2 退化排序

3.3.3 复杂度分析

3.4 K-极大团枚举

3.5 实验及分析

3.5.1 数据集

3.5.2 对比算法

3.5.3 软硬件平台

3.5.4 实验结果

3.6 本章小结

第四章极大团枚举算法的并行实现

4.1 并行算法的难点

4.1.1 兼顾切分瓶颈和负载均衡

4.1.2 子图的总计算量变化

4.2 图数据切分

4.2.1 单边扩展的图切分法

4.2.2 图切分的子图尺寸

4.3 基于MAPREDUCE的极大团算法并行实现

4.3.1 构造候选团的并行实现

4.3.2 提取极大团的并行实现

4.3.3 节点度数排序的并行实现

4.4 实验及分析

4.4.1 对比算法

4.4.2 软硬件平台

4.4.3 实验结果及分析

4.5 本章小结

第五章 K边连接子图挖掘问题

5.1 概述

5.2 K边连接子图挖掘算法综述

5.2.1 精确算法

5.2.2 近似算法

5.3 存在的问题与难点

5.3.1 算法的速度限制图的规模

5.3.2 提高近似算法的正确率

5.4 本章小结

第六章快速的K边连接子图挖掘近似算法

6.1 局部K-ECC连接度检测

6.1.1 最远s点的选择

6.1.2 有向最大s-t流算法

6.1.3 缩小k-ECC检测范围

6.2 算法流程与实现

6.2.1 图分解框架

6.2.2 剪枝策略

6.2.3 合并切分算法实现

6.2.4 合并检查算法实现

6.3 算法速度与正确率分析

6.4 实验及分析

6.4.1 数据集

6.4.2 对比算法

6.4.3 实验结果及分析

6.5 本章小结

第七章总结与展望

7.1 全文总结及创新点

7.2 未来工作

参考文献

攻博期间发表和在审的科研成果与参与的科研项目

致谢

文章来源

类型: 博士论文

作者: 余婷

导师: 刘梦赤

关键词: 图算法,极大团,并行计算,边连接子图,最大流

来源: 武汉大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机软件及计算机应用

单位: 武汉大学

分类号: TP311.13;O157.5

DOI: 10.27379/d.cnki.gwhdu.2019.000069

总页数: 119

文件大小: 53253k

基于大规模稀疏图的稠密子图挖掘算法研究

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢