Posts

Théorie et mesure des réseaux

Théorie et mesure des réseaux

Edition 2017

Contributeurs : Cyril Bertelle, Jean-Philippe Cointet, Jean-Pierre Gaudin, Damien Olivier, Jean-Baptiste Rouquier

Mots-clefs : Réseau complexe, graphe de terrain, grand réseau d’interaction, graphe, hiérarchie, clustering, communautés, dynamique, robustesse, données partielles, données contextuelles

Introduction

La technologie actuelle produit des données à un rythme toujours plus rapide, et une partie de ces données peut être modélisée par des graphes. Dans de nombreux domaines, le point de vue graphe apporte un éclairage complémentaires aux analyses spécialisées propres au domaine. Cela permet notamment d’orienter les recherches vers les voies les plus prometteuses, d’appréhender la structure d’une grande masse de données. L’approche réseau est un moyen de travailler l’articulation multi-échelle qui caractérise la plupart des systèmes complexes.

Pour tenter de dessiner les contours du domaine des réseaux complexes, nous proposons les trois critères suivants : il s’agit de graphes qui sont

  • construits à partir de données d’observation
  • suffisamment grands pour permettre des statistiques et une approche agglomérative
  • évoluant essentiellement par des mécanismes locaux

Quels sont les verrous actuels de l’étude des réseaux ? Quelles sont les problématiques communes à plusieurs disciplines ? Au fil des pages de la feuille de route, les réseaux sont mentionnés plusieurs fois. Le but est ici d’identifier les problématiques communes, qui appellent des méthodes communes.

Défis

  • Structure et hiérarchie, classification (translation of this section at the end)
  • Classification

Recueil et formalisation des données

A. Incomplétude des données

La non-exhaustivité des données peut provenir de différents facteurs : coût de rassemblement, soucis de confidentialité, stratégie de rétention des possesseurs de données (capitalisation de l’information). Une partie de ce défi peut être aujourd’hui surmontée par des protocoles innovants de collecte de données. Notamment, l’obstacle des coûts ou de faisabilité peut être réduit par le recours à des protocoles qui s’appuient sur des dispositifs d’information embarqués, comme les téléphone portables, les dispositifs munis de puces RFID (type navigo/oyster), des logiciels proposés à l’utilisateur, etc.

Ces difficultés sont encore augmentées lorsque l’on souhaite faire un recueil longitudinal (encore appelé dynamique, ou diachronique) de données. La dynamique est par exemple cruciale pour étudier un réseau de déplacement de population (qui montre des cycles journaliers et saisonniers) et sa réaction aux incidents, ou bien l’infrastructure internet (le réseau de routeurs et serveurs) dont la dynamique est plus rapide que le processus de mesure.

Ces difficultés de collecte peuvent induire une description lacunaire des réseaux. Pour travailler avec des données lacunaires, il y a principalement deux voies :

  • utiliser des modèles artificiels pour compléter les trous ;
  • s’appuyer sur d’autres sources pour combler les manques (par exemple, utiliser des données statistiques et démographiques pour estimer les données manquantes)
  • prendre en compte, dès la mesure, un indicateur de confiance sur toutes les données (par exemple la probabilité qu’un lien dans les données existe réellement dans le système mesuré, ou bien un intervalle de confiance sur le poids d’un nœud). Puis adapter les méthodes à ce type de données.

 

B. Enrichissement du formalisme réseau

Le formalisme de base des réseaux s’appuie sur une approche relationnelle stricte (et homogène en termes de nœuds) qu’il s’agit ensuite de remettre en situation de plusieurs manières :

1. Introduire d’autres contextes

Il s’agit notamment d’approches géographiques : utiliser le contexte physico-spatial. D’autres contextes sont la démographie, l’économie et la politique. Par exemple, comment travailler sur des données concernant la préparation d’un projet, les présents aux réunions, comment mesurer l’implication des partenaires ?
Leur prise en compte appelle à un enrichissement de l’analyse des structures relationnelles, et vice-versa : l’approche réseau éclaire ces contextes.
L’art du modélisateur prend toute sa mesure sur ces problèmes, pour contrôler quelle information est perdue lors de la modélisation (par exemple en approximant l’économie d’une ville par sa population et quelques flux tels que eau et argent), nécessairement schématique. L’information entrée dans le modèle peut être largement améliorée.

2. Donner du relief

Les réseaux dont les relations sont purement binaires décrivent des situations décontextualisées. Il s’agit donc de développer des procédures à même de prendre en compte plus d’informations :

  • un cas en cours est celui des réseaux orientés(ou dirigés) et/ou pondérés(ou valués: les nœuds et liens ont un poids)
  • la superposition de réseau (multi-réseau)
  • la sémantique des liens (par exemple, contenu textuel attaché à un échange d’emails)
  • des nœuds hétérogènes (s’il y a deux types de nœud, c’est un réseau biparti, mais il peut y en avoir plus)
  • hyper-réseaux : formalisation d’un tissu relationnel qui se constitue autour d’événements, d’enjeux et de co-production qui engagent un ensemble d’agents.

 

Dynamique

La prise en compte de la dynamique dans les grands réseaux est essentielle pour leur approche dans le cadre de l’étude des systèmes complexes. Trois aspects sont à considérer et sont développés dans la suite : la caractérisation de ces dynamiques, la mesure des dynamiques elles-mêmes et les propriétés induites.

1. Caractérisation des dynamiques

La dynamique peut s’exprimer de différentes façons non nécessairement exclusives :

  • la dynamique dans le réseau telle que la variation des flux portés par la connectivité du réseau,
  • la dynamique du réseau lui-même, correspondant à la variation de la topologie/structure du réseau.

De plus, ces deux dynamiques sont amenées à interagir et il est nécessaire alors d’étudier leurs pro-actions et rétro-actions.

2. Mesure de la dynamique

Il s’agit ici de pouvoir étudier et qualifier la trajectoire de l’évolution du réseau, avec la mise en évidence de certains comportements caractéristiques tels que des dynamiques lentes ou rapides ou encore des phénomènes de bifurcations.

L’inscription de cette dynamique dans le réseau conduit à des constructions morphologiques. L’étude de ce phénomène peut s’effectuer sous différents angles :

  • la genèse de l’apparition de ces formes (aspect stigmergique du processus : lien important entre la forme en construction et la dynamique),
  • la détection de formes localisées dans le réseau (réseaux sociaux, …) et la dynamique des processus d’auto-organisation qui en sont à l’origine,
  • l’influence du réseau global sur les processus émergents locaux.

Ces différents éléments amènent des questions telles que :

  • le réseau conserve-t-il les mêmes caractéristiques au cours de sa constitution ?
  • existe-t-il des étapes structurelles au cours de sa dynamique ?

 

3. Propriétés et maîtrise du réseau dans sa dynamique

La manipulation des grands réseaux en tant qu’outils de modélisation appelle à identifier des propriétés et des méthodes de contrôle ou de régulation.

On peut s’intéresser à l’expression de lois de conservation sur les réseaux en tant que structures discrètes et notamment transposer ces lois de manière opératoire sur des très grands réseaux. A l’opposé, on peut être amené à modéliser des effets dissipatifs.

Étudier la dynamique, c’est implicitement étudier la robustesse et la résilience. Comment des perturbations introduites sur le réseau modifient les trajectoires ?

Enfin, un problème important est celui du contrôle des trajectoires par des actions locales sur le réseau, et des dynamique multi-échelle. Comment une modification à un niveau d’échelle donné (par exemple au niveau méso : application d’une politique publique) se répercute sur les autres niveaux d’échelles ?


Structure et hiérarchie, classification

La hiérarchie peut signifier simplement un ordre d’importance entre les nœuds. Ordonner les nœuds permet de diriger les efforts vers les entités les plus importantes : les protéger (vaccination, sécurité, renforcement), les contrôler et surveiller, leur allouer plus d’effort pour les mesurer…

Mais de façon plus importante, parler de hiérarchie c’est parler de structures telle que dendrogrammes ou communautés hiérarchiques. Comprendre cette organisation multi-échelles est crucial pour comprendre à la fois comment les structures à grande échelle émergent d’interactions locales (de bas en haut) et réciproquement comment (de haut en bas) comment la structure globales (par exemple des institutions) influe sur les entités locales. Il faut bien sûr combiner ces deux approches, ce qui donnera une vision de l’échelle mésoscopique.

Beaucoup de méthodes fructueuses pour trouver de la structure dans un réseau ont été publiées : petit mondes et navigabilité, mesures de centralité, détection de communautés (cf. “Community detection in graphs”, Santo Fortunato, 2010)…
Il existe également des modèles de génération de réseau : attachement préférentiel, block model (voir “A Survey of Statistical Network Models”, Anna Goldenberg, Alice X. Zheng, Stephen E. Fienberg and Edoardo M. Airoldi, 2009). Une régression entre un tel modèle et des données permet de préciser sa structure.
Peut-on espérer une théorie plus unifiée ou un modèle intégré pour décrire la structure d’un réseau, adaptable à de nombreux cas particuliers ?

D’un point de vue technique, il manque toujours un logiciel générique pour analyser et visualiser les réseaux, bien qu’il existe des projets prometteurs (GePhi, Tulip…).


Classification

Il est classique de distinguer les réseaux naturels des réseaux artificiels. Les premiers on tendance à être assortatifs (ce que l’on appelle homophilie), leurs liens résultent d’affinités, tandis que les seconds font souvent preuve de l’effet inverse et des contraintes externes ont une influence (par exemple, des politiques publiques sur les réseaux commerciaux). Mais cette distinction sur l’origine des données a des limites dans ses capacités opératoires, il nous faut chercher d’autres classifications.

Il est aussi nécessaire d’avoir des approches différentes pour les petits et les grands réseaux : dans le premier cas on peut s’attacher à l’exhaustivité et apporter une attention à chaque nœud, tandis que le second exige une vision globale, un résumé du réseau.

Beaucoup de paramètres mesurables ont été définis (“Characterization of Complex Networks: A Survey of measurements”, L. da F. Costa, F. A. Rodrigues, G. Travieso and P. R. Villas Boas). Nous avons maintenant besoin d’une vision globale sur les invariants et propriétés pertinentes pour classifier les réseaux. Nous avons besoin de façons de comparer les réseaux entre disciplines, pour faciliter le portage de méthodes, pour obtenir des idées précises et des intuitions de tous les domaines.

 

 

Théorie et mesure des réseaux (2008)

Théorie et mesure des réseaux

Contributeurs : Cyril Bertelle, Jean-Philippe Cointet, Jean-Pierre Gaudin, Damien Olivier, Jean-Baptiste Rouquier

Mots-clefs : Réseau complexe, graphe de terrain, grand réseau d’interaction, graphe, hiérarchie, clustering, communautés, dynamique, robustesse, données partielles, données contextuelles

Introduction

La technologie actuelle produit des données à un rythme toujours plus rapide, et une partie de ces données peut être modélisée par des graphes. Dans de nombreux domaines, le point de vue graphe apporte un éclairage complémentaires aux analyses spécialisées propres au domaine. Cela permet notamment d’orienter les recherches vers les voies les plus prometteuses, d’appréhender la structure d’une grande masse de données. L’approche réseau est un moyen de travailler l’articulation multi-échelle qui caractérise la plupart des systèmes complexes.

Pour tenter de dessiner les contours du domaine des réseaux complexes, nous proposons les trois critères suivants : il s’agit de graphes qui sont

  • construits à partir de données d’observation
  • suffisamment grands pour permettre des statistiques et une approche agglomérative
  • évoluant essentiellement par des mécanismes locaux

Quels sont les verrous actuels de l’étude des réseaux ? Quelles sont les problématiques communes à plusieurs disciplines ? Au fil des pages de la feuille de route, les réseaux sont mentionnés plusieurs fois. Le but est ici d’identifier les problématiques communes, qui appellent des méthodes communes.

Défis

  • Structure et hiérarchie, classification (translation of this section at the end)
  • Classification

Recueil et formalisation des données

A. Incomplétude des données

La non-exhaustivité des données peut provenir de différents facteurs : coût de rassemblement, soucis de confidentialité, stratégie de rétention des possesseurs de données (capitalisation de l’information). Une partie de ce défi peut être aujourd’hui surmontée par des protocoles innovants de collecte de données. Notamment, l’obstacle des coûts ou de faisabilité peut être réduit par le recours à des protocoles qui s’appuient sur des dispositifs d’information embarqués, comme les téléphone portables, les dispositifs munis de puces RFID (type navigo/oyster), des logiciels proposés à l’utilisateur, etc.

Ces difficultés sont encore augmentées lorsque l’on souhaite faire un recueil longitudinal (encore appelé dynamique, ou diachronique) de données. La dynamique est par exemple cruciale pour étudier un réseau de déplacement de population (qui montre des cycles journaliers et saisonniers) et sa réaction aux incidents, ou bien l’infrastructure internet (le réseau de routeurs et serveurs) dont la dynamique est plus rapide que le processus de mesure.

Ces difficultés de collecte peuvent induire une description lacunaire des réseaux. Pour travailler avec des données lacunaires, il y a principalement deux voies :

  • utiliser des modèles artificiels pour compléter les trous ;
  • s’appuyer sur d’autres sources pour combler les manques (par exemple, utiliser des données statistiques et démographiques pour estimer les données manquantes)
  • prendre en compte, dès la mesure, un indicateur de confiance sur toutes les données (par exemple la probabilité qu’un lien dans les données existe réellement dans le système mesuré, ou bien un intervalle de confiance sur le poids d’un nœud). Puis adapter les méthodes à ce type de données.

 

B. Enrichissement du formalisme réseau

Le formalisme de base des réseaux s’appuie sur une approche relationnelle stricte (et homogène en termes de nœuds) qu’il s’agit ensuite de remettre en situation de plusieurs manières :

1. Introduire d’autres contextes

Il s’agit notamment d’approches géographiques : utiliser le contexte physico-spatial. D’autres contextes sont la démographie, l’économie et la politique. Par exemple, comment travailler sur des données concernant la préparation d’un projet, les présents aux réunions, comment mesurer l’implication des partenaires ?
Leur prise en compte appelle à un enrichissement de l’analyse des structures relationnelles, et vice-versa : l’approche réseau éclaire ces contextes.
L’art du modélisateur prend toute sa mesure sur ces problèmes, pour contrôler quelle information est perdue lors de la modélisation (par exemple en approximant l’économie d’une ville par sa population et quelques flux tels que eau et argent), nécessairement schématique. L’information entrée dans le modèle peut être largement améliorée.

2. Donner du relief

Les réseaux dont les relations sont purement binaires décrivent des situations décontextualisées. Il s’agit donc de développer des procédures à même de prendre en compte plus d’informations :

  • un cas en cours est celui des réseaux orientés(ou dirigés) et/ou pondérés(ou valués: les nœuds et liens ont un poids)
  • la superposition de réseau (multi-réseau)
  • la sémantique des liens (par exemple, contenu textuel attaché à un échange d’emails)
  • des nœuds hétérogènes (s’il y a deux types de nœud, c’est un réseau biparti, mais il peut y en avoir plus)
  • hyper-réseaux : formalisation d’un tissu relationnel qui se constitue autour d’événements, d’enjeux et de co-production qui engagent un ensemble d’agents.

 

Dynamique

La prise en compte de la dynamique dans les grands réseaux est essentielle pour leur approche dans le cadre de l’étude des systèmes complexes. Trois aspects sont à considérer et sont développés dans la suite : la caractérisation de ces dynamiques, la mesure des dynamiques elles-mêmes et les propriétés induites.

1. Caractérisation des dynamiques

La dynamique peut s’exprimer de différentes façons non nécessairement exclusives :

  • la dynamique dans le réseau telle que la variation des flux portés par la connectivité du réseau,
  • la dynamique du réseau lui-même, correspondant à la variation de la topologie/structure du réseau.

De plus, ces deux dynamiques sont amenées à interagir et il est nécessaire alors d’étudier leurs pro-actions et rétro-actions.

2. Mesure de la dynamique

Il s’agit ici de pouvoir étudier et qualifier la trajectoire de l’évolution du réseau, avec la mise en évidence de certains comportements caractéristiques tels que des dynamiques lentes ou rapides ou encore des phénomènes de bifurcations.

L’inscription de cette dynamique dans le réseau conduit à des constructions morphologiques. L’étude de ce phénomène peut s’effectuer sous différents angles :

  • la genèse de l’apparition de ces formes (aspect stigmergique du processus : lien important entre la forme en construction et la dynamique),
  • la détection de formes localisées dans le réseau (réseaux sociaux, …) et la dynamique des processus d’auto-organisation qui en sont à l’origine,
  • l’influence du réseau global sur les processus émergents locaux.

Ces différents éléments amènent des questions telles que :

  • le réseau conserve-t-il les mêmes caractéristiques au cours de sa constitution ?
  • existe-t-il des étapes structurelles au cours de sa dynamique ?

 

3. Propriétés et maîtrise du réseau dans sa dynamique

La manipulation des grands réseaux en tant qu’outils de modélisation appelle à identifier des propriétés et des méthodes de contrôle ou de régulation.

On peut s’intéresser à l’expression de lois de conservation sur les réseaux en tant que structures discrètes et notamment transposer ces lois de manière opératoire sur des très grands réseaux. A l’opposé, on peut être amené à modéliser des effets dissipatifs.

Étudier la dynamique, c’est implicitement étudier la robustesse et la résilience. Comment des perturbations introduites sur le réseau modifient les trajectoires ?

Enfin, un problème important est celui du contrôle des trajectoires par des actions locales sur le réseau, et des dynamique multi-échelle. Comment une modification à un niveau d’échelle donné (par exemple au niveau méso : application d’une politique publique) se répercute sur les autres niveaux d’échelles ?


Structure et hiérarchie, classification

La hiérarchie peut signifier simplement un ordre d’importance entre les nœuds. Ordonner les nœuds permet de diriger les efforts vers les entités les plus importantes : les protéger (vaccination, sécurité, renforcement), les contrôler et surveiller, leur allouer plus d’effort pour les mesurer…

Mais de façon plus importante, parler de hiérarchie c’est parler de structures telle que dendrogrammes ou communautés hiérarchiques. Comprendre cette organisation multi-échelles est crucial pour comprendre à la fois comment les structures à grande échelle émergent d’interactions locales (de bas en haut) et réciproquement comment (de haut en bas) comment la structure globales (par exemple des institutions) influe sur les entités locales. Il faut bien sûr combiner ces deux approches, ce qui donnera une vision de l’échelle mésoscopique.

Beaucoup de méthodes fructueuses pour trouver de la structure dans un réseau ont été publiées : petit mondes et navigabilité, mesures de centralité, détection de communautés (cf. “Community detection in graphs”, Santo Fortunato, 2010)…
Il existe également des modèles de génération de réseau : attachement préférentiel, block model (voir “A Survey of Statistical Network Models”, Anna Goldenberg, Alice X. Zheng, Stephen E. Fienberg and Edoardo M. Airoldi, 2009). Une régression entre un tel modèle et des données permet de préciser sa structure.
Peut-on espérer une théorie plus unifiée ou un modèle intégré pour décrire la structure d’un réseau, adaptable à de nombreux cas particuliers ?

D’un point de vue technique, il manque toujours un logiciel générique pour analyser et visualiser les réseaux, bien qu’il existe des projets prometteurs (GePhi, Tulip…).


Classification

Il est classique de distinguer les réseaux naturels des réseaux artificiels. Les premiers on tendance à être assortatifs (ce que l’on appelle homophilie), leurs liens résultent d’affinités, tandis que les seconds font souvent preuve de l’effet inverse et des contraintes externes ont une influence (par exemple, des politiques publiques sur les réseaux commerciaux). Mais cette distinction sur l’origine des données a des limites dans ses capacités opératoires, il nous faut chercher d’autres classifications.

Il est aussi nécessaire d’avoir des approches différentes pour les petits et les grands réseaux : dans le premier cas on peut s’attacher à l’exhaustivité et apporter une attention à chaque nœud, tandis que le second exige une vision globale, un résumé du réseau.

Beaucoup de paramètres mesurables ont été définis (“Characterization of Complex Networks: A Survey of measurements”, L. da F. Costa, F. A. Rodrigues, G. Travieso and P. R. Villas Boas). Nous avons maintenant besoin d’une vision globale sur les invariants et propriétés pertinentes pour classifier les réseaux. Nous avons besoin de façons de comparer les réseaux entre disciplines, pour faciliter le portage de méthodes, pour obtenir des idées précises et des intuitions de tous les domaines.