面向查询保护的图聚集算法研究

发布时间：2020-12-24 12:51

　　图数据经常在现实生活中用来描述实体之间的关系。节点表示实体,边表示实体与实体之间的特定关系,如网络中用户之间的关系、交通网络中道路之间的关系、WEB图中网页之间的关系等。随着图数据规模不断增大,无法直接通过肉眼视觉来处理和分析这些图数据。为了节省存储空间和便于对图数据进行分析和查询,需要将大规模图进行压缩,以便于可视化和分析图数据。因此,图聚集技术成为了研究热点。面向查询的图聚集的主要目的是保持原始图中的查询信息,如可达性关系,邻域关系,节点距离等,以此为目标对节点进行聚集。通过对现有图聚集技术现状总结分析,本文主要在面向距离查询的图聚集和可达性保护的图聚集两个方面展开了深入的研究,并取得了如下研究成果:1.提出了融合结构与属性相似性的加权图聚集算法:针对现有算法未考虑图数据同时带有节点属性与边权重的情况,提出一种融合结构与属性相似性的加权图聚集算法,本方法首先使用一种剪枝策略来快速判断节点之间的闭邻域结构相似度,去除掉结构不相似的节点对,并计算剩余节点对精确的结构相似度;其次使用最小哈希技术,计算结构相似的节点对之间的属性相似度;再次,结合节点对之间的结构相似度和属性相似度,得到节点... 

【文章来源】：西北师范大学甘肃省

【文章页数】：72 页

【学位级别】：硕士

【部分图文】：

融合结构与属性相似性的加权图聚集算法框架图

第3章融合结构与属性相似性的加权图聚集算法15最小哈希签名矩阵中列之间的相似度，就是节点对之间的属性相似度，即用节点,对应的列取值相等的行数比矩阵总行数，就可得到节点对之间的属性相似度(,)。图3-3使用MinHash计算节点属性相似性以图3-2为例，计算节点对之间的属性相似度。例如，计算节点1,2之间的属性相似度，根据最小哈希签名矩阵中1,2对应的列，如图3-3所示，计算可得到(1,2)=0.66，同理，也可计算得到点对4,7的属性相似度(4,7)=0.66。3.2.2联合相似度与超边权重计算在图数据中，节点的数量是远远大于属性维度的数量。因此在计算了节点的结构相似度与属性相似度后，需要调节两种相似度所占有的权重比例。利用式(3-2)来计算节点之间的联合相似度，它平衡了节点之间的结构相似度与属性相似度。在3.1节中，使用修剪规则快速判断出了结构相似的节点对，但没有计算节点对之间精确的结构相似度值。但在计算联合相似度时需要计算出过滤后得到的节点对,之间精确的结构相似度值，以便计算出准确的联合相似度值，用于判断节点对,是否能够合并成为超点。(,)=×(,)+(1)×(,)(3-2)在式(3-2)中，节点,是图中的待计算相似度的节点，参数取值在(0,1)之间。设置阈值，当节点,的联合相似度值(,)≥时，就对节点,进行合并，并对合并后形成的超点赋予新的权重值。本章的超边加权方法：当超点中所有原始节点之间的边权重取平均值时，超点之间的超边权重值达到最优，此时将最优值赋予超边。

第4章面向距离查询的属性加权图聚集算法21第4章面向距离查询的属性加权图聚集算法本章提出了面向距离查询的属性加权图聚集算法，可用于查询和存储加权图和无权图，且使用此算法进行聚集对节点间的距离影响最校当合并两个节点成一个超点，引入方程组使合并导致的距离差异最小化，基本原理就是使误差的平均值等于零。算法首先使用剪枝策略过滤掉结构不相似的节点对，并计算剩余节点对间的精确结构相似度；其次，使用属性熵来衡量形成的超点内部属性的一致性；然后，根据已得到的结构相似度值和属性熵值，来计算节点对之间的质量分数，决定该节点对是否合并；最后，通过联立方程组并解方程来赋予新边的权重值，使新边权重对节点间距离的影响最校实验结果表明，本章所提出的算法可行且有效。本章方法的整体框架图如图4-1所示：图4-1面向距离查询的属性加权图聚集算法框架图4.1基础知识4.1.1属性加权图与聚集图定义4-1(属性加权图)：给定一个无向属性加权图为四元组=(,,,)，其中={1,2,,}是图中节点的集合，{(,)|,}是节点之间边集，(,)表示图中节点,之间的边；有穷集合={1,2,…,}是节点属性的集合；={(1,1),…,(,),…,(,)}表示边权重集合，如果边(,)，

【参考文献】：
期刊论文
[1]一种有效的加权图聚集算法[J]. 胡宝丽,游进国,周翠莲,王洋,崔红波.  中国科学技术大学学报. 2016(03)
[2]图聚集技术的现状与挑战[J]. 潘秋萍,游进国,张志朋,董朋志,胡宝丽.  软件学报. 2015(01)
[3]一种新的高效图聚集算法[J]. 尹丹,高宏,邹兆年.  计算机研究与发展. 2011(10)

硕士论文
[1]图聚集算法与聚集图质量评价算法研究[D]. 尹丹.哈尔滨工业大学 2011



本文编号：2935689