论文摘要
近年来,越来越多的领域都使用“图”来表示和管理数据,称为“图数据”。针对图数据的分析可以发现其中的结构特征、频繁模式、演变规律等有用的知识,具有重要的科研意义和应用价值。随着研究的深入,人们发现现实世界的图数据往往包含数据对象间多种类型的关系。例如,社交网络数据包括多个社交媒体组成的网络;交通网络数据涵盖了多种交通工具组成的网络。这种图数据称为“多层图”,其每一层包含了数据对象间某种特定类型的关系。多层图分析可以发现准确可靠、价值更高的知识。然而,多层图分析面临两方面的挑战:一方面,单层图上的计算语义在多层图场景下不再适用,多层图上的计算语义更加复杂;另一方面,多层图分析涉及多个图层上的计算任务,使得问题的固有计算复杂性大大增加。现有的多层图分析方法在计算语义和算法设计两个方面都存在缺陷,不能很好的解决多层图分析的有关问题。本文综合运用数据分析的相关理论、技术和方法,对于多层图分析进行了系统研究。本文同时考虑了无概率的普通多层图和带概率的多层图,从图数据的稠密性、可靠性、传播性和相似性四方面重要性质出发,对多层图分析领域中的一系列重要问题进行了深入研究,主要研究成果如下:1.本文研究了多层图上的多样化稠密区域发现问题,该问题在生物蛋白复合体检测和社区发现上具有重要应用。在无概率的普通多层图模型基础上,本文提出了一种新的稠密区域概念d-Coherent-Core（简称d-CC）,设计了两种近似比为1/4的高效搜索算法来求解该NP-难问题,算法在结果质量和执行时间两个方面均优于基于准团的传统算法。d-CC概念同时刻画了稠密区域的稠密度和支持度两方面重要特性,满足唯一性、包含性和层次性3个重要数学性质。自底向上和自顶向下两种搜索算法采用了高效的搜索策略和剪枝方法,分别适用于支持度参数较小和较大两种情况。真实数据上的实验结果表明:自底向上和自顶向下两种搜索算法是高效、准确的。2.本文研究了多层图上的top-k可靠顶点搜索问题,该问题在通信网络中具有重要的研究意义,相比基于阈值的搜索问题自适应性更好。本文给出了一种图层带概率的多层图模型,提出了一种新的多层图计算框架——共享计算,其可以有效利用多层图不同图层间的重叠结构以减少搜索代价、提高算法效率。基于此,本文设计了求解top-k可靠顶点搜索问题的共享BFS精确算法和随机算法。真实数据上的实验结果表明:共享BFS精确算法具有很高的效率和扩展性;共享BFS随机算法具有很高的准确率。3.本文研究了多层图上的影响力最大化问题,该问题在病毒式营销和舆情控制中应用广泛。为描述影响力最大化问题中的图数据,本文给出了一种带概率的多层图模型,其可以表示由于边的不确定性而形成的多层图。针对已有算法的缺陷,本文设计了一种能够同时达到高时间效率、高结果质量、低内存开销和高健壮性的影响力最大化算法,具有线性的时间和空间复杂度。该算法采用高质量的分数估计方法和增量式的分数更新方法,在实际社交网络中表现出良好的性能和很高的扩展性。4.本文研究了多层图上SimRank顶点相似性测度问题,该问题是推荐系统、实体识别等众多应用的基础。在带概率的多层图模型基础上,本文严格给出了符合其可能世界语义的SimRank相似性测度定义,设计了高效、准确的计算顶点间SimRank相似性的方法。同时,作为SimRank相似性测度的基础,本文提出了多层图上随机游走的定义,严格证明了这一定义满足马尔可夫性,设计了计算随机游走概率的高效算法。真实数据上的实验结果表明:本文提出的SimRank算法是高效、准确的;本文提出的SimRank测度比传统测度在实际应用中效果更好。
论文目录
摘要Abstract第1章 绪论 1.1 研究背景 1.2 国内外研究现状分析 1.2.1 多层图模型相关工作 1.2.2 多层图分析相关工作 1.2.3 稠密区域发现相关工作 1.2.4 可靠顶点搜索相关工作 1.2.5 影响力最大化相关工作 1.2.6 顶点相似性测度相关工作 1.2.7 现有工作的不足 1.3 本文的主要研究内容 1.3.1 多层图多样化稠密区域发现问题 1.3.2 多层图Top-k可靠顶点搜索问题 1.3.3 多层图影响力最大化问题 1.3.4 多层图SimRank顶点相似性测度问题 1.4 本文的主要研究成果 1.5 本文的章节安排第2章 多层图多样化稠密区域发现问题 2.1 引言 2.2 基础概念和问题定义 2.2.1 多层图模型 2.2.2 d-core和 d-Coherent-Core 2.2.3 问题定义 2.3 d-CC计算方法 2.4 贪心算法 2.4.1 算法流程 2.4.2 算法局限性 2.5 自底向上算法 2.5.1 Top-k多样化d-CC更新方法 2.5.2 自底向上候选d-CC生成方法 2.5.3 整体算法 2.6 自顶向下算法 2.6.1 自顶向下候选d-CC生成方法 2.6.2 可能顶点集收缩方法 2.6.3 整体算法 2.7 优化算法 2.7.1 索引结构 2.7.2 d-CC快速计算方法 2.7.3 DCCS优化算法 2.8 实验结果 2.8.1 实验设置 2.8.2 DCCS算法执行时间 2.8.3 DCCS算法结果质量 2.8.4 DCCS算法性能和参数s的关系 2.8.5 DCCS算法性能和参数d的关系 2.8.6 DCCS算法扩展性 2.8.7 DCCS算法性能和预处理方法的关系 2.8.8 DCCS算法和跨层准团算法的对比 2.9 本章小结第3章 多层图Top-k可靠顶点搜索问题 3.1 引言 3.2 基础概念和问题定义 3.3 基础算法 3.4 多层图共享计算框架 3.5 共享BFS算法 3.5.1 共享BFS精确算法 3.5.2 共享BFS随机算法 3.6 多源Top-k可靠顶点搜索问题 3.6.1 问题定义 3.6.2 规约算法 3.7 反向Top-k可靠顶点搜索问题 3.7.1 第一类反向Top-k可靠顶点搜索问题 3.7.2 第二类反向Top-k可靠顶点搜索问题 3.8 实验结果 3.8.1 实验设置 3.8.2 Top-k可靠顶点搜索算法执行时间 3.8.3 SimuBFS-Exact算法性能和参数k的关系 3.8.4 SimuBFS-Exact算法性能和图层数量的关系 3.8.5 SimuBFS-Exact算法性能和源顶点集合大小的关系 3.8.6 SimuBFS-Rdm算法结果准确性 3.8.7 反Top-k可靠搜索算法性能 3.9 本章小结第4章 多层图影响力最大化问题 4.1 引言 4.2 基础概念和问题定义 4.2.1 多层图模型 4.2.2 影响力最大化问题 4.3 现有影响力最大化算法分析 4.3.1 算法分类 4.3.2 评价指标 4.3.3 正向模拟算法 4.3.4 反向采样算法 4.3.5 评分估计算法 4.3.6 总结和发现 4.4 分数估计方法 4.4.1 分数估计函数分析 4.4.2 分数计算算法 4.5 分数更新方法 4.5.1 算法概览 4.5.2 增量更新方法 4.5.3 延迟更新方法 4.6 QuickIM算法 4.7 实验结果 4.7.1 实验准备 4.7.2 QuickIM算法性能和参数L的关系 4.7.3 延迟更新策略的效果 4.7.4 QuickIM算法运行时间 4.7.5 QuickIM算法结果质量 4.7.6 QuickIM算法内存开销 4.7.7 QuickIM算法健壮性 4.8 本章小结第5章 多层图SimRank顶点相似性测度问题 5.1 引言 5.2 基础概念 5.2.1 随机游走 5.2.2 SimRank顶点相似性 5.3 多层图随机游走定义 5.4 转移概率计算方法 5.4.1 游走概率计算方法 5.4.2 WalkPr算法优化策略 5.4.3 k-步转移概率计算方法 5.4.4 基于采样的k-步转移概率计算方法 5.5 多层图SimRank定义 5.6 单对顶点SimRank计算方法 5.6.1 基础算法 5.6.2 采样算法 5.6.3 两阶段算法 5.6.4 两阶段优化算法 5.7 单源Top-k SimRank计算方法 5.8 实验结果 5.8.1 实验设置 5.8.2 不同顶点结构相似性度量比较 5.8.3 多层图SimRank收敛性 5.8.4 多层图SimRank算法执行时间 5.8.5 多层图SimRank算法结果相对误差 5.8.6 多层图SimRank算法性能和参数N的关系 5.8.7 多层图SimRank算法扩展性 5.8.8 多层图单源Top-k SimRank算法实验结果 5.9 多层图SimRank应用 5.9.1 相似蛋白质发现 5.9.2 实体识别 5.10 本章小结结论参考文献攻读博士学位期间发表的论文及其他成果致谢个人简历
文章来源
类型: 博士论文
作者: 朱鎔
导师: 李建中,邹兆年
关键词: 多层图分析,多样化稠密区域发现,可靠顶点搜索,影响力最大化,顶点相似性测度
来源: 哈尔滨工业大学
年度: 2019
分类: 基础科学,信息科技
专业: 数学,计算机软件及计算机应用
单位: 哈尔滨工业大学
分类号: O157.5;TP301.6
DOI: 10.27061/d.cnki.ghgdu.2019.000327
总页数: 234
文件大小: 5054K
下载量: 79
相关论文文献
标签：多层图分析论文; 多样化稠密区域发现论文; 可靠顶点搜索论文; 影响力最大化论文; 顶点相似性测度论文;
