Thời gian: 9h30, ngày thứ 5, ngày 4 tháng 1 năm 2018
Địa điểm: Phòng 611 - 612, nhà A6, Viện Toán học, 18 Hoàng Quốc Việt
Tóm tắt: 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 kerne.

joint work with Clémence Magnien, Pierre Meyer and Thi Ha Duong Phan.