Link Stream Edition: Sparse Split and Bi-Sparse Split

Friday, December 15, 2017
Speaker(s) : Binh-Minh Bui-Xuan (UPMC)

(joint work with Clémence Magnien, Pierre Meyer and Ha Duong Phan)
Abstract: Recent advances in 'real world' networks analysis make it possible to mine data stemming from human activities. This is brought to daily use by the many notorious toolkits in web analytics (Neo4j), graph mining statistics (Tiger Graph), criminology graph visualization (AnaCrim) and so on. An important, yet not quite well understood, feature of graph data collected by such tools comes from the time dimension: edges here are timestamped edges. They come ordered by the time interval where they are effectively active. We call this kind of data a link stream.
We focus on well-organised link streams and address the problem of edge-editing an arbitrary link stream into one well-organised link stream (by the act of deleting and adding edges to the original link stream). We present two classes of clique-like link streams, called Sparse Split (SS) and Bi-Sparse Split (BiSS) link streams. We show that both problems SS-edge-edition and BiSS-edge-edition are fixed parameter tractable (FPT) parameterized by the number of editing operations we perform on the input link stream in order to render it a SS or BiSS link stream. Our algorithms are also kernelization algorithms producing quadratic kernels.

More details here …
Romain.Demangeon (at) nulllip6.fr