南京大学学报(自然科学版) ›› 2019, Vol. 55 ›› Issue (6): 960–972.doi: 10.13232/j.cnki.jnju.2019.06.009

• • 上一篇    下一篇

具有结果多样性的近似子图查询算法

洪佳明1,黄云2(),刘少鹏3,印鉴4   

  1. 1. 广州中医药大学医学信息工程学院，广州，510006
    2. 吉首大学软件学院，张家界，427000
    3. 广东技术师范大学计算机科学学院，广州，510665
    4. 中山大学数据科学与计算机学院，广州，510006
  • 收稿日期:2019-07-17 出版日期:2019-11-30 发布日期:2019-11-29
  • 通讯作者: 黄云 E-mail:huangyun109@sina.com
  • 基金资助:
    国家自然科学基金(61472453);广东省自然科学基金(2015A030310312);广东省教育厅青年创新人才项目(2017 KQNCX117);广州中医药大学青年英才培养工程(QNYC20170204);广东省大数据分析与处理重点实验室开放基金(201802);广东大学生科技创新培育专项基金(pdjh2018a0289)

Approximate subgraph query algorithm with result diversity

Jiaming Hong1,Yun Huang2(),Shaopeng Liu3,Jian Yin4   

  1. 1. School of Medical Information Engineering，Guangzhou University of Chinese Medicine，Guangzhou，510006, China
    2. Software College，Jishou University，Zhangjiajie，427000, China
    3. Department of Computer Science and Technology，Guangdong Polytechnic Normal University，Guangzhou，510665, China
    4. School of Data and Computer Science，Sun Yat?sen University，Guangzhou，510006, China
  • Received:2019-07-17 Online:2019-11-30 Published:2019-11-29
  • Contact: Yun Huang E-mail:huangyun109@sina.com

RichHTML

639

PDF (PC)

1004

摘要：

针对大型图中的各种top?k近似子图查询算法存在的顶点重叠度高、无法满足多样性匹配结果输出等问题，提出具有最大顶点覆盖集的多样性近似子图查询算法.该算法建立基于近邻关系和基于区域划分的双重索引，并为相互关系紧密的同标号顶点建立簇索引.在图查询过程中，利用近邻特征为查询图中的每个顶点快速筛选出满足局部匹配要求的候选顶点集，并从不同区域找到多个满足要求的近似匹配子图，避免了查询结果间的高重复率.同时，基于区域和同标号近邻簇的划分，优先查找属于不同划分或不同簇顶点的匹配，减少了不同区域划分间的交互，提高了查询的效率.在大量数据集上的实验结果验证了该算法在查询效率和结果多样性等方面的有效性.

关键词: 子图查询, 近似查询, 结果多样性, 顶点覆盖集

Abstract:

This paper proposes a new algorithm for the diversified top?k approximate subgraph query with maximum vertex cover set to avoid the typical problem of many state?of?the?art algorithms that a large number of duplicate vertices might occur in the result set. The algorithm builds the double index based on the nearest neighbor relation and the region partition，and sets up the cluster index for the closely related vertices. In the process of graph query，we use the nearest neighbor feature to quickly select the candidate vertex set for each vertex in the query graph. We find multiple approximate matching subgraphs from different regions to avoid the high repetition rate between the query results. Meanwhile，based on the division of the region and the neighborhood vertices cluster，we process the graph query from different partitions or the different cluster vertices in order to reduce the interactions between different regions and improve the query efficiency. Extensive experiments on many datasets confirm the effectiveness of our new algorithm in query efficiency and result diversity.

Key words: subgraph query, approximated query, diversified result, vertex cover set

中图分类号: 

  • TP311

图1

近似子图查询示例"

图2

近似子图查询定义及相似性度量示例"

图3

标号为a的顶点邻接关系加权图（对应图1）"

图4

HPRD数据集上DASM算法和其他算法的查询时间随查询图大小变化的趋势"

图5

WordNet数据集上DASM算法和其他算法的查询时间随查询图大小变化的趋势"

图6

DBLP数据集上DASM算法和其他算法的查询时间随查询图大小变化的趋势"

图7

HPRD数据集上DASM算法和其他算法在不同查询图大小下的平均近似子图匹配代价"

图8

HPRD数据集上DASM算法和其他算法在不同查询图大小下的查询结果顶点覆盖集大小"

图9

IMBD数据集上DASM算法和其他算法的查询时间随结果集大小变化的趋势"

图10

IMBD数据集上DASM算法和其他算法的顶点覆盖集大小随结果集大小变化的趋势"

表1

不同规模的人工数据集下DSAM算法的查询时间和查询结果"

10 k 50 k 100 k 500 k 1 M 2 M
查询时间(ms) 35.4 67.4 98.2 87.4 89.8 97
顶点覆盖集大小 183 190 194 199 198 200

图11

DSAM算法的查询时间随数据图平均顶点度变化的趋势"

图12

DSAM算法的查询时间随数据图标号数变化的趋势"

1 Zhang S J ， Yang J ， Jin W . Sapper：subgraph indexing and approximate matching in large graphs. Proceedings of the VLDB Endowment，2010，3(1-2)：1185-1194.
2 Zhu G P ， Lin X M ， Zhu K ，et al . TreeSpan：Efficiently computing similarity all?matching∥Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. Scottsdale，AZ，USA：ACM，2012：529-540.
3 Kim J ， Choi D H ， Li C . Inves：incremental partitioning?based verification for graph similarity search∥Proceedings of the 22nd International Conference on Extending Database Technology. Lisbon，Portugal：Open Proceedings，2019：229-240.
4 Wang R ， Fang Y X ， Feng X . Efficient parallel computing of graph edit distance∥Proceedings of the 35th International Conference on Data Engineering Workshops. Macao，China：IEEE，2019：233-240.
5 Shan X H ， Wang G X ， Ding L L ，et al . Top?k subgraph query based on frequent structure in
large?scale dynamic graphs. IEEE Access，2018，6：78471-78482.
6 Jin J H ， Luo J Z ， Khemmarat S ，et al . GStar：an efficient framework for answering top?k star queries on billion?node knowledge graphs. World Wide Web，2019，22(4)：1611-1638.
7 Khan A ， Wu Y H ， Aggarwal C C ，et al . NeMa：fast graph search with label similarity. Proceedings of the VLDB Endowment，2013，6(3)：181-192.
8 黄云，洪佳明，覃遵跃 . 基于双索引的近似子图匹配. 计算机应用，2012，32(7)：1994-1997.（Huang Y，Hong J M，Qin Z Y. Approximate subgraph matching based on dual index. Journal of Computer Applications，2012，32(7)：1994-1997.）
9 Yang J ， Yang X ， Zhou Z B ，et al . Graph matching based on fast normalized cut∥25th International Conference on Neural Information Processing. Springer Berlin Heidelberg，2018：519-528.
10 Goyal P ， Ferrara E . Graph embedding techniques，applications，and performance：a survey. Knowledge?Based Systems，2018，151：78-94.
11 Bi F ， Chang L J ， Lin X M ，et al . Efficient subgraph matching by postponing cartesian products∥Proceedings of the 2016 ACM SIGMOD International Conference on Management of Data. San Francisco，CA，USA：ACM，2016：1199-1214.
12 Zheng W Z ， Zou L ， Zhao D Y . Answering subgraph queries over large graphs∥12th International Conference on Web?Age Information Management. Springer Berlin Heidelberg，2011：390-402.
13 Zhu L H ， Ng W K ， Cheng J . Structure and attribute index for approximate graph matching in large graphs. Information Systems，2011，36(6)：958-972.
14 Malliaros F D ， Vazirgiannis M . Clustering and community detection in directed networks：a survey. Physics Reports，2013，533(4)：95-142.
15 Yang Z W ， Fu A W C ， Liu R F . Diversified top?k subgraph querying in a large graph∥Proceedings of the 2016 ACM SIGMOD International Conference on Management of Data. San Francisco，CA，USA：ACM，2016：1167-1182.
16 Yu H W ， Yuan D Y . Subgraph search in large graphs with result diversification∥Proceedings of the 2014 SIAM International Conference on Data Mining. Philadelphia，PA，USA：SIAM，2014：1046-1054.
[1] 吕国俊,曹建军,郑奇斌,常宸,翁年凤. 基于结构保持对抗网络的跨模态实体分辨[J]. 南京大学学报(自然科学版), 2020, 56(2): 197-205.
[2] 吴静怡,吴钟强,商琳. 基于Shapelet的不相关情感子序列挖掘方法[J]. 南京大学学报(自然科学版), 2020, 56(1): 57-66.
[3] 李家辉, 周忠眉. 基于多次学习和关联度的关联分类改进算法[J]. 南京大学学报(自然科学版), 2019, 55(4): 564-572.
[4] 李藤, 杨田, 代建华, 陈鸰. 基于模糊区分矩阵的结直肠癌基因选择[J]. 南京大学学报(自然科学版), 2019, 55(4): 633-643.
[5] 胡　淼，王开军，李海超，陈黎飞. 模糊树节点的随机森林与异常点检测[J]. 南京大学学报(自然科学版), 2018, 54(6): 1141-1151.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 汪　勇，刘　瑾*，宋泽卓，白玉霞，王琼亚，祁长青，孙少锐. 高分子稳定剂加固河道边坡表层砂土室内试验研究[J]. 南京大学学报(自然科学版), 2018, 54(6): 1095 -1104 .
[2] 孙　玫，张　森，聂培尧，聂秀山. 基于朴素贝叶斯的网络查询日志session划分方法研究[J]. 南京大学学报(自然科学版), 2018, 54(6): 1132 -1140 .
[3] 魏　桐，童向荣. 基于加权启发式搜索的鲁棒性信任路径生成[J]. 南京大学学报(自然科学版), 2018, 54(6): 1161 -1170 .
[4] 周星星，张海平，吉根林. 具有时空特性的区域移动模式挖掘算法[J]. 南京大学学报(自然科学版), 2018, 54(6): 1171 -1182 .
[5] 王　倩，聂秀山，耿蕾蕾，尹义龙. D2D通信中基于Q学习的联合资源分配与功率控制算法[J]. 南京大学学报(自然科学版), 2018, 54(6): 1183 -1192 .
[6] 韩明鸣, 郭虎升, 王文剑. 面向非平衡多分类问题的二次合成QSMOTE方法[J]. 南京大学学报(自然科学版), 2019, 55(1): 1 -13 .
[7] 刘　素, 刘惊雷. 基于特征选择的CP－nets结构学习[J]. 南京大学学报(自然科学版), 2019, 55(1): 14 -28 .
[8] 王伯伟, 聂秀山, 马林元, 尹义龙. 基于语义相似度的无监督图像哈希方法[J]. 南京大学学报(自然科学版), 2019, 55(1): 41 -48 .
[9] 孔　颉, 孙权森, 纪则轩, 刘亚洲. 基于仿射不变离散哈希的遥感图像快速目标检测新方法[J]. 南京大学学报(自然科学版), 2019, 55(1): 49 -60 .
[10] 贾海宁, 王士同. 面向重尾噪声的模糊规则模型[J]. 南京大学学报(自然科学版), 2019, 55(1): 61 -72 .

版权所有 © 2021 《南京大学学报(自然科学)》

地址：江苏省南京市鼓楼区汉口路22号，南京大学学报编辑部，210093

电话：025-83592704 , 传真：025-83592704        技术支持：北京玛格泰克科技发展有限公司