大规模动态图中标签约束的频繁子图Top-K查询

来源：计算机科学与探索杂志2018年第11期北京时间：

作者：单晓欢，王广香，宋宝燕，丁琳琳，许岩

单位：辽宁大学 信息学院，沈阳 110036

摘要：Top-K子图查询作为重要的图搜索技术，因可更具针对性地为用户返回查询结果而被广泛应用于社交网、生物信息网等新兴领域。随着图规模增大且动态演变，用户通常希望通过增加约束条件而快速、准确获得查询结果。鉴于上述查询需求，提出了一种标签约束的频繁子图Top-K查询方法（LVC-FS Top-K）。该方法通过建立频繁结构映射与标签值聚合的二级索引（FSM-LVA），快速准确地锁定查询图结构并根据约束限制剪枝过滤，缩小查询范围，提高查询效率；利用FSM-LVA索引对同构于查询图的频繁结构进行查找以实现频繁结构查询，同时结合查询图的约束条件及K值限制对频繁子图进行匹配筛选，缩小比较空间，加快查询效率。实验结果表明提出的方法能快速准确地在大规模动态图中进行具有约束限制的频繁子图Top-K查询。

关键词：大规模动态图,标签约束,聚合划分,Top-K查询