Réseaux Sociaux et Systèmes de Réunions Planifiées

J’ai terminé le premier volet de ma simulation du « Corporate Meeting System » (CMS, système réunionnel) sur les traces des expériences sur les réseaux sociaux de Duncan Watts. Je vais décrire cette simulation et livrer quelques premiers résultats. Une analyse plus sérieuse sera faite lorsque j’aurai terminé une véritable campagne de mesure sur des graphes de grande taille.
Ce message est de nature un peu technique, je m’en excuse à l’avance auprès de mes lecteurs occasionnels.

1. L’objet de l’étude

Les principes généraux on été décrits dans mon message de Mai. Je m’intéresse à un graphe dont les nœuds sont les acteurs (les managers) d’une entreprise et les arêtes sont les besoins en termes d’interaction. Chaque arête représente le fait que deux personnes ont besoin de se voir (régulièrement) et la valeur affectée à l’arête (étiquette) représente la fréquence souhaitée de contact.
Je génère des graphes aléatoires, d’une taille allant de 100 personnes à 1000 (il me faudra aller plus loin, mais les algorithmes que je vais expliquer par la suite sont assez gourmand). Le graphe est aléatoire, mais sa « géométrie » est contrôlée par un degré de « clusterisation » (le facteur C de Duncan Watts). De façon simplifiée, le « custering coefficient » représente le taux de connexion entre des voisins d’un même nœud. Un taux voisin de 1 signifie que le graphe est quasi-transitif (les amis de mes amis sont mes amis). Le facteur C est important puisque de nombreuses études sur des réseaux sociaux réels montrent qu’ils on un facteur élevé de clusterisation.
Pour pouvoir juger de l’impact de ce que j’ai appelé de « diamètre informationnel » (c'est-à-dire le degré moyen des nœuds, ou autrement dit le nombre moyen de personnes que chaque acteur doit rencontrer en un mois), je contrôle également ce paramètre lors de la génération du graphe aléatoire. La génération du graphe est simple, ce qui l’est un peu moins est de générer des étiquettes de fréquence de telle sorte que la somme des fréquences soit 1 pour chaque nœud. Je fais cela avec une heuristique grossière, mais il m’a fallu du temps pour la mettre au point et cela mériterai un petit peu de recherche bibliographique pour trouver une solution exacte. Il existe bien entendu une infinité de solution. J’utilise un paramètre de l’heuristique pour contrôler la « régularité » de ces fréquences (pour aller d’une situation ou chaque voisin est vu avec la même fréquence à une situation ou il y a une distribution exponentielle de ces fréquences).

Dans la suite de cet exposé, une expérience est définie par un réseau social donné (avec ses caractéristiques : degré, taux de « clusterisation », forme de la distribution des fréquences .


2. Le principe de l’étude

Le principe est de construire un ensemble de réunions qui couvre le mieux possible les besoins en interactions, exprimé par le réseau social que nous venons de décrire.
Il se trouve que c’est un problème non-trivial, ce qui est intéressant en soi puisque chaque entreprise le résout de façon implicite chaque jour. Après différents tâtonnements, j’ai implémenté un algorithme « glouton » (sans recherche) qui correspond à l’heuristique suivante :

1. Choisir le contact le plus utile (c'est-à-dire une arête (x,y) du réseau social de départ)
   - L’utilité est fonction de la fréquence demandée pour (x,y) et du « taux courant de réunion » (somme des fréquences déjà affectée aux hyper-arêtes existantes) pour x et y.
   - Si il existe déjà une solution de contact entre x et y avec une fréquence moindre, l’intérêt s’en trouve réduit d’autant (c’est la différence que l’on considère : fréquence demandée – fréquence déjà supportée)
   - Cette notion d’ « intérêt » tient donc compte implicitement des fréquences déjà assignées à x et y, de telle sorte que la somme des fréquences par nœud, une fois que l’algorithme termine, est à peu près constante.
2. S’il existe une réunion (hyper-arête) qui supporte ce contact, l’arête est ajoutée à cette réunion,
   - Une hyper-arête est définie par un ensemble d’arêtes du réseau social, dont on tire : (a) la liste des nœuds, (b) la fréquence de la réunion en fonction des fréquences des arêtes (le maximum X un facteur de modération qui est un paramètre de l’heuristique)
3. Sinon on crée une nouvelle réunion
   - La « stratégie de création de réunion » précise la taille minimale et maximale (le nombre de nœuds), ainsi que le coefficient de « modération de fréquence »
   

J’ai fait quelques essais de "randomization", mais elles n’ont pas donné de résultats intéressants. Un sujet à traiter par la suite serait de trouver de meilleures heuristiques. Mais, comme je l’ai déjà signalé, il est peu probable que les méthodes des entreprises soient optimales …
La question de l’équilibrage des fréquences est un peu délicate, il faudrait implémenter un algorithme d’optimisation locale pour corriger les sommes approchées.

A titre d’exemple, voici une simulation :
=== 338 meetings (7.895 meet/pers), avg frequency = 13.21301775, avg size = 9.34
3195266, MD = 56.065, cRate = 17

obtenue sur un graphe de 400 nœuds, qui produit 338 réunions (le réseau social ayant 18688 arêtes, un degré moyen ID de 93, et un facteur C de 0.5). La fréquences est exprimée en heures/mois (200 => 1 reunion unique en boucle,1 => une fois par mois). La taille moyenne est le nombre moyen de participants, MD est le diametre réunionel (cf. les messages précédents : le nombre des personnes que je vois une fois par mois dans une des réunions). On peut définir un taux de clusterisation (cR) de la même façon.

J’ai encapsulé les paramètres de l’heuristique dans un objet appelé « stratégie de création de réseau d’affiliation ». Je peux jouer avec ces paramètres et j’ai créé de nombreuses situations en fonction :

• Du nombre de participants en réunion.
• De la fréquence moyenne des réunions.
• De la distribution de cette fréquence
  

Je peux facilement tester des stratégies hybrides, correspondant à une structure « de petits mondes » (cf. les messages précédents : beaucoup de petites réunions fréquentes et quelques grosses réunions plus espacées).


3. La réalisation de l’étude

La simulation consiste donc à :

• Construire une expérience, c'est-à-dire un réseau social.
• Choisir une stratégie de couverture par un réseau d’affiliation, c’est-à-dire générer les hyper-arêtes
• Calculer les distances et longueurs moyennes en tirant aléatoirement 1000 paires de nœuds. La génération aléatoire tient compte de la fréquence : les paires ont une chance d’être tirée qui est proportionnelle à l’étiquette sur le réseau social.

Le calcul de la distance se fait avec un algorithme de plus court chemin (Dijkstra) pour produire trois informations :

• Le degré de séparation : plus petit chemin en nombre d’arêtes.
• La distance : plus court chemin en utilisant l’inverse des féquence comme distance sur les arêtes. La somme des inverses des fréquences représente le temps de propagation de l’information (pour s’en convaincre : plus une réunion est fréquente, plus la propagation qu’elle assure est rapide).
• La longueur du chemin associé (pas forcément le degré de séparation, puisque les plus court chemins ne coïncident pas selon les deux distances).

Pour obtenir des résultats plus stables, chaque simulation est repété plusieurs fois (10 aujourd’hui parce que j’étais pressé, il faudra que je contrôle la déviation et que j’ajuste, probablement à 100).

A titre d’exemple, voici ce que l’on obtient :

-- experiment line [ 552s ] -------------------
ID cld frd deg MD cls fqr path dist sep d(dis)
92.27 46 39 8.5275 64.36 17 39 2.37 6.93 1.60 0.376

Ici la distance moyenne (durée de propagation) est de 6.93 heures (37% de déviation), pour un degré de séparation de 1.6 et une longueur de chemin de 2.37.

4. Premiers résultats

• Le degré de clusterisation du réseau social est un facteur d’efficacité pour le système réunion (on s’en serait douté). Il reste à examiner ce qui se passe dans les cas extrêmes, mais ils ne sont pas forcément représentatif (il y a une transition de phase puisque lorsqu’on force la clusterisation à degré constant, on casse la connectivité globale).
• Le diamètre réunionnel optimal semble suivre la loi prévue (cf. message précédent), à confirmer avec un gros volume d’expériences. Il faudra également caractériser la loi d’évolution du temps de propagation optimal.
• L’influence de la distribution des fréquences dans le réseau social initial reste à caractériser mais il est clair que le problème de couverture devient plus difficile si les fréquences sont homogènes. On obtient un temps de propagation qui est multiplié par 10 si toutes les fréquences sont les mêmes. Ceci s’explique simplement par le fait que l’heuristique fonctionne bien et « capture » les clusters qui existent sous forme de réunion.
  Il y a une bonne stabilité des stratégies de création de réunion par rapport aux expériences … à confirmer. Ce serait plutôt encourageant quant à la pertinence de ce travail (il ne servirait à rien d’optimiser un système réunion si celui-ci est instable par rapport aux conditions de l’entreprise).
• Le diametre réunionel optimal correspond à des réunions fréquentes (donc pas très nombreuses). Par exemple, pour un des exemples de 400 personnes, il est de 46.
  La longueur du chemin optimal peut être améliorée avec une structure mixte « de petit monde » - cf. messages précédents – mais l’amélioration n’est pas très significative avec des graphes à 100 ou 400 nœuds. A creuser lorsque j’aurai des études plus complètes.

Je vais revenir à d’autres expériences pour un exposé que je prépare sur les systèmes complexes, donc la suite arrivera à la fin de l’année, probablement sous la forme d’un article de recherche.