使用社区结构信息的子图匹配算法优化方法*

• 作者: 楼昀恺 王朝坤
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 子图匹配 社区结构 优化
• 年，卷（期）: 2019,（1）
• 所属期刊栏目: 数据库技术
• 页码范围: 1-22
• 页数: 22页
• 分类号: TP311
• 字数: 23826字
• 语种: 中文

摘要

子图匹配是图数据查询处理技术中的一个重要研究问题.针对现有子图匹配算法运行效率不高且缺乏通用优化方法的现状,提出一种基于社区结构的子图匹配算法优化方法(community structure based subgraph matching optimization method,CSO).首先,提出两种优化策略,即解析模式图信息以减少子图匹配过程的计算量,以及利用社区结构信息在子图匹配过程中进行剪枝;然后,结合上述两种优化策略提出基于社区结构的子图匹配算法优化方法,并进行了理论分析.真实数据集和合成数据集上的大量实验结果表明,CSO方法能有效减少子图匹配算法的时间开销.同时,不同规模数据集上的实验结果验证了CSO方法良好的可扩展性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王朝坤	清华大学软件学院	17	137	7.0	11.0
2	楼昀恺	清华大学软件学院	1	1	1.0	1.0