求子图同构的QuickSI算法

Question

我正在研究快速子图同构(QuickSI)算法，我在理解第6页、第(2)页和第(3)页中描述的关于内部支持和平均内部支持计算的公式时遇到了问题。如果"v“代表顶点，"e”代表边，那么f(v)和f(e)做什么？如何从第6页获取表2的值？第5页的定义4对我的理解并没有多大帮助。通过从查询图到数据图的同构映射，我理解从查询图中提取不同的组件，看看它们是否可以在数据图中找到。但对于大型图来说，计算时间似乎并不太可行。

你可以在这里找到原文：http://www.cse.unsw.edu.au/~lxue/10papers/vldb08_haichuan.pdf

提前谢谢你！

Answer 1

函数f在定义1中描述-它只是保持标签(l)的同构函数。

“平均内支持”是具有同构的“特征”(例如，顶点)的数量除以具有同构的图的数量。要获得表的值，您需要知道所使用的图(D)的数据集。它似乎没有被引用，除非在示例4中。

真的，退后一步--你需要实现这个特殊的算法吗？有很多更简单的方法，它们可能会稍微慢一些，但更清晰。此外，为什么不使用别人实现的子图同构算法呢？