子图匹配中基于启发式策略的图分割算法

摘要

在大规模的子图匹配过程中,如果直接对原有数据图进行查询,那么所需要的内存和时间开销都是相当巨大的。而根据现实网络的特性,假定用户大多数查询都在社区范围内,如果通过图分割算法将数据图分成多个分区,如此可在不同的分区中同时进行匹配查询,可以极大提高查询效率。提出基于启发式策略的图分割算法(HSGSA),经实验证明,分割时间不会随着图规模的增大而急剧增加,对内存的消耗也不会显著增加,并且分割后进行匹配存在合理性。