Clustering Dynamique par Rayon

National audienceComprendre les dynamiques d'évolution de réseaux sociaux et d'infrastructuresest un problème crucial dans les domaines comme l'épidémiologie, l'urbanismeou la marketing viral. Une quantité croissante de données dynamiquessur des réseaux divers est disponible depuis plusieurs années maisles outils pour analyser ces données ne sont pas toujours adaptés.Nous proposons d'utiliser ces données dynamique pour faire des groupesd'individus de comportement similaire restant stables avec le temps.Pour cela nous introduisons une variante dynamique du problème Sum-Radii Clustering, en utilisant le formalisme du problème DynamicFacility Location, avec la distinction que nous cherchons à minimiser le diamètre des groupes aulieu de la somme des distances au centre. Nous étudions deux adaptations naturelles d'algorithmes probabilistes utilisés pour Dynamic Facility Location (marchant respectivement dans le cas général et quand on se restreint à des espaces métriques). Dans le premier cas, l'algorithme atteint la même borne d'approximation et nous proposons une amélioration, aussi valable pour l'algorithme original (faisant passer le facteur d'approximation de $O(\log nT)$ à $O(\log n)$, où $n$ est le nombre de clients et $T$ la durée en nombre de pas de temps).Enfin, nous montrons que dans le cas métrique, les outils actuels ne permettent pas encorede donner un meilleur résultat, et exhibons un contre-exemple pour le deuxième algorithme, prouvant qu'il ne peut pas atteindre une approximation constante