时序图中Top-k稠密子图查询算法研究  

Top- k Densest Subgraphs Search in Temporal Graphs

作　　者：穆聪聪 王一舒 袁野 乔百友 马玉亮 MU Cong-cong;WANG Yi-shu;YUAN Ye;QIAO Bai-you;MA Yu-liang(School of Computer Science and Engineering,Northeastern University,Shenyang 110000,China)

机构地区：[1]东北大学计算机科学与工程学院,沈阳110000

出　　处：《计算机科学》2021年第10期152-159,共8页Computer Science

基　　金：国家重点研发计划项目(2016YFCI401900)。

摘　　要：稠密子图的查询是图分析领域的重要研究问题之一,在社交用户相关性分析、Web中社群分析等方面都有着广泛的应用。目前,关于稠密子图查询的研究工作主要基于静态图。而在实际应用中,时序信息会对稠密子图查询产生重要的影响,使得图拓扑结构随时间序列不断发生变化,包含的信息量也不断增加,使得已有的针对静态图的查找方法不再适用于时序图。因此,如何高效地在时序图上查找稠密子图仍然是一个挑战。为了解决上述挑战,首先规范化地定义了基于时序图的稠密子图查找问题;然后,根据图的拓扑结构和包含时间标签的边之间的相似度,提出一种基于阈值的近似查找算法DTS-base。为了加快算法的收敛速度,提出了一个基于快速计算最大相似度时间片的优化算法DTS-opt。最后,通过在真实数据集上的实验,证明了所提算法的高效性和可扩展性。The dense subgraph search problem is one of the most important graph analysis problems.It is widely used in many fields,such as the social user correlation analysis in social networks,the community discovery in the Web,etc.However,the current research focuses on searching dense subgraphs on static graphs.In practical application,temporal information has an important impact on the query of dense subgraphs,which makes the topology structure of graphs change constantly with time sequences,and the amount of information contained also increases dramatically.Therefore,the existing searching methods for static graphs are no longer applicable to temporal graphs.Hence,it is still a challenge to search dense subgraphs efficiently on a temporal graph.In order to solve the above challenge,this paper first defines the Top-k densest temporal subgraphs searching problems in a standardized way.Then,to address the above challenge,this paper proposes an approximate searching algorithm DTS-base based on threshold according to the topology of the graph and the similarity between edges containing time tags.Furthermore,an optimization algorithm DTS-opt based on the fast calculation of maximum similarity time slice is proposed in order to accelerate the convergence speed.Finally,experiments on real data sets demonstrate the efficiency and scalability of the proposed algorithms.

关 键 词：稠密子图 时序图 TOP-K查询 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]