【摘要】 针对图相似度度量过程中复杂度高、信息缺失的问题,采用将图转换为广义树,将广义树表示为垂直维序列的方法,通过计算垂直维序列的距离度量图的相似度。该方法把度量图相似度的问题简化为计算垂直维序列距离的问题。垂直维序列不仅包含了顶点标号、入度和出度信息,而且体现了顶点的层次结构特性,保留了图中的路径信息。与现有方法相比,该方法在度量过程中考虑了更多的图信息,并将时间复杂度降至O(n~2)。更多还原

【Abstract】 To solve the problems of high complexity and information loss in the process of measuring graph similarity,a method to calculate the distance of vertical dimensional sequences is proposed,which is used to measure graph similarity.Using this method,the graph is converted into the generalized tree,which is regarded as the vertical dimensional sequences.This method simplifies the graph similarity measurement to the distance calculation of the sequences.The vertical dimensional sequences not only obtain labels,in-degrees and out-degrees information of vertices,reflect level structural property of vertices,but also reserve the path information of graph.Compared with the existing graph similarity methods,this method involves more graph information in the process of graph similarity measurement,and decreases the time complexity to O(n~2).更多还原