用于查找子图同构的QuickSI算法

我正在研究Quick Subgraph Isomorphism（QuickSI）算法，并且在理解第6页（2）和（3）中介绍的关于内部支持和平均内部支持计算的公式时遇到问题。。如果“v”代表顶点，“e”代表边，那么f（v）和f（e）是做什么的？我如何从第6页获取表2的值？第5页中的定义4在帮助我理解方面并没有太大的帮助。通过从查询图到数据图的同构映射我理解从查询图中获取不同的组件，并查看它们是否可以在数据图中找到。但是对于大图，计算时间似乎不太可行。用于查找子图同构的QuickSI算法

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

预先感谢您！

来源

2017-08-14 Vestilios

函数f在定义1中描述 - 它只是保存标签的同构函数（l）。

'平均内支持'是具有同构的'特征'（例如，顶点）除以具有同构的图的数量的数目。要获取表格的值，您需要知道所用图表的数据集（D）。它似乎没有被引用，除了在例4中。

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

来源

2017-08-14 16:00:44 gilleain

感谢您的快速回复。是的，我必须执行此操作。图（D）的数据集位于图1的第1页。我一直试图使用这两个公式，但是我无法从表2中得到答案。如果可能，您可以帮助我一步一步的示例使用公式与数据集？我无法获得边缘类型N-C的1.4或5.1，也没有边缘类型的C-C。谢谢！ – Vestilios

嗯。奇怪我试图计算它，并且这些值似乎不匹配。例如，phi-avg（N）应该是4/3，对吗？ D中有4个顶点标记为'N'，并且有3个包含f（v）的图 - 也就是说3个具有（至少一个？）映射。也许桌子实际上不符合他们给的D？你总是可以问作者... – gilleain

我在边缘部分工作。在三个数据图上我们有4个NC边界映射。我尝试了以下内容：1）4/3，4张映射超过3张图。不工作。 2）4/20，其中20是三个图中的边的总数。没有成功。 3）4/16。 16个边缘，因为我从总共20个边中减去了NC的4个外观。我将尝试的最后一种方法是计算包含此边的可以映射的特征总数。如果失败了，我最终会联系作者。 – Vestilios

用于查找子图同构的QuickSI算法

回答

相关问题