Approximate Subgraph Matching Algorithm:相关图的近似子图匹配算法-开源

子图匹配问题（子图同构）是NP完全的。 以前，我们使用回溯方法（http://esmalgorithm.sourceforge.net）为依赖关系图设计了精确的子图匹配（ESM）算法。 我们进一步设计了一种近似子图匹配（ASM）算法，该算法能够基于子图距离检测近似子图匹配。 假设图G和子图Gs分别具有m和n个顶点，以及km和kn边，则最坏情况下的算法总复杂度为O（m ^ n * n（n-1）/ 2 * km * log m） 。 该Java实现实现了我们的ASM算法。 请参阅README文件：https://sourceforge.net/projects/asmalgorithm/files/如果您使用我们的ASM实现来支持学术研究，请引用以下论文：Hai Hai Liu，Lawrence Hunter，Vlado Keselj和Karin Verspoor。 基于近似子图匹配的生物医学事件和关系文献挖掘。 PLOS ONE，8：4 e60954，2013年。