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

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

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

宋宝燕, 纪婉婷, 丁琳琳   

  1. 辽宁大学 信息学院, 沈阳 110036
  • 收稿日期:2015-08-29 修回日期:2015-09-12 出版日期:2016-02-10 发布日期:2016-02-03
  • 通讯作者: 丁琳琳
  • 作者简介:宋宝燕(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   

  1. College of Information, Liaoning University, Shenyang Liaoning 110036, China
  • Received:2015-08-29 Revised:2015-09-12 Online:2016-02-10 Published:2016-02-03

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

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

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

中图分类号: