[01134786]一种基于K2-MDD的无重复标签图的子图匹配算法软件V1.0

数据的结构化表示已经在许多邻域得到了广泛应用,如生物学,化学,社交网络,数据库,知识发现等邻域。这些结构化表示对于有效地描述数据之间的关系是必不可少的。在一些情况下,数据可以很好的被属性图表示,其中顶点用于表示不同的部分,边表示这些部分之间存在的关系,附加信息（称为标签或属性）可以附加到顶点和边上面。随着时间的推移和技术的发展,许多邻域的数据规模越来越大,如何高效的管理这些大规模的图数据,已经成为当下的研究热点问题之一,其中子图匹配查询更是备受关注。从广义上讲,图匹配问题可以分为精确匹配,两个图之间（或至少在它们的子部分之间）需要严格对应,以及不精确或容错匹配,其中图之间的某种程度的结构差异是可接受的。常见的精确匹配（称为子图匹配）包括发现目标图中所有可能的子图,这些子图在结构上等效于模式图。有文献已经证明,当没有对图的结构做出假设时,子图同构是NP完全的;因此,计算复杂性是阶乘的。虽然这个限制是固有的并且无法克服,但通常可以在一般情况下降低计算复杂度,甚至在一些特殊情况下,子图匹配问题可以在多项式时间内解决,无重复标签图的子图匹配算法的复杂度为顶点数量的二次方。虽然无重复标签图的子图匹配不是NP问题,相对容易解决,但其查询时间同样会随着查询图规模的增大呈线性增加。针对以上问题和特点,有必要研制一套精确计算无重复标签图的子图匹配的软件,该软件不仅能够减少了数据存储的节点数量,并且可以减小了查询规模,达到提高查询效率的目的。该软件基于K2-MDD技术提出了一种无重复标签图的子图匹配算法,并以此为基础开发了一款“求解无重复标签图的子图问题的软件”,为网络设计人员及科研人员提供一个能够精确求出无重复标签图的子图的简便易操作工具。改软件主要特点：（1）基于K2-MDD,提出了一种无重复标签图的子图匹配求解的算法,即先对两个图中的顶点进行编码,根据顶点的编码再对边编码,通过边的编码集合构建k2-MDD。该算法将目标图和模式图同时转化为k2-MDD,图在K2-MDD存储表示下,较传统的图存储表示（关联矩阵和邻接表）,大大减少了所需存储的节点的数量。（2）该算法利用k2-MDD能够对图数据进行高效紧凑的表示这一特点,同时结合MDD的交（INTERSECTION）操作,这使得在查询时具有更低的复杂性和更好的可扩展性。（3）用户界面简洁,操作方便,减小了查询规模,同时达到了提高查询效率的目的。