Enabling Time-Centric Computation for Efficient Temporal Graph Traversals From Multiple Sources

Temporal graph traversal is an approach for analyzing how information spreads throughout a network over time. A system has been recently proposed as an initial effort for efficient analyses against higher time complexity and infinitely evolving data unlike static graph. However, with the system, the response time for traversals from multiple sources is proportional to the number of sources; thus, application domains of the system can be limited. To resolve this problem, the state-of-the-art vertex-centric paradigm can be considered; however, we have found that the paradigm is not fitted into this computation. The paper proposes a novel time-centric computation approach for efficient all-pairs temporal graph traversals. One benefit of this approach is that users only need to focus on designing a repetitive task for graph elements that are valid at each sliding time, which simplifies the program logic and alleviates the burden of writing codes. Another benefit is that the approach is expected to enhance the performance by facilitating the reuse of intermediate results of multiple sources. The proposed approach is evaluated with a prototyped system, the recipes for existing algorithms, and the experiments with open temporal datasets. In addition, we also discuss how to handle ever-evolving real-world temporal networks.

Automated summary

This paper proposes a novel time-centric computation approach for efficient all-pairs temporal graph traversals. The approach simplifies program logic and reduces the burden of coding, and is expected to enhance performance by reusing intermediate results. The effectiveness of the proposed approach is evaluated through experiments and discussions on handling ever-evolving real-world temporal networks.