Computing Temporal Twins in Time Logarithmic in History Length

摘要

A temporal graph g is a sequence of static graphs indexed by a set of integers T representing time instants. For Δ an integer, a pair of Δ-twins is a pair of vertices u ≠ v which, starting at some time instant, have exactly the same neighbourhood outside {u, v} for Δ consecutive instants. We address the enumeration problem of all pairs of Δ-twins in g, such that the overall runtime depends the least on the history length, namely max{t : G_t ∈ g not empty } - min{t : G_t ∈ g not empty }. We give logarithmic solutions, using red-black tree data structure. Numerical analysis of our implementation on graphs collected from real world data scales up to 10~8 history length.