共查询到10条相似文献,搜索用时 34 毫秒
1.
2.
在分析了复杂网络(社会网络)结构的基础上,针对不确定属性图的特征,首先定义了不确定属性图的期望子图同构;由于其只用一个阈值作为限制条件,虽然方法简单,但计算量大,故接着给出了不确定属性图的α-β子图同构的定义,并对其语义进行了解释说明;第三,设计并实现了子图同构算法;最后,通过实验证明α-β子图同构优于期望子图同构,同时分析了不同阈值情况下α-β子图同构的变化规律.α-β子图同构算法的研究为不确定属性图的子图查询和社区挖掘工作奠定了基础. 相似文献
3.
4.
5.
6.
图模型具有强大的表达能力,被广泛用于各种应用领域的数据建模.如何在大规模图数据库中进行高效子图包含查询是当前的研究难点之一.由于子图同构是一个NP完全问题,在现有的子图包含查询算法中,基于图特征的索引技术被广泛用来提高查询处理性能,但是这些索引结构的维护代价较高.针对有向无环图提出了一种基于拓扑序列的子图包含查询算法,... 相似文献
7.
基于子图同构的三维CAD模型局部匹配 总被引:4,自引:4,他引:0
针对整体相似性检索算法无法实施精确的局部结构匹配的问题,提出一种基于子图同构的三维CAD模型局部结构匹配算法.该算法通过提取CAD模型的B-Rep信息,将其表示为以面作为节点的属性邻接图.在局部匹配过程中,用户输入的局部结构被表示成"子图".待匹配的整体CAD模型被表示成"大图";则在整体CAD模型中.检索局部结构的问题就被转换成在"大图"中寻找同构"子图"的问题.子图同构是NP完全问题,通过利用CAD模型的面特征将图顶点有效细分,并利用已匹配顶点之间的邻接关系动态裁剪搜索空间,实现了快速的同构匹配.实验结果表明,该算法能实现精确的局部结构匹配,并且检索效率能满足实际应用要求. 相似文献
8.
基于子图同构与事例匹配的装配体局部结构相似性分析 总被引:1,自引:1,他引:0
基于事例推理是解决面向装配的设计和装配工艺规划问题的有效方法,装配体检索是应用此方法的关键步骤.为此提出一种基于子图同构与事例匹配的装配体局部结构相似性分析方法.该方法将装配体零件间的装配关系用属性邻接图来表示,通过对装配体中联结关系的定性分类及装配体属性邻接图预处理规则的定义,利用Ullmann算法匹配出相似的装配体图(子图)结构,并给出了装配体局部结构相似度计算公式.最后通过实例验证了文中方法的有效性. 相似文献
9.
近年来,图模型广泛应用于生物信息、计算化学、语义网等领域.目前,"过滤-验证"机制被广泛用于子图包含查询,即首先根据图数据的特征构造索引,然后根据索引产生候选集,最后对候选集中的每一个图进行子图同构验证.在这类算法中,"过滤"阶段是关注的重点,力争过滤掉更多的数据;而"验证"阶段则只是单纯地进行候选图子图同构检测,并没有进一步优化查询性能的可能.因此,提出了一种新的子图包含查询的迭代处理机制:"选择-验证-过滤",可利用从子图同构验证过程中得到的信息,结合数据库中图数据之间的相关关系,进行迭代查询处理.该机制首先选择数据库中的图与查询图进行同构验证,然后根据本次验证得到的信息,结合图数据之间的子图映射关系,进行迭代查询处理.一旦子图同构验证成功则可直接获得查询结果,而若验证不成功,则可以缩小下次迭代的查询搜索空间.为提高验证成功概率,提出了一种基于搜索空间预测的图选择策略.大量实验表明,该算法具有较"过滤-验证"机制更高的查询处理性能. 相似文献
10.
图匹配在现实中被广泛运用,而子图同构匹配是其中的研究热点,具有重要的科学意义与实践价值。现有子图同构匹配算法大多基于邻居关系来构建约束条件,而忽略了节点的局部邻域信息。对此,提出了一种基于邻居信息聚合的子图同构匹配算法。首先,将图的属性和结构导入到改进的图卷积神经网络中进行特征向量的表示学习,从而得到聚合后的节点局部邻域信息;然后,根据图的标签、度等特征对匹配顺序进行优化,以提高算法的效率;最后,将得到的特征向量和优化的匹配顺序与搜索算法相结合,建立子图同构的约束满足问题(CSP)模型,并结合CSP回溯算法对模型进行求解。实验结果表明,与经典的树搜索算法和约束求解算法相比,该算法可以有效地提高子图同构的求解效率。 相似文献