基于邻域安全压缩的动态图增量子图匹配算法

来源：计算机应用研究杂志2023年第12期北京时间：

作者：徐周波,许昌胜,王嘉鑫,

单位：桂林电子科技大学广西可信软件重点实验室,广西桂林514000；

摘要：针对目前最先进的增量子图匹配算法Symbi中的索引结构DCS中存在的信息冗余问题，提出了一种新的索引结构CDCS（compressed dynamic candidate space），并提出了CDCS的更新算法INCCDCS来动态维护CDCS索引结构和匹配结果，最后提出了动态图的增量子图匹配算法CSymbi。该方法通过引入邻域信息约束，在构建和更新辅助结构的过程中过滤候选集，提高算法的求解效率。最后，在Netflow和LSBench数据集上进行验证，相较于现有方法，候选节点数量最高可以删减56%，候选边数量最高可以删减62%，有效缩减了计算空间并提高了算法的求解效率。

关键词：动态图,增量子图匹配,邻域约束,CSymbi,

基金资助：国家自然科学基金资助项目(61762027)；；