Analyse des forces et des faiblesses d’un réseau avec R : le package NetSwan
Suite à l’école thématique RESEM « Etudier les réseaux sociaux : espaces, mobilités » qui s’est tenue du 21 au 25 septembre sur l’île d’Oléron, je me suis dit qu’il serait pertinent de sensibiliser davantage d’autres disciplines aux extensions que je développe concernant l’analyse des forces et des faiblesses des réseaux. En effet, durant cette école thématique pluridisciplinaire, seuls des géographes m’ont posé des questions concernant le plugin QGIS que je développe périodiquement. Il faut dire que les SIG restent avant tout utilisés par des géographes et que le plugin en question se focalise sur des réseaux spatiaux !
Ainsi, durant la semaine de pause pédagogique de cette fin d’octobre, j’ai entrepris d’écrire quelques fonctions permettant d’analyser les forces et les faiblesses d’un réseau à l’aide du logiciel R. Puis, afin de diffuser ces fonctions, je n’ai trouvé d’autres solutions que de produire un package. Autant le dire de suite, l’aide est très cursive et rédigée dans un anglais très moyen. Néanmoins, ce package est depuis le 31 octobre disponible sur le CRAN. Une des tâches les plus difficiles a finalement été de trouver un nom à ce package : ce sera finalement NetSwan pour « NETwork Strengths and Weaknesses ANalysis ». Ce package repose sur le package Igraph.
Cette version 0.1 est un ballon d’essai visant à étudier si ces développements sont pertinents en dehors du champ des réseaux spatiaux. Ainsi, seulement quatre fonctions sont proposées actuellement. Une fonction « swan_efficiency » qui se focalise sur la comparaison des valeurs d’éloignement entre le réseau normal et le réseau perturbé. Une fonction « swan_closenness » qui se focalise sur la comparaison des valeurs de proximité entre le réseau normal et le réseau perturbé. Une fonction « swan_connectivity » qui mesure le nombre de relations rendues impossibles lorsqu’un nœud est supprimé. Une fonction « swan_combinatory » qui reproduit les algorithmes d’erreurs et d’attaques développés par Albert et al. [1] [2].
Au-delà des exemples proposés dans l’aide, nous pouvons désormais analyser un réseau social aspatial comme le Zachary Karaté Club et tester sa résistance aux algorithmes développés par Albert et al. Pour cela, il convient de taper le code suivant :
res<-swan_combinatory(karate,10)
Le plus long consiste finalement à produire le graphique représentant les résultats de l’analyse :
col=c(“yellow”,”blue”,”red”, “orange”))
Le code final est disponible ici. Il apparaît qu’avec 3 nœuds supprimés, il est possible de perturber plus de 60% des relations de ce réseau, quel que soit le type d’attaques. Seules les erreurs aléatoires produisent des perturbations moins importantes.
Si le besoin s’en fait ressentir, les pistes de développement pour ce package sont nombreuses. Premièrement, ce package ne supporte que les graphes définis avec igraph, il serait tout aussi pertinent de permettre l’analyse de graphes construits avec d’autres packages, comme par exemple statnet. Deuxièmement, les fonctions développées dans NetSwan proviennent avant tout de travaux se focalisant sur l’analyse des forces et des faiblesses de réseaux spatiaux. Il conviendrait de développer plus de fonctions qui tiennent compte des particularités des réseaux non spatiaux.
OpenEdition vous propose de citer ce billet de la manière suivante :
Serge Lhomme (7 novembre 2015). Analyse des forces et des faiblesses d’un réseau avec R : le package NetSwan. groupe fmr (flux, matrices, réseaux). Consulté le 4 octobre 2024 à l’adresse https://doi.org/10.58079/p84u
Hello again,
OK pour les points (1) et (2), qui tiennent du détail.
Pour le point (3), j’ai bien compris qu’il s’agissait de “prendre l’inverse des distances et d’en faire la somme” ; c’est ce que je fais dans le code, avec les mêmes résultats que le votre. Simplement, tout le code de la fonction
swan_closenesspeut du coup s’écrire comme un cas spécial de la fonctionswan_efficiency.Je comprends aussi l’intérêt de passer les distances infinies à 0 ; ce que je ne comprends pas, c’est pourquoi seule la fonction
swan_closenessle fait. Dans mon code, je le fais aussi pourswan_efficiency, qui renvoie sinon desNaN. Il suffit de rajouter deux noeuds de degré nul à l’exemple publié, comme je le fais ici, pour illustrer le problème.Sur le point (4), je comprends mieux l’inversion des termes dans la soustraction, et effectivement, ce n’est pas deux fois la somme des distances du graphe qui est soustraite, mais deux fois la somme des distances passant par le noeud que l’on supprime,
sum(cl_g[ v, ])etsum(cl_g[ ,v ]).Dernière question (pour de vrai) : dans
swan_connectivity, les distances non-infinies sont codées 0 et les distances infinies sont codées 1. En revanche, dansswan_combinatory, c’est l’inverse—ce dont je me suis rendu compte en réécrivant l’algorithme. Est-ce normal ?Re,
Je ne repasse pas les distances infinies à zéro pour swan_efficiency, car cela m’indique si la suppression d’un noeud engendre une rupture de la connexité du graphe. En revanche, si vous partez avec un réseau qui n’est pas connexe, l’algo se retrouve à devoir effectuer une différence entre deux valeurs infinies, d’où les valeurs Nan. Mais cela n’est pas plus mal, car cela vous indique que la notion d’allongement dans un graphe qui n’est pas initialement connexe est en fait problématique à traiter. C’est un cas que je n’ai jamais rencontré sur les réseaux techniques que je traite d’habitude. A l’heure actuelle, je n’ai pas assez de recul pour vous dire ce qu’il est pertinent de faire, si ce n’est de privilégier swan_closeness quand le graphe n’est pas connexe initialement. Je vais y réfléchir et peut-être limiter cette fonction au graphe initialement connexe.
Pour la dernière question, dans les deux cas, je cherche à obtenir le nombre de relations rendues impossibles par des suppressions de noeuds. Dans swan_connectivity, comme je ne supprime qu’un noeud, je peux décompter facilement ce nombre à l’aide des valeurs infinis. En revanche, pour swan_combinatory lorsque dix noeuds ont été supprimés par exemple, si j’effectue la même manipulation, j’obtiens le nombre de relations rendues impossibles dans un réseau qui est très différent par rapport à celui de départ. Cette valeur n’a alors plus grand sens. Il convient en fait de compter le nombre de relations qui restent toujours possibles dans ce graphe fortement perturbé et de le soustraire au nombre de relations possibles sur le réseau de départ. D’où une différence dans le code : dans un cas je cherche directement le nombre de relations impossibles, dans l’autre je compte au préalable le nombre de relations toujours possibles.
Merci pour vos réponses détaillées, je comprends mieux le comportement des fonctions.
Limiter
swan_efficiencyaux graphes connexes paraît recommandable, en tout cas plus qu’un vecteur deNaN, qui n’a pas grande signification. Renvoyer desNA, à la rigueur ?Un autre chouette billet. J’ai fait comme avec le précédent, j’ai repris le code pour essayer de mieux comprendre ce qui se passe sous le capot. Voici le résultat pour les trois premières fonctions du package (efficiency, closeness, connectivity).
Quelques remarques :
1. Je n’ai pas compris à quoi servent les objets
arcetnoeud, qui sont créés mais non utilisés dans les fonctions.2. J’ai légèrement optimisé le code en utilisant
vcountetdelete_verticespour gagner du temps de calcul.3. La fonction
swan_closenesspeut être codée comme une sous-application de la fonctionswan_efficiency.Je n’ai pas non plus très bien compris comment les distances infinies sont gérées : la fonction
swan_closenessles prend en compte en les retirant des calculs, alors que les deux autres fonctions les conservent.Dernière question : j’ai du mal à comprendre le rapport entre ces différentes fonctions et la “closeness vitality” publiée dans Brandes et Erlebach. Si j’ai bien compris, cette dernière s’écrit
c_{CV} (x) = I_W (G) - I_W (G \setminus {x})où
I_W (G)est l’index de Wiener du graphe G, etI_W (G \setminus {x})l’index de Wiener du même graphe après que l’on a retiré le noeudx.Toujours si j’ai bien compris, la fonction
swan_efficiencyy ressemble, sauf que les termes de la soustraction sont inversés (pourquoi ?) et que l’on enlève également deux fois la somme des distances du graphe (pourquoi ? bis) ; la fonctionswan_closenessfait également pareil, mais en prenant l’inverse des distances.Merci,
1. Effectivement, question d’habitude.
2. Ok.
3. ?
Dans swan_closeness, j’opte pour l’astuce qui consiste à prendre l’inverse des distances et d’en faire la somme, et non pas à prendre la somme des distances et à calculer l’inverse de cette somme. Effectivement, cela revient presque à calculer la closeness vitality. Cette solution permet de synthétiser deux phénomènes différents, les pertes de connectivités et les problématiques d’allongement engendrées par la suppression d’un nœud. Bref, c’est un algo pratique, mais à utiliser avec précaution selon moi, d’où l’existence de swan_efficiency qui est focalisée sur les problématiques d’allongement et swan_connectivity qui se focalise sur les pertes de connectivité. De plus, s’il peut exister des distances infinies, il existe toujours des distances égales à zéro : les distances d’un noeud à lui même. Or, ces distances n’ont pas à intervenir dans le calcul et quand on calcule l’inverse de ces distances cela donne des valeurs infinies. C’est pourquoi je repasse logiquement ces valeurs à zéro avant d’effectuer la somme finale, c’est une juste une façon de coder et ainsi d’éviter des exceptions et des boucles coûteuses en temps de calcul. Les fonctions de R sont très efficaces, c’est pourquoi je les privilégie par rapport à un codage plus classique.
Enfin, pour swan_efficiency, l’algo se focalise donc sur des calculs d’allongement. La différence est inversée, car on ne peut avoir que des valeurs d’un seul signe : autant que ce signe soit positif. Ainsi plus la valeur est importante, plus les allongements provoqués par la suppression d’un nœud sont importants. C’est à mon sens plus compréhensible dans ce sens. Attention, je n’enlève pas deux fois la somme des distances du graphe. En fait, l’algo prend le soin de retirer la somme des distances partant d’un point et arrivant à ce point (lorsque le réseau est normal), car ce point n’existe plus quand on le supprime (lorsque le réseau est perturbé). Prendre en compte ces valeurs dans la comparaison n’est ainsi pas justifié. C’est une précaution rarement prise je vous l’accorde.