基于随机游走的语义结构查询算法

在语义结构查询问题中,传统的查询方法无法快速直观地描述一个具有百万节点的大图,并衡量语义结构的重要性。针对该问题,VoG算法利用子图分割方法并最大化对语义结构进行匹配。提出一种MRQ算法,解决传统算法中查询时间长等问题。利用ApxGreedy算法对输入图进行聚集;通过聚集后超点强弱关联生成随机游走图;使用随机游走算法对语义结构进行查询,根据聚集过程与查询过程中产生的损失进行加权求和,并排序输出语义结构。随机游走查询算法有效地降低了时间复杂度。MRQ算法与VoG算法在真实数据集上的对比实验表明,MRQ算法在时间上比VoG快10倍,误差率降低3.75%。

A SEMANTIC STRUCTURE QUERY ALGORITHM BASED ON RANDOM WALK

In the semantic structure query problem,the traditional query methods cannot describe a large graph with millions of nodes quickly and intuitively,and cannot measure the importance of the semantic structure.To solve this problem,the VoG algorithm uses the subgraph segmentation method and maximizes the matching of the semantic structure.This paper proposed MRQ algorithm to solve the problem of long query time.The ApxGreedy algorithm was adopted to aggregate the input graph;random walk graphs were generated by the strong and weak correlation after the aggregation;random walk algorithm was used to query the semantic structure,weighted sum was made according to the loss of aggregation and query process,and the output semantic structure was ranked.The random walk query algorithm effectively reduces the time complexity.The comparison between the MRQ algorithm and the VoG algorithm on the real dataset shows that the MRQ algorithm is 10 times faster than VoG and the error rate is reduced by 3.75%.