论文部分内容阅读
随着大数据技术的飞速发展,大规模图数据在各个领域中的关键作用逐渐凸显出来。如何在不同类型的图中找出有用的结构从而获取有效信息成为一个受到广泛关注的问题。作为由图中一组内部紧密联系的顶点组成的拓扑结构,紧密子图由于其直观、易于解释、扩展性强等特性逐渐成为图数据管理与挖掘中的研究热点,被广泛应用于社交、生物、物理化学、金融等各个领域之中。当前,各种类型的紧密子图得到了学术界和工业界的研究。然而随着数据规模和类型的增加,紧密子图搜索面临着算法效率下降以及难以满足新型应用需求的问题。为了满足大数据环境下不同应用的需求,提升查询效率从而优化用户的体验,本文着重选取了三种最为常见的图:简单图、不确定图和二部图,并分别对不同类型大规模图中的子图搜索问题展开了深入的研究,包括:简单图和不确定图上的基于影响力社区模型的紧密子图搜索问题以及二部图中基于最大准二部团模型的紧密子图搜索问题。在参阅了大量的现有工作后,我们针对现有子图模型的不足,结合不同图的属性和结构特征,提出新颖的子图模型以及高效的子图查询算法。本文的主要工作和创新点如下:(1)简单图影响力社区搜索。在简单图中,首先针对现有影响力社区搜索中由于顶点权重不同影响结果正确性从而限制其应用场景的问题,提出了一种能够处理相同权重顶点的更通用的影响力社区搜索方法。对于可能影响最终结果的具有相同权重的顶点,通过顶点之间的连通性判断来避免对结果产生影响。同时,为了进一步提高算法的效率,提出了一种基于Union-Find的方法来快速地判断顶点之间的连通性。最后在大规模的真实数据集上对所提出的方法和现有的方法进行了大量的实验和对比。实验结果表明,该方法能够有效地处理权重相同的顶点从而保证获得的影响力社区的准确性。(2)不确定图影响力社区搜索。在不确定图中,首次根据边的不确定性提出了一种新型的社区模型用于有效描述不确定图影响力社区。对于不确定图影响力社区的计算,首先提出了一种基于顶点剥离的影响力社区在线算法,该算法通过迭代地删除图中权重最小的顶点并更新被删除顶点的邻居信息来获取影响力社区。为了提升查询的效率,提出了一种新型的基于表的索引以及索引查询方法,并将索引组织成树状结构来提升其查询的效率。同时,为了减小索引的空间占用,进一步提出了两种优化方法:社区合并和社区压缩,前者可以合并索引中不同节点间重复存储的社区,而后者可以压缩同一个节点内存储的社区顶点。最后在大规模真实数据集上的实验对比了不确定图与简单图中影响力社区模型的差异并评估了不确定图影响力社区搜索算法的效率。实验结果表明,基于索引的方法比在线方法运行效率提升了多达两个数量级。(3)二部图准二部团搜索。在二部图中,研究了一种准二部团模型最大k-biplex的搜索问题。首先证明了该问题为一个NP-hard问题,并提出了一个解决该问题的MBS算法。该算法通过回溯的方式枚举所有可能的极大k-biplex作为候选集合,然后在其中挑选规模最大的k-biplex作为输出。在枚举候选集合时,提出了两种基于k-biplex特性的剪枝策略来去除不可能成为k-biplex的候选集合,从而提升搜索的效率。为了进一步缩短搜索时间,提出了一种基于core的图约简方法。该方法能够将图约简为一系列规模较小且可能包含最大k-biplex的子图。同时通过研究子图中可能包含k-biplex规模的上下界对不包含最大k-biplex的子图进行剪枝,从而进一步提升算法效率。此外还提出了启发式算法及并行算法来进一步满足实际需求中对效率的要求。大规模真实数据集上的实验结果显示,所提出方法的计算速度在现有最先进方法基础上提升了2到3个数量级。