Provenance in Temporal Interaction Networks

In temporal interaction networks (TINs), vertices correspond to entities, which exchange data quantities (e.g., money, bytes, messages) over time. We study the problem of con-tinuously tracking the origins of quantities at network vertices, as interactions take place over time. We target applications, such as financial exchange networks, where the selected transferred units at each interaction are not specified. We investigate several quantity selection policies that apply to different application scenarios. For each policy, we propose space- and time-efficient meta-data propagation mechanisms for continuously tracking provenance at vertices. For the hard case of proportional selection policy, we reduce the cost of tracking in practice, by either (i) limiting provenance tracking to a subset of vertices or groups of vertices, or (ii) tracking provenance only for quantities that were generated in the near past or limiting the provenance data in each vertex by a budget constraint. Our experimental evaluation on real datasets demonstrate the efficiency and scalability of our techniques compared to baseline approaches that extend flow computation algorithms to track provenance.