学位论文简介

移动应用数据蕴含着高价值的信息，但这些数据却具有结构复杂、规模庞大、高速增长等特点。对于这样的大规模图数据流是无法直接加载到内存中进行处理的。此外，现实世界的图通常由于顶点度的随机性而出现局部图密度分布不均匀的特性。针对上述问题，本文尝试突破当前依赖调试参数的图摘要方法，设计无参数调试的压缩算法；结合特定的应用背景和需求，设计稠密子图模型和批量式查询算法；在子图匹配中，将单一查询图转变成多查询图的算法思路，设计多查询图索引结构和查询算法，主要研究工作及贡献如下：

(1) 提出了一种无参数的增量式图数据流无损压缩方法。针对大规模图数据流的无参数的图摘要问题展开研究。基于顶点聚合技术，在压缩图的过程中充分考虑图结构的变化特性，研究增量式图摘要算法，从而提升算法的运行效率。本文提出了一种无参数方法来对全动态图数据流进行无损汇总。针对边的插入和删除，我们首先开发了一种增量式算法，通过仔细探索受影响的子图来维护压缩结果。此外，我们提出了一种基于相似性的算法来控制子图上顶点的移动，从而保证每次摘要更新时的最佳结果。为了提高我们方法的性能，我们还提出了两种关于候选超级节点细化和目标超级节点选择的优化技术。实验结果表明，所提出的方法在压缩质量方面大大优于最先进的方法，并且在大多数数据集上具有可比的运行时间。

(2) 提出了一种基于批量式图更新边的极大biclique的增量式枚举方法。本文从biclique这种密度约束力最强也是最广泛应用的稠密子图入手，研究在大规模二部图数据流上的极大biclique枚举问题。针对biclique枚举问题，结合大规模图数据流的实时更新特点，通过设计针对时间复杂度和空间开销的优化策略，探究稳定快速可扩展的新的增量式算法框架。本文设计了一种新颖的框架，在二分图动态更新的同时有效地维护极大biclique。主要包括两种处理，对于插入新的边，枚举新生成的极大biclique；对于删除边，枚举包含删除边的极大biclique。当插入或删除一批边时，我们对边进行排序。基于边的序列，我们构造了一个递归搜索树，以避免重复枚举新生成的极大biclique和非极大biclique。此外，删除边过程中，首先枚举包含删除边的biclique，以有效的方式检查biclique 的极大性。实验结果证明了我们的技术的效率，其表现优于最先进的方法。

(3) 提出了一种面向多查询图的持续子图匹配查询方法。由于大规模图数据流上进行单一查询图的子图匹配计算复杂性是相当大的，同时考虑到真实场景中查询图的种类以及数量众多的情况，为了快速地获取查询结果，本文将设计一种面向多查询图的子图匹配查询方法。在本文中，我们通过修改现有单一查询图的子图匹配算法，提出了两个基准方法。此外，我们研究了面向多查询图的持续子图匹配查询方法。我们首先提出了一种新的索引结构来存储初始数据图的匹配结果。随着图数据流的更新，我们提出了一种增量式更新算法来实时更新索引结构。然后，我们结合缓存的中间结果，计算所有查询图的顶点匹配顺序。为了平衡内存的使用和缓存结果的检索时间，我们提出了一种高效的搜索匹配结果算法。这导致了性能的显著提高。大量的实验验证了我们解决方案的有效性。

主要学术成果

[1] A parameter-free approach to lossless summarization of fully dynamic graphs. Information Sciences, 2022, 589: 376-394. (第一作者, CCF B类期刊, IF: 8.233).

[2] Efficient maintenance for maximal bicliques in bipartite graph streams. World Wide Web, 2022, 25(2): 857-877. (第一作者, CCF B类期刊, IF: 3.0).

[3] A parameter-free approach for lossless streaming graph summarization. International Conference on Database Systems for Advanced Applications. DASFAA 2021, Springer, Cham, 2021: 385-393. (第一作者,  CCF B类会议)

[4] Efficient Maximal Biclique Enumeration on Large Uncertain Bipartite Graphs. IEEE Transactions on Knowledge and Data Engineering. (第三作者, CCF A类期刊, under review)