基于快照的大规模动态图相似节点查询算法

doi:10.11772/j.issn.1001-9081.2016.02.0358

计算机应用 ›› 2016, Vol. 36 ›› Issue (2): 358-363.DOI: 10.11772/j.issn.1001-9081.2016.02.0358

• 第三届CCF大数据学术会议(CCF BigData 2015) • 上一篇下一篇

基于快照的大规模动态图相似节点查询算法

宋宝燕, 纪婉婷, 丁琳琳

辽宁大学信息学院, 沈阳 110036

收稿日期:2015-08-29 修回日期:2015-09-12 发布日期:2016-02-03 出版日期:2016-02-10
通讯作者: 丁琳琳
作者简介:宋宝燕(1965-),女,辽宁铁岭人,教授,博士,CCF高级会员,主要研究方向:数据库、射频识别、大数据管理、图数据管理;纪婉婷(1992-),女,辽宁沈阳人,硕士研究生,主要研究方向:图数据管理
基金资助:
国家自然科学基金资助项目(61472169,61502215,61572119);辽宁省教育厅优秀人才项目(LR201017);辽宁省教育厅科学研究一般项目(L2015193);辽宁省博士科研启动基金资助项目(201501127);辽宁省科学技术计划项目(2012216007);辽宁大学青年科研基金资助项目(LDQN201438);辽宁省科学事业公益研究基金资助项目(2015003003)。

Similarity nodes query algorithm on large dynamic graph based on the snapshots

SONG Baoyan, JI Wanting, DING Linlin

College of Information, Liaoning University, Shenyang Liaoning 110036, China

Received:2015-08-29 Revised:2015-09-12 Online:2016-02-03 Published:2016-02-10

摘要/Abstract

摘要： 动态图拓扑结构演进过程中,为了量化在一定时间域内节点间联系的变化情况,定义了一种泛相似节点的概念,通过衡量其与当前节点的联系是否频繁、分布是否均匀来确定与当前节点的泛相似程度,并提出了一种基于快照的大规模动态图泛相似节点查询处理算法。具体包括:图动态演进过程的快照集表示,即演进动态图;图动态演进过程中的节点泛相似的语义及其形式化表示方式,从联系的频繁程度与分布的均匀程度对节点的相似程度进行了刻画;节点泛相似语义的矩阵表示及处理方式;针对这种语义的泛相似节点查询处理算法。真实数据集和合成数据集上的实验结果均表明算法能够处理大规模动态图上泛相似节点的查询问题,并在实际应用中运用实现。

关键词: 大规模图, 动态图, 演进图, 时间快照, 相似节点查询

Abstract: In the evolution of dynamic graph topology, in order to quantify the change of the relation between the nodes within a certain time, a concept, namely ubiquitous similarity node, was defined, and the level of ubiquitous similarity with the current node was measured by the frequent degree of interaction with the current node and the uniformity of distribution, and a similarity node query processing algorithm for large dynamic graph based on the snapshots was proposed. The concrete content includes: the snapshot expression of the dynamic evolution of graph, namely evolution dynamic graph; the semantic representation and its formal representation of the nodes' ubiquitous similarity in the dynamic evolution of graph, which was characterized by the frequent degree of interaction and uniformity coefficient of distribution; the matrix representation and processing method of the semantic of the nodes' ubiquitous similarity; the query algorithm for ubiquitous similarity nodes. The experimental results on the synthetic dataset and the real dataset show that the proposed algorithm can deal with the nodes' ubiquitous similarity query on the large dynamic graph, and be implemented in the practical applications.

Key words: large graph, dynamic graph, evolution graph, time snapshot, similarity node query

中图分类号:

TP391

宋宝燕, 纪婉婷, 丁琳琳. 基于快照的大规模动态图相似节点查询算法[J]. 计算机应用, 2016, 36(2): 358-363.

SONG Baoyan, JI Wanting, DING Linlin. Similarity nodes query algorithm on large dynamic graph based on the snapshots[J]. Journal of Computer Applications, 2016, 36(2): 358-363.

参考文献

[1] 张青.社交网络中的子图查询研究[D]. 徐州:中国矿业大学,2014:1-12. (ZHANG Q. Research of subgraph query on social network [D]. Xuzhou: China University of Mining and Technology, 2014: 1-12.)
[2] SUN J, FALOUTSOS C, PAPADIMITRIOU S, et al. Graph scope: parameter-free mining of large time-evolving graphs[C]//KDD '07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2007: 687-696.
[3] TANTIPATHANANANDH C, BERGER-WOLF T, KEMPE D. A framework for community identification in dynamic social networks[C]//KDD '07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2007: 717-726.
[4] BACKSTROM L, HUTTENLOCHER D, KLEINBERG J, et al. Group formation in large social networks: membership, growth, and evolution[C]//KDD '06: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2006: 44-54.
[5] ASUR S, PARTHASARATHY S, UCAR D. An event-based framework for characterizing the evolutionary behavior of interaction graphs[C]//KDD '07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2007: 913-921.
[6] 王楠,王斌,李晓华,等.支持动态图数据的子图查询方法[J].计算机科学与探索,2014,8(2):139-149. (WANG N, WANG B, LI X H, et al. Subgraph queries over dynamic graph data[J]. Journal of Frontiers of Computer Science and Technology, 2014, 8(2): 139-149.)
[7] YAN X, YU P S, HAN J. Substructure similarity search in graph databases[C]//SIGMOD '05: Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2005: 766-777
[8] YAN X, ZHU F, YU P S, et al. Feature-based similarity search in graph structures[J]. ACM Transactions on Database Systems, 2006, 31(4): 1418-1453
[9] YAN X, ZHU F, HAN J, et al. Searching substructures with superimposed distance[C]//ICDE '06: Proceedings of the 22nd International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2006: 88-97.
[10] 杨雅君.动态图数据挖掘与查询算法的研究[D].哈尔滨:哈尔滨工业大学,2013:1-14. (YANG Y J. Research on mining and query processing algorithms on dynamic graphs [D]. Harbin: Harbin Institute of Technology, 2013: 1-14.)
[11] MONDAL J, DESHPANDE A. Managing large dynamic graphs efficiently[C]//SIGMOD '12: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2012: 145-156.
[12] 郭聪敏.图集的子图查询算法研究[D].秦皇岛:燕山大学,2011:1-6. (GUO C M. Research on algorithms for subgraph query based on graph database [D]. Qinhuangdao: Yanshan University, 2011: 1-6.)
[13] CHEN C, YAN X, YU P S, et al. Towards graph containment search and indexing[C]//VLDB '07: Proceedings of the 33rd International Conference on Very Large Data Bases. New York: ACM, 2007: 926-937.
[14] 仲新宇.图的近似匹配算法在本体匹配中的应用[D].南京:东南大学,2006:1-5. (ZHONG X Y. The application of approximate matching algorithm in ontology matching based on graph [D]. Nanjing: Southeast University, 2006: 1-5.)
[15] HE H, SINGH A K. Closure-tree: an index structure for graph queries[C]//ICDE '06: Proceedings of the 22nd International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2006: 38-47
[16] TIAN Y, PATEL J M. Tale: a tool for approximate large graph matching[C]//ICDE '08: Proceedings of the 24th International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2008: 963-972.
[17] TIAN Y, MCEACHIN R C, SANTOS C, et al. Saga: a subgraph matching tool for biological graphs[J]. Bioinformatics, 2007, 23(2):232-239.
[18] DEPIERO F, KROUT D. An algorithm using length-r paths to approximate subgraph isomorphism[J]. Pattern Recognition Letters, 2003, 24(1/2/3): 33-46.
[19] MENIK S, GARCIA-MOLINA H, RAHM E. Similarity flooding: a versatile graph matching algorithm[C]//ICDE 2002: Proceedings of the 18th International Conference on Data Engineering. London: dblp Computer Science Bibliography, 2002: 1-12.
[20] 邹兆年,高宏,李建中,等.演变图上的连接子图演变模式挖掘[J].软件学报,2006,21(5):1007-1019. (ZOU Z N, GAO H, LI J Z, et al. Mining evolving patterns of connection subgraphs over evolving graphs[J]. Journal of Software, 2010, 21(5): 1007-1019.)
[21] YAN X, YU P S, HAN J. Graph indexing: a frequent structure-based approach[C]//SIGMOD '04: Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2004: 335-346.

基于快照的大规模动态图相似节点查询算法

Similarity nodes query algorithm on large dynamic graph based on the snapshots

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics

[1]	杜郁, 朱焱. 构建预训练动态图神经网络预测学术合作行为消失[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2726-2731.
[2]	刘越, 刘芳, 武奥运, 柴秋月, 王天笑. 基于自注意力机制与图卷积的3D目标检测网络[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1972-1977.
[3]	高瑞, 陈学斌, 张祖篡. 面向部分图更新的动态社交网络隐私发布方法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3831-3838.
[4]	项能强, 朱小飞, 高肇泽. 原型感知双通道图卷积神经网络的信息传播预测模型[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3260-3266.
[5]	罗香玉, 李嘉楠, 罗晓霞, 王佳. 改进的动态图社区演化关系分析方法[J]. 计算机应用, 2020, 40(8): 2313-2318.
[6]	王卓, 索勃, 潘巍. 三角形的并行枚举算法[J]. 计算机应用, 2017, 37(12): 3397-3400.
[7]	律睿慜, 陈伟, 孟磊, 陈丽芳, 吴昊天, 李静远. 周期性动态图像的傅里叶表达、渲染及应用[J]. 计算机应用, 2015, 35(8): 2280-2284.
[8]	王海洋车生兵舒旭. 基于信息熵与动态区域分割的半脆弱数字水印算法[J]. 计算机应用, 2011, 31(08): 2169-2173.