Ecole d’été Ferney-Voltaire, Les réseaux, août 2014 (suite)

Ci-dessous, une présentation réalisée à l’occasion de l’Université d’été Ferney-Voltaire consacrée aux réseaux (voir le programme sur le site http://ferney2014.sciencesconf.org/). Cette présentation a servi de support pour l’atelier PAJEK.

Elle comprend une brève introduction à l’analyse de réseau, une présentation des objets réseaux, partitions et vecteurs tels qu’ils doivent être manipulés et mis en forme dans Pajek. On y trouve une description des différentes opérations de type « network+partition » à savoir: extraction d’un sous-graphe, réduction d’un graphe en graphe image, création d’une vue contextuelle.

Pour finir une manipulation est proposée sur un sous-graphe du réseau « world.trade » (lequel est téléchargeable depuis le lien suivant: http://vlado.fmf.uni-lj.si/pub/networks/data/esna/metalWT.htm). A l’issue de cette manipulation, une représentation du réseau européen de commerce est exportée en format vectoriel (svg), chargée et retravaillée dans le logiciel Inkscape afin d’enrichir le contenu et la valeur de la représentation. En particulier, pour en améliorer la lisibilité: on montre qu’il convient d’y ajouter un titre et une légende.

Atelier Pajek Ferney 2014

La détection de communautés avec Pajek 3.6

La toute nouvelle version de Pajek réserve de bonnes surprises aux explorateurs de graphes complexes.

Les nouveautés dont il est question ici ont été ajoutées au logiciel entre Mai 2012 et Septembre 2012.

Deux algorithmes de détection de communautés ont été implémentés:

Network/Create Partition/Communities

-Louvain method

Le premier algorithme s’appuie sur la méthode de Louvain [1]. Cette méthode est bien adaptée aux graphes valués, y compris s’ils sont signés. Comme pour beaucoup d’algorithmes de clustering (ou détection de communautés), la qualité du partitionnement est optimisée par maximisation de la fonction de modularité [2].  L’indice de modularité mesure la différence entre la densité d’un graphe (ou sous-graphe) donné et la densité d’un graphe aléatoire possédant les même caractéristiques (nombre et poids des liens).

Principe

Maximiser la fonction de modularité pour partitionner un graphe revient à s’assurer que le nombre et le poids des liens est plus important à l’intérieur des partitions qu’entre les partitions. Pour l’exprimer autrement, il faut que la densité intra-communautaire dépasse la densité inter-communautaire.

La méthode de Louvain est « bottom-up » et multi-niveau. Au lancement de l’algorithme, tous les sommets appartiennent à une partition différente. Ils sont regroupés, par itération, dans des partitions de modularité optimale. Arrivé à une première situation d’optimum, le processus se poursuit au niveau supérieur : chaque partition est traitée comme un sommet et ainsi de suite. L’opération continue jusqu’à ce qu’il n’y ait plus aucun gain de modularité possible.

Avantage

Cette approche permet d’échapper au défaut de la modularité connu sous le nom de « limite de résolution » [3]. Si le fait d’associer une partition du premier niveau avec une autre devait engendrer une perte de modularité, cette association ne serait pas réalisée par la méthode de Louvain. De ce fait, les petites structures dotées d’une bonne modularité ne risquent pas d’être noyées dans des structures plus grandes et moins significatives. C’est ce qu’il risquerait d’arriver avec un algorithme « top-down » appliqué à un trop grand graphe.

Inconvénient

Le défaut connu de la méthode provient de la sensibilité du résultat à l’ordre de traitement des sommets. L’ordre dans lequel les sommets sont considérés a une influence sur le partitionnement. De ce fait, il peut être utile de procéder à des permutations pour s’assurer de la robustesse du résultat [4]. L’autre piste est d’imposer un ordre qui tienne compte des caractéristiques du réseau [5].

En plus de l’algorithme classique de Louvain,  Pajek propose une variante (avec rafinement multi-niveau) qui tend à donner de meilleurs résultats pour les grands graphes [6]. La méthode de Louvain est également disponible dans les logiciels Gephi et NetworkX ainsi que dans la librairie igraph du logiciel R, l’algorithme étant plus rapide sur Pajek que sur Gephi.

-VOS Clustering

La méthode de détection de communauté VOS optimise une autre fonction de qualité que la fonction de modularité: la fonction dite de VOS clustering [7]. Il s’agit d’une variante pondérée de la modularité qui a été pensée pour le traitement des données bibliométriques. Cette technique donne moins de poids qu’une méthode classique aux sommets à très haut degré. Contrairement à la méthode de Louvain, elle dépend d’un algorithme « « top-down« . Pour cette raison, le seul moyen d’échapper au problème de limite de la résolution consiste à faire varier le paramètre de résolution.

Cette méthode convient en fait aux graphes pour lesquels la valeur des liens rend compte de l’importance de la similarité entre les sommets. Ses concepteurs ont souhaité que soit associé à l’algorithme de clustering un algorithme de visualisation faisant appel au même principe mathématique. Cette approche unifiée permet d’éviter qu’ils y ait des incohérences entre le résultat du processus de clustering et la représentation graphique de ce résultat.

Tout naturellement, Pajek propose aussi l’algorithme de visualisation VOS. Il fonctionne sur le principe de l’optimisation de la fonction de qualité dite de VOS mapping. Étant donné la proximité des deux méthodes de détection, il n’est surement pas impensable d’utiliser le VOS mapping pour représenter un graphe partitionné suivant la méthode de Louvain.

Aller plus loin

Une comparaison des deux méthodes de détection est accessible sur: http://mrvar.fdv.uni-lj.si/pajek/community/LouvainVOS.htm

Des précisions sur l’utilisation de ces méthodes avec Pajek se trouvent aussi sur le site: paramétrage, évaluation de la qualité du partitionnement, représentation graphique du résultat.

Depuis l’interface graphique de Pajek, un raccourci vers le logiciel VOSviewer offre la possibilité d’obtenir rapidement une représentation  élégante du partitionnement.

Ci-dessous, un exemple à partir des données de collaborations scientifiques néerlandaises (Source: Web of Science 2006-2008):

Références
[1] V. Blondel, J.-L. Guillaume, R. Lambiotte, et E. Lefebvre, « Fast unfolding of communities in large networks », Journal of Statistical Mechanics, vol. 2008, no 10, sept. 2008.
[2] Il existe de nombreuses autres méthodes de détection de communautés. Pour avoir un aperçu de l’existant: S. Fortunato, « Community detections in graphs », Physics and Society, vol. 2010, no 486, p. 75-174.
[3] S. Fortunato et M. Barthélemy, « Resolution limit in community detection », Proceedings of the National Academy of Sciences of the United States of America, vol. 104, no 1, p. 36-41, janv. 2007.
[4] V. Blondel, G. Krings, et I. Thomas, « Régions et frontières de téléphonie mobile en Belgique et dans l’aire métropolitaine bruxelloise », Brussels studies, no 42, oct. 2010.
[5] P. De Meo, E. Ferrara, G. Fiumara, et A. Provetti, « Generalized Louvain method for community detection in large networks », under review, 2011. URL: http://www.emilio.ferrara.name/wp-content/uploads/2011/07/isda2011-k-path.pdf
[6] R. Rotta et A. Noack, « Multilevel local search algorithms for modularity clustering », Journal of Experimental Algorithmics, vol. 16, no 2.3, 2011.
[7] L. Waltman, N. J. van Eck, et E. C. M. Noyons, « A unified approach to mapping and clustering of bibliometric networks », Journal of Infometrics, vol. 4, no 4, p. 629-635, oct. 2010.

 

Cartographier flux et relations avec Paj2KML

Le logiciel Paj2KML est un petit utilitaire Windows bien utile pour qui souhaite combiner graphe et représentation cartographique.

Le fichier .exe doit être placé dans le même dossier que :

  • un graphe Pajek au format .net

Lancer le logiciel produit alors un fichier .kml qu’il est possible de superposer à une vue Google Earth ou Google maps. Le plus pratique reste cependant d’ouvrir le fichier .kml et de copier/coller le contenu ici : http://display-kml.appspot.com/. La carte apparaît quelques secondes plus tard. Il n’est pas possible de l’exporter en format image ou vectoriel, seule la capture d’écran est possible.

L’exemple ci-dessous utilise l’un des jeux de données sur les relations entre les villes mondiales du GaWC (http://www.lboro.ac.uk/gawc/datasets/da7.html).  Il s’agit d’un indice variant entre 0 et 1 et mesurant l’intensité des échanges de services entre villes. Le graphe de départ est complet, différents seuils ont été testés afin de produire une visualisation lisible.  Seuls les liens supérieurs à 0.4 ont été gardés.

Les deux images ci-dessous montrent le graphe généré par Pajek (algorithme de Kamada-Kawai > Free) et la carte correspondante générée par display-klm.

Visualisation produite par Pajek

Résultat obtenu avec Paj2KLM

La principale limite est évidemment la projection Mercator qui se prête particulièrement mal à la représentation de flux mondiaux. De plus, si la vue globale peut faire illusion, zoomer sur la carte (voir ci-dessous) montre que la précision de l’outil est très relative…

Visulisation produite par Paj2KLM - détail

Le fichier groupefmr_Paj2KML.zip téléchargeable ci-dessous contient trois fichiers : le jeu de données du GaWC original au format .net, le même fichier mais uniquement avec les liens supérieurs à 0.4 et enfin le fichier .txt avec les coordonnées de 55 villes concernées. Les liens internet et le descriptif des fichiers  se trouvent dans LISEZ_MOI.txt.

Dossier .zip téléchargeable ici.

Merci à Marion Maisonobe d’avoir attiré mon attention sur cet utilitaire il y a de nombreux mois déjà.

Plus d’informations et d’exemples sur la page http://www.leydesdorff.net/gmaps/.

Après Pajek, Pajek XXL

Logo de Pajek XXLUne version spéciale de Pajek, dédiée à l’analyse des énormes graphes (huge graph), est disponible depuis maintenant près d’un an pour les systèmes d’exploitation Windows 32 et 64 bits.

D’après le site officiel, cette version XXL permet l’analyse de graphes peu denses (sparse networks) comptant jusqu’à plusieurs dizaines de millions de sommets, à condition bien sûr que l’ordinateur puisse stocker les résultats générés.

L’interface ne change guère, excepté l’absence du menu Draw et, inversement, la présence du menu VertexID. Ce dernier permet de nommer les sommets de 1 à n, les sommets étant par défaut anonymes afin de garder un maximum d’espace mémoire disponible.

 Interface du logiciel Pajek XXL

Avant de s’amuser avec des graphes monstrueux, il est prudent de déterminer la mémoire disponible sur son ordinateur avec la fonction Info > Memory (ou F11), surtout après avoir généré un graphe volumineux. La capture d’écran ci-dessous montre les informations obtenues.

Message obtenu avec Info > Memory

Afin ne pas saturer l’espace disponible, les auteurs recommandent de répondre No quand Pajek demande si l’on souhaite créer un nouveau réseau. Pour mémoire (mais je renvoie au billet écrit avec Pierre Mercklé dans Quanti/Sciences sociales [1]), à chaque opération ou presque, Pajek crée de nouveaux réseaux correspondant aux résultats de ces opérations. On s’en doute, si le  graphe de départ est monstrueux, les fichiers correspondants aux résultats ne seront pas très légers.

L’utilisation attendue par les auteurs est double :

  • mesures directes sur un gros graphe ;
  • extraction d’un sous-graphe pertinent pouvant être analysé et visualisé avec le programme Pajek standard.

Les exemples proposés par les auteurs sont d’un intérêt limité dans la mesure où, comme ils l’écrivent eux-mêmes, les mêmes traitements pourraient être réalisés sans problème avec le Pajek standard. L’absence de visualisation pourra gêner celles et ceux qui restent persuadé-e-s que l’exploration visuelle reste la démarche primordiale en analyse de graphes.

Enfin, il est possible de s’interroger sur les utilisateurs et utilisatrices potentiel-le-s de ce programme. A priori, si je sais générer des graphes de millions de sommets, je n’ai pas spécialement besoin d’un logiciel clicodrome… Mais dans la mesure où les packages R se heurtent vite à des problèmes de mémoire disponible, ce Pajek-XXL peut constituer ne piste alternative ou complémentaire intéressante. A tester donc…

Téléchargement et informations : http://mrvar.fdv.uni-lj.si/pajek/default.htm

[1] Beauguitte Laurent et Pierre Mercklé (2011), “Analyse des réseaux : une introduction à Pajek”, Quanti, mis en ligne le 6 juin 2011, URL : http://quanti.hypotheses.org/512/.