Temporal Matching
share
A link stream is a sequence of pairs of the form (t,{u,v}), where t∈ N represents a time instant and u≠ v. Given an integer γ, the γ-edge between vertices u and v, starting at time t, is the set of temporally consecutive edges defined by {(t',{u,v}) | t' ∈ [t,t+γ-1]}. We introduce the notion of temporal matching of a link stream to be an independent γ-edge set belonging to the link stream. Unexpectedly, the problem of computing a temporal matching of maximum size turns out to be NP-difficult. We show a kernelization algorithm parameterized by the solution size for the problem. As a byproduct we also depict a 2-approximation algorithm. Both our 2-approximation and kernelization algorithms are implemented and confronted to link streams collected from real world graph data. We observe that finding temporal matchings is non trivial when sampling our data from such a perspective as: managing peer-working when any pair of peers X and Y are to collaborate over a period of one month, at an average rate of at least two exchanges every week. We furthermore design a link stream generating process by mimicking the behaviour of a random moving group of particles under natural simulation, and confront our algorithms to these generated instances of link streams. On tangent areas of our sampling method, the kernelization algorithm leads to an upper bound which nearly meets the lower bound given by the temporal matching computed by the 2-approximation algorithm. All the implementations are open source.
READ FULL TEXT