Dynamic clustering of evolving networks: some results on the line

International audienceUnderstanding the dynamics of evolving social/infrastructure networks is a central challenge in many applied areas such as epidemiology, viral marketing, city planification, etc. During the last decade, a massive amount of data has been collected on such networks that still resist to analysis. In this article, we propose to use the data on the dynamics to find better partitions of the network into groups by requiring the groups to be stable over time. For that purpose, we introduce a dynamic version of the k-clustering problem which includes a cost for every point that moves from one cluster to another. We show that this yields in many realistic situations better fitting solutions than optimizing independently various snapshots of the network. We present a first non-trivial exact algorithm for this problem when the points move along a line; this algorithm runs in polynomial time when k and the time horizon are bounded by a constant. We conclude with a series of surprising results on the complexity of the structure of optimal solutions for the line case