子图查询是指输入一个图数据库和查询子图, 输出图数据库中包含查询子图的图集合, 它广泛应用于社会网、生物网和信息网的查询应用中。目前的子图查询算法大多采用静态消耗测算模式, 此类测算模式在图中点数和连接边数呈指数分布时, 会在少数节点上花费较多时间遍历其邻节点, 导致查询算法效率低下。根据信息熵在信息度量中的作用, 将条件信息熵作为启发式匹配的依据, 提出了基于信息熵的子图匹配算法。实验表明, 基于信息熵的子图匹配算法具有更高的查询效率, 且在指数分布的数据集上效果更明显。

子图匹配问题（子图同构）是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年。

子图匹配问题（子图同构）是NP完全的。 我们使用回溯方法为依赖图设计了一个简单的精确子图匹配（ESM）算法。 最坏情况下的算法总复杂度为O（n ^ 2 * k ^ n），其中n是顶点数，k是顶点度。 我们已经证明了我们的算法在三种生物医学关系和事件提取应用程序中的成功使用：BioNLP 2011在事件提取，蛋白质-残基关联检测和蛋白质-蛋白质相互作用识别方面的共同任务。 该Java实现实现了我们的ESM算法。 请参阅README文件：https://sourceforge.net/projects/esmalgorithm/files/如果您使用我们的ESM实现来支持学术研究，请引用以下文件：Liu Haibin，Vlado Keselj和Christian Blouin。 探索用于从文学中提取生物事件的子图匹配方法。 计算智能，2013年。

云平台存储和处理大规模社交网络数据的日益普及，如果我们不注意使用云平台的方法，隐私泄露将成为一个严重的问题。 本文提出了一种分布式k自同构算法和一种分布式子图匹配方法，该分布式k自同构算法可以通过添加噪声边缘来确保k自同构和分布式，从而有效地保护云平台中社交网络的隐私。子图匹配方法可以快速获得临时子图匹配结果。 将临时结果加入后，我们可以根据客户端中k自同构图和k自同构函数的对称性，通过对临时结果进行恢复和过滤来获得正确的结果。 我们还提出了一种改进的方法，该方法利用增量思想来解决动态子图匹配的问题。 实验表明，上述方法对于处理大规模社交网络图问题是有效的，并且可以有效解决子图匹配的隐私泄露问题。