基于相似性的极大（k,r）-core图查询

论文摘要

给定顶点度k和顶点之间相似性r,基于相似性的极大（k,r）-core查询用于从图中返回符合条件的社区,该社区既满足k-core条件,又满足k-core中任意顶点之间都相似,并且当除（k,r）-core之外的任意顶点加入时,都不满足（k,r）-core。现有方法的求解过程分为三步:第1步对图中每条边对应的顶点对计算相似性,删除不相似的边;第2步计算k-core;第3步对k-core子图进行验证。通过分析可知,现有方法中存在顶点和边的重复计算所导致的效率低下问题。本文针对k-core的求解方法进行研究,具体研究内容如下。首先,通过分析发现现有方法在前两步计算时都需要访问所有顶点,代价较高。针对第1步和第2步中的冗余计算问题,提出一种高效的k-core计算方法。该方法首先计算k-core,可以减少后续处理中需要访问的顶点和边的数量;然后依次计算每条边对应的顶点对的相似性,删除不相似的边,快速得到满足条件的k-core。其次,现有方法在第3步处理中需要对k-core中的所有顶点进行验证。当所余下的冗余顶点越多,算法的查询效率就越低。针对该问题,提出一种高效验证方法。该方法首先对度为k并且相似顶点个数为k的顶点进行验证,可以快速删除不满足（k,r）-core的顶点。同时,将中间计算结果进行缓存,避免了已有方法在验证过程中对相同顶点对进行多次验证所花费的代价。最后,基于多个不同特征的真实数据集进行实验,通过对本文提出方法与现有求解方法的效果比较,发现本文方法在具体求解过程中更为方便,效果更好。

论文目录

• 摘要
• Abstract
• 第1章 绪论
•   1.1 研究背景及意义
•   1.2 研究现状
•   1.3 研究内容
•   1.4 本文结构
• 第2章 基础知识概述
•   2.1 相关概念
•   2.2 社区发现基本方法
•     2.2.1 给定查询点的社区查询算法
•     2.2.2 未给定查询点的社区查询算法
•   2.3 本章小结
• 第3章 基于k-core的维护处理方法
•   3.1 问题分析
•   3.2 算法思想
•   3.3 算法描述
•     3.3.1 k-core查询处理算法
•     3.3.2 基于相似性的简化策略
•     3.3.3 基于k-core性质的维护操作
•   3.4 算法分析
•   3.5 本章小结
• 第4章 基于约束条件的SHRINK方法和相似性存储
•   4.1 问题分析
•   4.2 基于约束条件的SHRINK方法
•     4.2.1 算法思想
•     4.2.2 算法描述
•   4.3 基于相似性的存储方法
•     4.3.1 算法思想
•     4.3.2 算法描述
•   4.4 算法分析
•   4.5 本章小结
• 第5章 实验及结果分析
•   5.1 引言
•   5.2 实验环境和数据集
•   5.3 性能比较与分析
•     5.3.1 CKDM效果比较
•     5.3.2 剪枝效果比较
•     5.3.3 相似度存储效果比较
•   5.4 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间承担的科研任务与主要成果
• 致谢

文章来源

类型: 硕士论文

作者: 王晓云

导师: 陈子阳,徐凤东

关键词: 相似性,顶点度,缓存

来源: 燕山大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 燕山大学

分类号: O157.5

DOI: 10.27440/d.cnki.gysdu.2019.001387

总页数: 59

文件大小: 942K

下载量: 15