Speaker: Bui Xuan Binh Minh (University Paris 6)
Time: 9h30, Thursday, January 4, 2018
Location: 611-612, Building A6, Institute of Mathematics, 18 Hoang Quoc Viet
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 kerne.
joint work with Clémence Magnien, Pierre Meyer and Thi Ha Duong Phan. |
