Morphogénèse des réseaux complexes

La thèse de David Fourquet consacré à la “découverte du comportement individuel des agents à partir de l’observation macroscopique et dynamique du réseau” a pour objectif de proposer une méthode systématique de morphogenèse de tout type de réseau, même des plus sophistiqués, tels les réseaux pondérés (e.g. réseau lexical dont les poids suivant une proximité sémantique), les réseaux hétérogènes (e.g. scientifiques liés à leurs mots-clés), voire même la structure véritablement dynamique de ces réseaux.

Le pitch du chercheur

Nous avons mis en place une méthode de découverte automatique des modèles génératifs pour les réseaux réels. On suppose qu’un ensemble d’individus créent des liens entre eux à partir de l’analyse de leurs propres caractéristiques (importance, nombre d’amis, rôle dans le réseau), de celles de leurs voisins et des liens qu’ils partagent (communauté d’appartenance, distance). Un algorithme génétique trouve le modèle le plus à même d’expliquer les caractéristiques générales du réseau réel étudié. Il permet donc de connaître la dynamique individuelle des agents, juste en analysant la structure globale du réseau. Notre méthode permet en outre de catégoriser les réseaux selon les modèles qui président à leur établissement et donc prévoir leur évolution future à partir de quelques observations simples.

Abstract

De très nombreux travaux récents menés par des sociologues, des mathématiciens ou des physiciens visent à expliquer les caractéristiques de divers réseaux complexes empiriques à partir de la modélisation du comportement des agents qui les composent et les animent : attachement préférentiel[1], homophilie, modèles de ségrégation[2], p*, etc. Ces modèles de morphogenèse de réseau permettent de simuler des réseaux aléatoires « réalistes », mais aussi de valider le rôle-clé de certains mécanismes microscopiques dans l’émergence de faits stylisés de haut niveau.

Pourtant, nous considérons que les modèles existants sont lacunaires à différents titres. Pour la plupart, ces méthodes visent en réalité à reconstruire un ensemble restreint d’observables de haut-niveau du réseau empirique final, parfois réduit à une seule caractéristique – typiquement la distribution des degrés et/ou le clustering. Lorsque les métriques de comparaison des réseaux sont plus riches, les modèles de morphogenèse existants s’appuient en contrepartie sur des formes fonctionnelles très contraintes (ERGM). A notre connaissance, il n’existe pas de modèle de morphogenèse de réseau permettant de reconstruire de façon satisfaisante des structures plus sophistiquées, tels les réseaux pondérés (e.g. réseau lexical dont les poids suivant une proximité sémantique), les réseaux hétérogènes (e.g. scientifiques liés à leurs mots-clés), voire même la structure véritablement dynamique de ces réseaux.

Objectifs

Ce projet de thèse vise à proposer une méthode systématique de morphogenèse de tout type de réseau. Nous pensons que les méthodes d’apprentissage constituent une approche extrêmement prometteuse à cet égard. L’idée principale est de modéliser les dynamiques des agents sous la forme d’un modèle probabiliste qui lie la création/le renforcement d’un lien aux caractéristiques de l’environnement microscopique mais aussi mésoscopique (comme l’appartenance communautaire, etc.) des nœuds sans définir a priori une liste de caractéristiques pertinentes et/ou une forme fonctionnelle explicite.

Méthodes

La première phase de notre travail consiste à rechercher les observables macroscopiques et dynamiques pertinentes pour la description des réseaux complexes que nous comptons étudier. Plusieurs études[3] [4] ont déjà montré que certaines de ces observables sont corrélées dans de nombreux réseaux réels. Nous étendrons ces études à un plus vaste ensemble d’observables et de réseaux et nous systématiserons la recherche des corrélations. Ceci nous permettra d’établir une première typologie des réseaux et de simplifier l’algorithme de reconstruction en ne tenant que les observables essentielles. Nous faisons le choix d’étudier uniquement les observables de haut niveau observables de haut niveau : distribution de degré, densité, communautés,… car elles sont insensibles aux phénomènes microscopiques et témoignent de la structure globale qui est souvent la seule information accessible.

Dans un second temps, les études sociologiques et anthropologiques associées à des considérations théoriques vont nous permettre de développer différents modèles comportementaux des individus à l’intérieur des réseaux. Dans sa forme actuelle, ce modèle permet à chaque individu de décider des liens à créer avec les individus qui l’entourent à partir des connaissances qui lui sont accessibles. Ces connaissances peuvent être strictement personnelles (propension à créer des liens), relationnelles (degré, centralité ), externes (pagerank des voisins), inter-individuelles (distances aux voisins) ou liées à la communauté d’appartenance (densité de la communauté). La propension à créer un lien avec un voisin particulier est alors le résultat d’un arbre composé d’opérateurs binaires ou simples : +,- min, exp , inverse,… dont les feuilles sont les valeurs particulières des variables précédemment décrites. Cette implémentation basique nous apparaît encore comme insatisfaisante car elle semble incomplète (la représentation mentale du réseau par ses agents est ignorée), et redondante (de nombreuses variables semblent conduire aux mêmes dynamiques d’agrégation des liens) et une grammaire précise des comportements reste à définir.

Nous avons en outre développé un modèle de génération de réseau à partir des modèles individuels. Chaque individu possède la même règle de création de liens, mais pas forcément les mêmes caractéristiques. A chaque étape, la propension d’apparition de chaque lien est calculée et une nouvelle arête est ajoutée à notre réseau artificiel jusqu’à ce qu ‘il atteigne le nombre d’arêtes du réseau réel. Les observables des deux réseaux sont comparées et permettent de définir la qualité de la reconstruction. Comme il est impossible de tester l’ensemble des modèles individuels possibles, nous avons choisi d’utiliser un algorithme génétique pour obtenir une solution optimale reproduisant le mieux possible le réseau réel. Nous pensons que le comportement découvert sera alors très proche du comportement réel des individus. De nombreuses questions demeurent ouvertes sur le modèle de morphogenèse (complexité, espace des réseaux accessibles) et la forme précise du processus d’apprentissage.

[1] A. Barabasi, « Emergence of Scaling in Random Networks », Science, vol. 286, n^o 5439, p. 509 512, oct. 1999.
[2] T. C. Schelling, « Dynamic models of segregation† », Journal of mathematical sociology, vol. 1, n^o 2, p. 143–186, 1971.
[3] G. Bounova et O. de Weck, « Overview of metrics and their correlation patterns for multiple-metric topology analysis on heterogeneous graph ensembles », Physical Review E, vol. 85, n^o 1, janv. 2012.
[4] C. Li, H. Wang, W. de Haan, C. J. Stam, et P. Van Mieghem, « The correlation of metrics in complex networks with applications in functional brain networks », Journal of Statistical Mechanics: Theory and Experiment, vol. 2011, n^o 11, p. P11018, nov. 2011.