Chapitre 6 Analyses de réseaux
library(igraph)
<- graph.data.frame(links,nodes,directed=TRUE)
graph <- graph.adjacency(df,mode="directed") graph
6.1 Bases de la théorie
- Graphe : ensemble d’unités (sommets) connectées par une ou plusieurs relations (arêtes)
- Sommets (noeuds, vertices) : unités
- Arêtes (liens, edges) : relations
- Réseaux complets v réseaux personnels (réseaux égo-centrés)
# Taille du réseau = nombre de noeuds
length(V(graph))
# Nombre de liens
length(E(graph))
6.1.1 Matrices
Ou comment stocker ses données avant de les traiter.
- d’adjacence
- matrice symétrique avec liens non-orientés (du coup liens réciproques)
- Carrée \(n* n\)
- Edge list : chaque paire de noeuds connectés sur une ligne d’une table
- Node list : chaque ligne représente les liens d’un noeud vers tous les autres
6.1.2 Liens
- Orientés
- Réciproques
- Non-orientés
6.2 Structures locales
Ou comment un réseau s’organise.
- Noeuds isolés
- Dyades
- Réciprocité
- Triades (liens orientés)
- Empty
- One-edge
- Two-path
- Triangle
- Triades (liens non-orientés)
- Intransitive : liens bilatéraux uniquement
- Transitive : l’ami de mon ami est mon ami
- Trois-cycles : forme d’échange généralisé
- Clique : sous-ensemble de noeuds où toutes les paires de noeuds existants sont connectés.
- Modularité : mesure segmentation d’un réseau en modules. Réseau à modularité élevée a densité élevée entre les noeuds qui font partie d’un même module, densité faible entre noeuds appartenant à modules différents.
# Trois algorithmes de modularité
<- walktrap.community(graph)
wtc <- fastgreedy.community(graph) # fonctionne uniquement pour liens non-orientés
grd <- spinglass.community(graph) # fonctionne si tous les noeuds sont connectés (aucun noeud isolé)
spn
# Indicateur de modularité pour le réseau
modularity(graph, membership(wtc))
modularity(graph, membership(grd))
modularity(graph, membership(spn))
6.3 Connectivité
- Chaîne/walk : parcours sur graphe non orienté allant d’un noeud à un autre en empruntant des arêtes (liens)
- Chemin : chaîne mais pour un graphe orienté
- Chaîne/chemin élémentaire (path) si chaque noeud y apparaît au plus une fois.
- Géodésique (geodesic) : chaîne/chemin élémentaire la/le plus court(e) (shortest path) entre deux noeuds.
- Cycle : départ et arrivée de la chaîne/chemin élémentaire est le même noeud.
- Graphe connexe (connected) : chemin ou chaîne entre toute paire de noeuds.
- Composante : sous-graphe maximalement connecté.
- Distance (géodésique) : nb de pas (plus courts chemins) entre un noeud et l’autre.
- noeuds connectés ont distance 1
- noeuds dans composantes différentes ont distance infinie
- Diamètre : distance la plus longue entre deux noeuds.
- Average path length : distance moyenne entre toutes les pairs de noeuds dans un réseau (moins sensible à des outliers que le diamètre).
- Eccentricité : distance depuis un noeud de départ vers le noeud le plus loin dans le réseau.
- Rayon : eccentricité minimale des noeuds. La plus petite distance à laquelle puisse se trouver un noeud de tous les autres (infini si graphe est non connecté)
shortest.paths(graph, algorithm="unweighted")
# Shortest path entre deux noeuds
get.shortest.paths(graph,
V(graph)[name=="name1"],
V(graph)[name=="name2"],
mode="all", output="both")
# Distance moyenne entre les noeuds
average.path.length(graph)
# Diamètre
diameter(graph)
# Eccentricité
eccentricity(graph)
# Rayon : eccentricité la plus faible
radius(graph)
6.4 Mesures basiques de cohésion
Tous les noeuds sont-ils liés entre eux? Quels types de liens existent dans le réseau et dans quelle quantité?
- Transitivité : \(\frac{nombre.triades.transitives}{nombre.triades}\)
- égal à 1 si tous les noeuds sont liés à tous les autres noeuds (connectivité complète)
- Excède rarement 0.2 dans réseaux aléatoires.
- Souvent compris entre 0.3 et 0.6 dans les réseaux empiriques.
- Densité : \(\frac{nombre.liens.existants}{nb.liens.pouvant.existés}\)
- \(\frac{L}{(n*(n-1))}\) liens orientés
- \(\frac{L}{\frac{(n*(n-1))}{2}}\) liens non-orientés
- Coefficient de clustering : mesure de cohésion dans le voisinage d’un noeud (combien de mes amis sont amis entre eux). 2 mesures :
- Mesure locale : on mesure d’abord pour chaque noeud i, le \(Cl_{i}\) ensuite on prend la moyenne \(\sum_{i = 1}^{n}\)\(\frac{Cl_{i}}{n}\). Tends to 1.
- Mesure globale : \(\sum_{i=1}^{n}\)\(\frac{nombre.liens.existants.entre.amis.de.i}{nombre.liens.possibles.entre.amis.de.i}\). Tends to 0 => transitivité.
# Transitivité du réseau
transitivity(graph)
# Transitivité d'un noeud
transitivity(graph,type="local")
# Densité du réseau
graph.density(graph)
# Nombre d'îles, i.e. clusters
clusters(graph)
6.5 Mesures de diversité
Tous mes groupes sont-ils représentés proportionnellement dans mon réseau?
- Deux familles de mesures:
- proportion (ou pourcentage) d’une catégorie sur la totalité
- hétérogénéité (variance, écart-type, IQV…)
- Indice de diversité de Blau \(\in[0;\frac{k-1}{k}]\) Une seule catégorie représentée => toutes les catégories représentées équitablement (utile si plus de 2 catégories - variante de l’indice Herfindahl-Hirschmann (HHI))
- Indice de variation qualitative, IQV \(\in[0;1]\) Une seule catégorie représentée => toutes les catégories représentées équitablement (un indice POUR CHAQUE ATTRIBUT d’intérêt)
<- function(x, type) {
get.Blau.index <- factor(x, levels = type);
x return(1 - sum(prop.table(table(x))^2))}
# Indice de diversité de Blau
<- get.Blau.index(as.factor(V(graph)$variable))
qualif_blau # on applique la fonction de l'IB à la variable x
qualif_blau
# Indice de variation qualitative
= qualif_blau / (1 - (1 / length(levels(as.factor(Proportions$Var1)))))
qualif_iqv
qualif_iqv# IQV de Qualification!!!
# HHI qui est égal à 1 - qualif_blau
<- 1 - qualif_blau
qualif_hhi qualif_hhi
6.6 Mesures de centralité
Y a-t-il un noeud ou groupe de noeuds qui a une plus grande importance/qui est le plus relié dans le réseau?
Centralité de degré (degree)
- noeuds les plus “actifs” (les plus connectées, qui sont liés à un plus grand nombre de noeuds) \(C_D(i) =\) \(\sum_{j=1}^{n}x_{ij} = \sum_{j=1}^{n} x_{ji}\)
- mesure normalisée: \(C'_D(i)=\frac{\sum_{j=1}^{n}x_{ij}}{n-1}\)
- centralité de demi-degré pour graphe orienté. Indicateur de position sociale.
- Extérieur (outdegree) = nb liens sortants (e.g: demander beaucoup de conseils)
- Intérieur (indegree) = nb liens entrants (e.g: recevoir beaucoup de demandes de conseils)
- noeuds les plus “actifs” (les plus connectées, qui sont liés à un plus grand nombre de noeuds) \(C_D(i) =\) \(\sum_{j=1}^{n}x_{ij} = \sum_{j=1}^{n} x_{ji}\)
Centralité d’intermédiarité (betweenness)
- position stratégique, entre différentes parties du réseau (e.g être le lien entre deux parties non connectées)
- nb de plus courts chemins entre toute paire d’acteurs k et j, et on prend ceux qui passent par i
- \(C_B(i)=\)\(\sum_{jk}\)\(\frac{s_{kij}}{s_{kj}}\)
Centralité de proximité (closeness). Un peu comme centralité de degré, mais noeuds sont pas aussi centraux.
Centralité de vecteur propre (eigenvector). Être connecté aux autres noeuds les plus connectés.
Centralité dans un réseau : se calcule pour chaque noeud dans un réseau (devient un attribut du noeud) [NB: soit centra de proxi, soit centra de degré, soit intermédiarité, etc…]. Dans quelle mesure le réseau est dominé par un noeud central (ou peu de noeuds centraux) ? On compare la centralité du noeud le plus central à la centralité des autres noeuds. Au niveau du réseau dans son ensemble, on peut regarder:
- La distribution des centralités des noeuds;
- Des indicateurs de “centralisation” agrégés.
- mesure de centralisation de Freeman
# Centralité de degré
degree(graph,mode="all")
degree(graph,mode="in")
degree(graph,mode="out")
# Centralité d'intermédiarité
betweenness(graph,directed=TRUE)
# Centralité de proximité
# il faut d'abord enlever les noeuds isolés, sinon le calcul ne marche pas
= which(degree(graph)==0)
Isolated = delete.vertices(graph, Isolated) # on construit un nouveau graphe en enlevant Isolated
graph2
# on calcule la proximité sur ce graphe
<- closeness(graph2, mode='all', normalized = FALSE)
close_graph # pour obtenir la valeur normalisée, la commande est :
<- closeness(graph2, mode='all', normalized = TRUE)
close_graph2
# Centralité de vecteur propre
eigen_centrality(graph, scale = TRUE, weights = NULL)