  Understanding the dynamics of evolving social or infrastructure networks is a
challenge in applied areas such as epidemiology, viral marketing, or urban
planning. During the past decade, data has been collected on such networks but
has yet to be fully analyzed. We propose to use information on the dynamics of
the data to find stable partitions of the network into groups. For that
purpose, we introduce a time-dependent, dynamic version of the facility
location problem, that includes a switching cost when a client's assignment
changes from one facility to another. This might provide a better
representation of an evolving network, emphasizing the abrupt change of
relationships between subjects rather than the continuous evolution of the
underlying network. We show that in realistic examples this model yields indeed
better fitting solutions than optimizing every snapshot independently. We
present an $O(\log nT)$-approximation algorithm and a matching hardness result,
where $n$ is the number of clients and $T$ the number of time steps. We also
give an other algorithms with approximation ratio $O(\log nT)$ for the variant
where one pays at each time step (leasing) for each open facility.
