Online Estimation of Weighted Reachability Between Vertex Pairs with Edge Similarity Decay in Temporal Interaction Graphs
摘要
Temporal interaction graphs (TIGs) consist of timestamped edges, modeling dynamic behaviors in social and communication networks. While reachability analysis has been extensively examined on TIGs, it remains unexplored when edges carry continuous or semantic attributes beyond discrete labels. We study online tracking of weighted temporal reachability (WTR) over a stream of temporal, attributed edges sorted by timestamp. We formalize WTR from a vertex s to v as the cumulative weight of all temporal walks connecting them. It follows the sum-product semiring path formulation with memoryless temporal decay to quantify their spatiotemporal and semantic proximity. To support real-time WTR estimation in evolving edge streams, we develop TReachTracker, an exact incremental method based on transitive closure, and TReachSketch, a theoretically grounded approximation method integrating temporal truncation and sketch-based aggregation under fixed memory. Together, they form a unified streaming solution for efficient, memory-bounded, and semantically aware reachability tracking. Experiments on diverse real-world datasets show that TReachSketch reduces index storage by up to 98%, answers queries within microseconds, and identifies semantically and behaviorally meaningful high-reach vertex pairs.