Comment aborder les problèmes liés au graphe dynamique

J'ai posé cette question à stackoverflow générique et j'ai été dirigé ici.

Ce sera formidable si quelqu'un peut expliquer comment aborder les problèmes de graphes partiels ou entièrement dynamiques en général.

Par exemple:

• Trouvez le chemin le plus court entre deux sommets dans un graphique pondéré non orienté pour instances, lorsqu'une arête est supprimée à chaque instance.$(u,v)$$n$
• Trouver le nombre de composants connectés dans un graphique non orienté pour n instances lorsqu'une arête est supprimée à chaque instance, etc.

J'ai récemment rencontré ce genre de problèmes lors d'un concours de programmation. J'ai cherché sur le Web et j'ai trouvé beaucoup de documents de recherche concernant les graphiques dynamiques [1,2]. J'en ai lu quelques-uns et je n'ai rien trouvé de simple (clustering, sparsification, etc.). Désolé d'être vague.

J'apprécie vraiment si certains peuvent fournir des conseils pour mieux comprendre ces concepts.

1. Algorithmes de graphiques dynamiques par D. Eppstein, Z. Galil, GF Italiano (1999)
2. Chemins les plus courts sur les graphiques dynamiques par G. Nannicini, L. Liberti (2008)

Il est difficile de vous donner des techniques concrètes car «dynamique» peut signifier une grande variété de choses, et les algorithmes / résultats dépendent de votre modèle. Voici un aperçu des préoccupations. Voici un article qui donne un aperçu de certaines préoccupations et modèles différents (liés à ce que Peter a cité dans une autre réponse).

Pour les problèmes dynamiques en général, les problèmes clés sont:

• voulez-vous une solution exacte dans tous les cas, ou une approximation est-elle autorisée?
• savez-vous quels changements se produiront (par exemple une distribution de probabilité), ou sont-ils tous également probables?
• comment l'algorithme apprend-il les changements?

Un modèle dynamique typique est quelque chose comme ceci:

1. Étant donné un graphique, vous souhaitez calculer une propriété. Vous êtes autorisé à calculer une solution pour le graphique initial.

2. On vous dit alors une modification: le bord est supprimé. Calculez la propriété sur le nouveau graphique en utilisant des ressources limitées .$(e,f)$

3. Répétez 2 fois pour fois.$n$

Et voici 3 modifications possibles:

• Vous n'êtes pas autorisé à calculer la solution complète au début en raison de limitations d'informations / de temps / d'espace (dont un exemple est les algorithmes en ligne )

• À l'étape 2, l'algorithme n'est pas "informé" de la modification, mais doit trouver la modification dans le graphique en interrogeant une structure de données ou quelque chose.

• Un modèle distribué (comme Peter en parle dans une autre réponse), où les informations sont découvertes localement et les calculs / modifications sont effectués localement.

Les modèles dynamiques sont généralement intéressants en raison des limites de ressources (par exemple temps / espace). À l'étape 2, si j'étais autorisé à calculer une réponse complète (comme je l'ai fait à l'étape 1), le problème est facile, car il s'agit simplement d'un problème de graphe statique répété . Nous sommes plus intéressés par la plus petite quantité de ressources nécessaires pour calculer le changement.

Les modèles de graphes dynamiques ont été étudiés de manière intensive en informatique distribuée. Pour les algorithmes distribués, le calcul est structuré en tours et la topologie des graphiques (= réseau) peut subir quelques changements de tour en tour, qui sont sous le contrôle d'un adversaire. De plus, chaque nœud du graphe exécute un algorithme qui peut envoyer un message à ses voisins (actuels!). (Ce message est l'entrée de l'algorithme des voisins dans le prochain tour.) Ce qui rend les choses intéressantes, c'est qu'un nœud ne "voit" pas le graphique entier mais seulement son voisinage local.

Les problèmes pris en compte dans ces paramètres sont par exemple la diffusion d'informations où chaque nœud du graphique contient initialement un jeton et, éventuellement, vous souhaitez que chaque nœud ait vu chaque jeton. L'objectif est de concevoir des algorithmes qui permettent d'atteindre cet objectif dans le plus petit nombre de tours, en utilisant le moins de messages. Voir [2] pour une enquête récente.

Pour le paramètre non distribué, vous voudrez peut-être regarder [1], qui est une extension du papier que vous avez mentionné.

[1] Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian, Eli Upfal, Fabio Vandin: Algorithmes sur l'évolution des graphes . ITCS 2012: 149-160

[2] Fabian Kuhn, Rotem Oshman: Réseaux dynamiques: modèles et algorithmes . SIGACT News 42 (1): 82-96 (2011)

S'appuyant sur les réponses de @Peter (c'est un très long commentaire, j'ai donc inclus comme réponse en espérant que quelqu'un en bénéficiera).

Je suggère la référence suivante:

Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, Nicola Santoro: graphiques variant dans le temps et réseaux dynamiques. IJPEDS 27 (5): 387-408 (2012)

$\Delta$

Ce qui est vraiment important dans cette classification, c'est qu'il existe des relations d'inclusion entre les différentes classes. Donc, si vous résolvez un problème dans une certaine classe, vous le résolvez dans toutes les autres classes dans lesquelles il est inclus.

Les mêmes auteurs ont présenté des algorithmes de diffusion sur certains des graphiques mentionnés. Ils ont donné différentes mesures de performance liées au temps (c'est-à-dire une définition différente du temps le plus court). En diffusion, l'idée est que chaque nœud construit une vue du réseau dans le domaine temporel. Cela se fait en écoutant à plusieurs reprises les voisins et en envoyant des informations aux voisins. En supposant la périodicité, un nœud peut indiquer quel est le chemin le plus court vers un autre nœud. Il utilise ces informations dans le routage. Plus de détails peuvent être trouvés dans:

Arnaud Casteigts, Paola Flocchini, Bernard Mans, Nicola Santoro: calculs déterministes dans les graphiques à variation temporelle: diffusion sous mobilité non structurée. IFIP TCS 2010: 111-124

$u$$v$$\{(u,x_1), (x_1, x _2), ...., (x _k, v)\}$$u$$v$$v$$u$

J'ai assisté à une conférence des auteurs précédents. D'après ma compréhension, ils affirment que nous sommes loin de pouvoir traiter avec des algorithmes de graphes dynamiques (suivant les définitions qu'ils suivent). Que nous sommes encore dans le cas des classes simples. En fait, ils affirment que la plupart des algorithmes informatiques mobiles supposent simplement que leurs algorithmes sont trop rapides pour être exécutés pendant que le réseau est en transition! (ce que je crois avoir entendu beaucoup) - Ou tout simplement, supposez la périodicité de l'apparence des bords (voir les réseaux tolérants aux retards, etc.)