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

A SEMANTIC STRUCTURE QUERY ALGORITHM BASED ON RANDOM WALK

作　　者：朱玉 游进国[1] 付子玉 Zhu Yu;You Jinguo;Fu Ziyu(College of Information Engineering and Automation,Kunming University of Science and Technology ,Kunming 650500,Yunnan,China;College of Computer Science and Engineering,Dalian Minzu University,Dalian 116000,Liaoning,China)

机构地区：[1]昆明理工大学信息工程与自动化学院,云南昆明650500 [2]大连民族大学计算机科学与工程学院,辽宁大连116000

出　　处：《计算机应用与软件》2019年第5期242-248,共7页Computer Applications and Software

基　　金：国家自然科学基金项目(61462050;61562054);云南省自然科学基金项目(KKSY201303095)

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

关 键 词：聚集 语义结构 查询 强弱关联 随机游走 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]