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

来源：计算机应用杂志2016年第2期北京时间：

作者：宋宝燕, 纪婉婷, 丁琳琳

单位：辽宁大学 信息学院, 沈阳 110036

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

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

基金资助：国家自然科学基金资助项目(61472169,61502215,61572119);辽宁省教育厅优秀人才项目(LR201017);辽宁省教育厅科学研究一般项目(L2015193);辽宁省博士科研启动基金资助项目(201501127);辽宁省科学技术计划项目(2012216007);辽宁大学青年科研基金资助项目(LDQN201438);辽宁省科学事业公益研究基金资助项目(2015003003)。