An Efficient Approximate Algorithm for Single-Source Discounted Hitting Time Query

摘要

Given a graph G, a source node s and a target node t, the discounted hitting time (DHT) of t with respect to s is the expected steps that a random walk starting from s visits t for the first time. For a query node s, the single-source DHT (SSDHT) query returns the top-k nodes with the highest DHT values from all nodes in G. SSDHT is widely adopted in many applications such as query suggestion, link prediction, local community detection, graph clustering and so on. However, existing methods for SSDHT suffer from high computational costs or no guaranty of the results. In this paper, we propose FBRW, an effective SSDHT algorithm to compute the value of DHT with guaranteed results. We convert DHT to the ratio of personalized PageRank values. By combining Forward Push, Backward propagation and Random Walk, FBRW first evaluates personalized PageRank values then returns DHT values with low time complexity. To our knowledge, this is the first time to compute SSDHT with personalized PageRank. Extensive experiments demonstrate that FBRW is significantly ahead of the existing methods with promising effectiveness at the same time.