图数据流上增量子图相似性匹配技术的研究与实现

摘要

近年来，随着图数据结构在通信网络，模式识别，化学/生物信息，社交网络等领域的广泛应用以及数据多样性的不断发展，图数据流模型受到了越来越多专家学者的关注。目前，虽然静态图上的子图匹配技术已得到了广泛并深入的研究，然而图数据流上的子图匹配问题作为图数据流上许多其他操作的基石，还没有得到深入的研究，而这种图数据流模型在网络安全、社交网络等很多方面都有着广泛的使用价值和深远的现实意义。 针对上述问题，本文对图数据流上增量子图相似性匹配问题进行研究。 首先，本文考虑图数据流上的简单更新，即对于一条已经存在的边不可再次插入。为了实现本文增量维护的思想，为图数据流设计了一种带有剪枝功效的分区策略——最近邻分区法，并对该方法进行增量维护。这样，当每次更新到达时，通过对发生改变的分区重新进行匹配来取代一次完整的匹配过程。考虑到图数据流不断更新变化的特性，本文通过为查询图创建生成树集合的方式完成子图匹配，将图-图之间的匹配转化为树-图之间的匹配从而提高了匹配的速度。同时，提出最大匹配的思想，避免了处理冗余的代价。最后分别在不同真实数据集和合成数据集上进行实验，并与传统静态图上的方法进行对比，证明了本文提出方法的正确性和有效性。 此外，本文还考虑了图数据流上的复杂更新，即同一条边可以被插入或删除多次。该问题是上述问题的进一步深入，因此在最近邻分区的基础上又提出了基于权重的最近邻分区方法，该方法通过权重的判断对图数据流进一步进行剪枝，以加快匹配的速度。同时为了进一步满足图数据流实时响应的特性，提出了一种近似匹配算法。该算法通过对匹配结果候选集合的维护，在每次更新时直接在结果候选集中进行增量维护，从而进一步加快了匹配的速度，并通过提出的近似误差率保证匹配结果的准确性。最后通过实验验证了提出方法的有效性。 总之，本文从越来越接近实际应用的图数据流模型的子图相似性匹配的典型特征和挑战出发，针对图数据流上的简单更新和复杂更新展开研究。基于增量维护的思想，提出了有效的图数据流上增量子图相似性匹配的处理方法。本文为增量维护、最近邻分区等思想的相关课题的展开打下了基础。

目录

声明

摘要

第1章引言

1．1研究背景

1．2问题提出

1．3．1主要研究内容

1．3．2面临的挑战

1．4本文主要贡献

1．5本文组织结构

第2章相关工作

2．1静态图上子图匹配

2．1．1静态图上子图匹配

2．1．2静态图上子图全匹配

2．2带权图上子图匹配

2．3图数据流

2．3．1图数据流上的简单更新

2．3．2图数据流上的复杂更新

2．4本章小结

第3章无权图数据流上增量子图相似性全匹配

3．1问题定义

3．1．1基本概念定义

3．1．2图数据流上增量子图相似性全匹配问题的定义

3．2最近邻分区

3．2．1结构剪枝

3．2．2最近邻判断

3．2．3分区

3．2．4动态维护

3．3生成树集合

3．3．1为查询图创建生成树集合

3．3．2有效的存储方式

3．4子图全匹配

3．4．1 QI-Sequence

3．4．2子图全匹配

3．4．3子图全匹配增量维护

3．5实验

3．5．1实验环境

3．5．2数据集

3．5．3实验结果

3．6总结

第4章带权图数据流上增量子图相似性全匹配

4．1问题定义

4．1．1基本概念定义

4．1．2带权图数据流上增量子图近似匹配

4．2子图全匹配

4．2．1基于权重的最近邻分区

4．2．2基于权重的最近邻分区的动态维护

4．2．3创建生成树集

4．2．4子图全匹配

4．2．5子图全匹配的增量维护

4．3实验

4．3．1实验环境

4．3．2数据集

4．3．3运行结果

4．4总结

第5章总结

5．1本文的主要贡献和结论

5．2进一步的工作

参考文献

致谢

攻读硕士学位期间的项目情况