Admin CliCours
Importance de la temporalité dans les phénomènes de propagation
Modèles réseaux statiques et dynamiques
Dans cette partie, nous présentons les différentes représentations que nous englobons dans l’appellation approches réseaux. Pour chacune, nous précisons sa mise en place dans le cadre de la description des échanges d’animaux d’élevages. Chaque représentation donne accès à différents outils de description des données (partie 1.2.3), et peut également être utilisée dans le cadre de simulations de diffusions (partie 1.3).
Comment modéliser les interactions ?
Le modèle le plus commun pour représenter des relations entre individus, de quelque nature que ce soit, est le modèle de graphe (que nous qualifions également de réseau statique). Il tire ses origines de la théorie des graphes, dont on attribue souvent les prémices au 18eme 1.1. Éléments contextuels 7 siècle au problème des sept ponts de Königsberg. Depuis lors, une profusion de mesures pour étudier la structure des relations représentées s’est développée. Un graphe G est un ensemble de nœuds V , les entités étudiées, et un ensemble de liens E, leurs relations. G = (V, E) On notera dans la suite du manuscrit n = |V | le nombre de nœuds et m = |E| le nombre de liens. Un lien dans un réseau statique, que l’on dénommera lien statique par la suite, est défini comme un couple de nœuds interagissant : (u, v) ∈ E, tq u ∈ V, v ∈ V (1.1) Les liens représentent des relations, dont la nature est fixée par l’utilisateur. Dans le contexte épidémiologique, un lien peut par exemple représenter une proximité ou un contact physique. C’est le cas par exemple de [Fournet and Barrat, 2014] et [Génois et al., 2015], étudiant la diffusion de maladies dans un établissement scolaire, de [Vestergaard et al., 2016, Starnini et al., 2013] en conférence scientifique, ou encore de [Liljeros et al., 2001], qui étudient la diffusion de maladies sexuellement transmissibles. Un autre exemple de relation représentée par un lien est la vente d’un animal [Christley et al., 2005,Bajardi et al., 2011,Dutta et al., 2014,?]. Dans la première liste d’exemples, le lien est réciproque : chaque nœud peut infecter son voisin (i.e. son partenaire d’interaction) au cours de ce contact. Au contraire, dans le deuxième exemple, seul le nœud vendeur peut contaminer l’acheteur, si l’animal échangé est malade. Pour prendre en compte cette non réciprocité, les liens peuvent être orientés : on distingue l’interaction du nœud u vers le nœud v, de l’interaction de v vers u. On parle alors de graphe orienté (voir le graphe de la figure 1.2). De plus, il est possible d’affecter à chaque lien (u, v) un poids w(u, v), défini comme le nombre de fois que la paire de nœuds a interagi. Le poids est appelé activité des liens statiques dans cette thèse, en référence aux mesures d’activité des nœuds, comme nous le verrons par la suite (chapitre 2). On parle alors de graphe pondéré. Dans le contexte de l’étude des échanges de bovins entre exploitations, les nœuds sont les exploitations et les liens les échanges d’animaux. Ainsi, un nœud est lié à un autre s’ils échangent au moins un animal. Les échanges commerciaux étant orientés, les graphes orientés sont préférés pour leur représentation. En effet, cette orientation sera de grande importance dans la modélisation ultérieure de propagation de maladies.
Comment inclure la temporalité dans la représentation ?
Les réseaux d’élevages étant dynamiques, les interactions n’ont pas forcément lieu d’année en année, de mois en mois, etc. entre les mêmes nœuds [Dutta et al., 2014]. D’une année sur l’autre, les nœuds ne sont donc pas reliés aux mêmes voisins. Différents modèles existent 8 Chapitre 1. État de l’art pour prendre en compte l’évolution du réseau au cours du temps. Le plus fréquemment utilisé est la séquence de graphes (figure 1.2, centre), également appelé séquence de snapshots (un snapshot désignant un graphe de la séquence) . Il consiste à découper la période de temps étudiée en fenêtres temporelles de durée égale. Les échanges inclus dans une même fenêtre seront utilisés pour construire un graphe statique (orienté, pondéré ou non), correspondant donc à la période de temps de la fenêtre. Par exemple, il est courant d’étudier une séquence de réseaux mensuels dans le contexte de la mobilité des animaux d’élevages, comme dans [Bajardi et al., 2011], ce qui veut dire que les données sont découpées en mois, puis chaque mois est transformé en un graphe. Une séquence S peut donc se définir comme suit, avec k le nombre de réseaux de la séquence : S = Gi , i ∈ {0, 1, . . . , k − 1} Gi = (Vi , Ei) L’atout majeur de ce modèle est qu’il permet d’utiliser les mesures de la théorie des graphes pour étudier la structure de chaque réseau statique composant la séquence. L’évolution de la structure des interactions est suivie réseau par réseau (snapshot par snapshot). Cependant, les dates des interactions ne sont pas prises en compte au sein d’un réseau de la séquence : si l’on sait que toutes les interactions représentées ont eu lieu durant la période de temps utilisée pour construire le snapshot, on ne connaît pas leur date précise d’interaction, et donc on perd l’information sur leur ordre.
Modèles réseaux intégrant entièrement l’information temporelle
Connaître l’ordre des interactions est essentiel pour restituer la notion de causalité entre les interactions et ainsi modéliser la propagation de maladies. Des modèles temporels ont donc été développés pour représenter la chronologie des interactions (voir la revue [Holme and Saramäki, 2012]). Parmi eux, on peut citer le graphe temporel de [Kostakos, 2009] : tout nœud u ∈ V de ce réseau est représenté par un ensemble de nœuds temporels (t, u) ∈ W, un pour chaque instant t ∈ T où l’entité a interagi. Par exemple dans la figure 1.1, le nœud A est dupliqué en deux nœuds temporels, A1 et A3, car A interagit aux temps 1 et 3. Deux types de liens coexistent dans cette représentation : les liens représentant les interactions (en noir dans la figure 1.1 à gauche), et les liens temporels (en orange dans la figure 1.1, gauche). Dans l’exemple précédant, un lien temporel relie A1 à A3. La figure 1.1, à droite, représente le graphe temporel obtenu à partir des données à gauche de la figure. Ce modèle présente l’avantage de pouvoir être étudié comme un réseau statique. Cependant, il traite de la même façon les deux types de liens, alors qu’ils représentent une information différente. Aussi, c’est souvent aux modèles de réseaux temporels s’affranchissant de la vision statique des interactions que font appel les études de la littérature. Les Time-Varying Graphs (réseaux évoluant au cours du temps), notés TVG, [Casteigts et al., 2012,Santoro et al., 2011] spécifient l’occurrence dans le temps de chaque interaction.
Introduction |
