Top-k Densest Subgraphs Search in Temporal Graphs

Abstract

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.

Keywords

• densest subgraph|temporal graph|top-k query