不确定属性图的子图同构及其判定算法

Uncertain Attribute Graph Sub-graph Isomorphism and its Determination Algorithm

在分析了复杂网络(社会网络)结构的基础上,针对不确定属性图的特征,首先定义了不确定属性图的期望子图同构;由于其只用一个阈值作为限制条件,虽然方法简单,但计算量大,故接着给出了不确定属性图的α-β子图同构的定义,并对其语义进行了解释说明;第三,设计并实现了子图同构算法;最后,通过实验证明α-β子图同构优于期望子图同构,同时分析了不同阈值情况下α-β子图同构的变化规律。α-β子图同构算法的研究为不确定属性图的子图查询和社区挖掘工作奠定了基础。

The uncertain attribute graph expectative sub-graph isomorphism is based on the analysis of complex net- work structure and the characteristic of uncertain attribute graph. The uncertain attribute graph expectative sub-graph isomorphism is only one threshold value as constraint conditions. The method is simple,hut the computation is large α-βmount. Therefore, it brought in the definition ofα-β sub-graph isomorphic of uncertain attribute graph, explained the se- mantic,and designed and implemented the algorithm of α-β sub-graph isomorphism. Through the experiments was proved that α-β sub-graph isomorphic is better than expectative sub-graph,and it arialyzed the variation in the different threshold cases. The research of α-β sub-graph isomorphism algorithm lays the foundation for uncertain attribute graph sub-graph query and community mining.