不确定图间α-β子图同构匹配算法

子图查询返回图数据集合中所有包含查询图的数据图。在查询图和数据图同时为不确定性图的前提下,提出了不确定图间的期望子图同构定义和α-β子图同构匹配定义。不确定图间的期望子图同构是确定图上子图同构在概率图模型上的直接推广,不确定图间α-β子图同构利用两个限制阈值来衡量查询图和数据图间的匹配质量。文章详细阐述了α-β子图同构匹配的语义特点,分析了其和期望子图同构的联系和差别,设计实现α-β子图同构匹配判定算法。

Algorithm for α-β Subgraph Isomorphism Problem on Uncertain Graph

Subgraph query in graph set returns data graph containing query graph.When the query graph and data graph both are uncertain,this paper proposes a definition of subgraph isomorphism between uncertain graphs and a definition of α-β subgraph isomorphism matching.Expectation subgraph isomorphism between uncertain graphs is a direct extension of subgraph isomorphism between deterministic graphs on probability graph model.There are two parameters α and β which are the thresholds to restrict quality of matching between query graph and data graph.This paper elaborates features of α-β subgraph isomorphism matching in detail,analyzes the differences between it and expectation subgraph isomorphism,meanwhile proposes α-β subgraph isomorphism matching decision algorithm.