Analyse des réseaux
Chapitre 4 : Topologie d’un réseau
[Link]@[Link]
04 octobre 2023
Licence 3 Economie-Gestion, Université Côte d’Azur
Table of contents
1. Introduction
2. Introduction
3. Network-wide indexes
4. Réseau invariant d’échelle
5. Coeur-Périphérie
6. Conclusion
1
Introduction
Introduction
• Jusqu’à présent
• Etude des noeuds (chapitre 2)
• Etude des liens et chemins (chapitre 3)
2
Introduction
• Jusqu’à présent
• Etude des noeuds (chapitre 2)
• Etude des liens et chemins (chapitre 3)
• Mais l’étude, la description des réseaux va au delà des caractéristiques
individuelles de ses membres
2
Introduction
• Jusqu’à présent
• Etude des noeuds (chapitre 2)
• Etude des liens et chemins (chapitre 3)
• Mais l’étude, la description des réseaux va au delà des caractéristiques
individuelles de ses membres
• Caractériser le réseau dans son ensemble.
2
Introduction
• Jusqu’à présent
• Etude des noeuds (chapitre 2)
• Etude des liens et chemins (chapitre 3)
• Mais l’étude, la description des réseaux va au delà des caractéristiques
individuelles de ses membres
• Caractériser le réseau dans son ensemble.
• Déjà initié avec la notion de diamètre du réseau (cf. chapitre 3)
• Caractériser la structure d’ensemble : “phénomène d’emergence” dans les
systèmes complexes.
2
Introduction
• Jusqu’à présent
• Etude des noeuds (chapitre 2)
• Etude des liens et chemins (chapitre 3)
• Mais l’étude, la description des réseaux va au delà des caractéristiques
individuelles de ses membres
• Caractériser le réseau dans son ensemble.
• Déjà initié avec la notion de diamètre du réseau (cf. chapitre 3)
• Caractériser la structure d’ensemble : “phénomène d’emergence” dans les
systèmes complexes.
• On parle de Topologie du réseau
2
Introduction
Topologie
• Étymologie : “étude du lieu”
3
Introduction
Topologie
• Étymologie : “étude du lieu”
• En mathématiques : étude des propriétés qui sont conservées lors de
déformation d’un objet géographique
3
Introduction
Topologie
• Étymologie : “étude du lieu”
• En mathématiques : étude des propriétés qui sont conservées lors de
déformation d’un objet géographique
• Étude des caractéristiques permanentes d’un système
3
Introduction
Topologie
• Étymologie : “étude du lieu”
• En mathématiques : étude des propriétés qui sont conservées lors de
déformation d’un objet géographique
• Étude des caractéristiques permanentes d’un système
• En analyse des réseaux : étude de la structure du réseau, indépendamment
des noeuds qui le composent (du moins à la marge).
3
Introduction
Topologie
• Étymologie : “étude du lieu”
• En mathématiques : étude des propriétés qui sont conservées lors de
déformation d’un objet géographique
• Étude des caractéristiques permanentes d’un système
• En analyse des réseaux : étude de la structure du réseau, indépendamment
des noeuds qui le composent (du moins à la marge).
• Par extension : topologie d’un réseau = son architecture
3
Introduction
Fractales et structure de réseau
• Si on s’intéresse aux propriétés permanentes de l’architecture d’un réseau,
c’est que souvent les réseaux ont un aspect “fractal”
• (cf. section “avant le cours sur moodle)
4
Fractales et structure de réseau
• Si on s’intéresse aux propriétés permanentes de l’architecture d’un réseau,
c’est que souvent les réseaux ont un aspect “fractal”
• (cf. section “avant le cours sur moodle)
• Propriétés similaires à toutes les échelles
4
Fractales et structure de réseau
• Si on s’intéresse aux propriétés permanentes de l’architecture d’un réseau,
c’est que souvent les réseaux ont un aspect “fractal”
• (cf. section “avant le cours sur moodle)
• Propriétés similaires à toutes les échelles
• Réseaux invariants d’échelle (“scale-free networks”)
4
Fractales et structure de réseau
• Si on s’intéresse aux propriétés permanentes de l’architecture d’un réseau,
c’est que souvent les réseaux ont un aspect “fractal”
• (cf. section “avant le cours sur moodle)
• Propriétés similaires à toutes les échelles
• Réseaux invariants d’échelle (“scale-free networks”)
• Consensus sur le fait que les réseaux du monde réel suivent cette propriété
• Débat portant sur le fait qu’ils soient “fortement” ou plus souvent
“faiblement” scale-free (Broido et al., 2019, Nature communications)
4
Introduction
Plan du cours
1. Comment appréhender et mesurer la structure d’un réseau
2. Qu’est-ce qu’un scale-free network?
3. Implications sur les réseaux réels et leur centralisation
• Small world network (six degrés de séparation)
• Coeur-périphérie et centralisation.
5
Network-wide indexes
Caractériser la structure du réseau
Rappels:
• Indices au niveau des noeuds
• degré, strength
• Indice au niveau des liens et chemins
• Poids (relatif), longueur, distance
• Indices au niveau du réseau dans son ensemble.
• diamètre, coefficient d’assortativité
6
Caractériser la structure du réseau
La densité
• La densité d’un réseau nous renseigne sur le proportion de liens existants.
• Le degré de connectivité du réseau
7
Caractériser la structure du réseau
La densité
• La densité d’un réseau nous renseigne sur le proportion de liens existants.
• Le degré de connectivité du réseau
• Va influencer la vitesse de diffusion/propagation dans le réseau
7
Caractériser la structure du réseau
La densité
• La densité d’un réseau nous renseigne sur le proportion de liens existants.
• Le degré de connectivité du réseau
• Va influencer la vitesse de diffusion/propagation dans le réseau
7
Caractériser la structure du réseau
La densité
• La densité d’un réseau nous renseigne sur le proportion de liens existants.
• Le degré de connectivité du réseau
• Va influencer la vitesse de diffusion/propagation dans le réseau
L
• densité : D = N(N−1)/2
• Nombre de liens existants / nombre de liens possibles
7
Caractériser la structure du réseau
La densité
• La densité d’un réseau nous renseigne sur le proportion de liens existants.
• Le degré de connectivité du réseau
• Va influencer la vitesse de diffusion/propagation dans le réseau
L
• densité : D = N(N−1)/2
• Nombre de liens existants / nombre de liens possibles
• Valeurs limites : 0 ≤ D ≤ 1 (si D = 1 on parle de graphe complet)
7
Densité
Soit le réseau suivant :
8
Densité
Soit le réseau suivant :
0 1 0 0 0 0 0 0
1 0 1 0 0 0 0 0
0 1 0 1 1 0 0 0
0 0 1 0 1 0 0 0
0 0 1 1 0 1 1 0
0 0 0 0 1 0 1 0
0 0 0 0 1 1 0 1
0 0 0 0 0 0 1 0
8
Densité
Soit le réseau suivant :
0 1 0 0 0 0 0 0
1 0 1 0 0 0 0 0
0 1 0 1 1 0 0 0
0 0 1 0 1 0 0 0
0 0 1 1 0 1 1 0
0 0 0 0 1 0 1 0
0 0 0 0 1 1 0 1
0 0 0 0 0 0 1 0
P P P
• Nombre de liens existants : L = i j aij /2 = i ki /2 = 18/2 = 9
8
Densité
Soit le réseau suivant :
0 1 0 0 0 0 0 0
1 0 1 0 0 0 0 0
0 1 0 1 1 0 0 0
0 0 1 0 1 0 0 0
0 0 1 1 0 1 1 0
0 0 0 0 1 0 1 0
0 0 0 0 1 1 0 1
0 0 0 0 0 0 1 0
P P P
• Nombre de liens existants : L = i j aij /2 = i ki /2 = 18/2 = 9
• Densité : D = L/N(N − 1)/2 = 9/(8 ∗ 7/2) = 9/28 = 0.32 8
Caractériser la structure du réseau
La centralisation
• La centralisation nous renseigne sur l’inégale distribution de la centralité
des noeuds.
• Plus un noeud est central par rapport aux autres : plus le réseau est
centralisé.
9
Caractériser la structure du réseau
La centralisation
• La centralisation nous renseigne sur l’inégale distribution de la centralité
des noeuds.
• Plus un noeud est central par rapport aux autres : plus le réseau est
centralisé.
• Lien avec la densité ?
9
Caractériser la structure du réseau
La centralisation
• La centralisation nous renseigne sur l’inégale distribution de la centralité
des noeuds.
• Plus un noeud est central par rapport aux autres : plus le réseau est
centralisé.
• Lien avec la densité ?
• La relation n’est pas systématique (pour une même densité, plusieurs valeur
de centralisation sont possible, et inversement). Mais logiquement, la
centralisation décroit avec la densité (si graphe complet, alors pas de noeud
plus central, hors pondération).
9
Caractériser la structure du réseau
La centralisation
• La centralisation nous renseigne sur l’inégale distribution de la centralité
des noeuds.
• Plus un noeud est central par rapport aux autres : plus le réseau est
centralisé.
• Lien avec la densité ?
• La relation n’est pas systématique (pour une même densité, plusieurs valeur
de centralisation sont possible, et inversement). Mais logiquement, la
centralisation décroit avec la densité (si graphe complet, alors pas de noeud
plus central, hors pondération).
9
Centralisation
• Mesurer la centralisation?
• Freeman (1979) centralization index
• =1 si “étoile”, 0 si graph complet
10
Centralisation
• Mesurer la centralisation?
• Freeman (1979) centralization index
• =1 si “étoile”, 0 si graph complet
• Intuition : Comparaison entre les différences de centralités dans le graphe
avec les différences des centralité maximales pour un graphe de même
taille.
10
Centralisation
• Mesurer la centralisation?
• Freeman (1979) centralization index
• =1 si “étoile”, 0 si graph complet
• Intuition : Comparaison entre les différences de centralités dans le graphe
avec les différences des centralité maximales pour un graphe de même
taille. P N
i=1 Cx (p∗ )−Cx (pi )
• Mathématiquement: Cx = P N C (p )−C (p )
Max i=1 x ∗ x i
10
Centralisation
• Mesurer la centralisation?
• Freeman (1979) centralization index
• =1 si “étoile”, 0 si graph complet
• Intuition : Comparaison entre les différences de centralités dans le graphe
avec les différences des centralité maximales pour un graphe de même
taille. P N
i=1 Cx (p∗ )−Cx (pi )
• Mathématiquement: Cx = P N C (p )−C (p )
Max i=1 x ∗ x i
• Attention Ne pas confondre centralité et centralisation
10
Centralisation
• Mesurer la centralisation?
• Freeman (1979) centralization index
• =1 si “étoile”, 0 si graph complet
• Intuition : Comparaison entre les différences de centralités dans le graphe
avec les différences des centralité maximales pour un graphe de même
taille. P N
i=1 Cx (p∗ )−Cx (pi )
• Mathématiquement: Cx = P N C (p )−C (p )
Max i=1 x ∗ x i
• Attention Ne pas confondre centralité et centralisation
• Centralité : au niveau d’un noeud
• Centralisation : au niveau du réseau/graphe dans son ensemble.
10
Graphes dirigés
• Dans un graphe dirigé :
• : Une seule densité : Nombre de Liens existants / liens possibles (entrants
et sortant)
P P P P
• Liens existant : i j aij = koutward = kinward
• Liens possibles : N(N − 1)
• centralisation entrante/sortante (ou moyenne)
11
Graphes pondérés
• Dans un graphe pondéré
12
Graphes pondérés
• Dans un graphe pondéré
• Densité ne change pas : nombre de liens, pas leur poids
12
Graphes pondérés
• Dans un graphe pondéré
• Densité ne change pas : nombre de liens, pas leur poids
• Centralisation : L’indice de Freeman s’adapte à toute mesure de centralité :
donc Strength (pondéré) également.
12
Application
Réseau aléatoire
• Calculer densité
• Calculer centralisation
13
Centralisation et distribution des degrés
Dans un graphe simple (non dirigé, non pondéré) la centralisation reflète la
distribution des degrés.
• Si distribution uniforme (tous les noeuds ont le même degré)
14
Centralisation et distribution des degrés
Dans un graphe simple (non dirigé, non pondéré) la centralisation reflète la
distribution des degrés.
• Si distribution uniforme (tous les noeuds ont le même degré)
• Centralisation = 0
• Plus la centralisation est élevée : plus la distribution est right-skewed
14
Centralisation et distribution des degrés
15
Réseau invariant d’échelle
Scale-free networks
• Les réseaux invariants d’échelle (scale-free networks sont une classe de
réseau dont la structure est insensible à l’échelle
• invariance d’échelle (cf fractales)
• La densité et la centralisation y sont similaires.
• la distance moyenne entre deux nœuds est proportionnelle au logarithme du
nombre de nœuds,
16
Scale-free networks
• Les réseaux invariants d’échelle (scale-free networks sont une classe de
réseau dont la structure est insensible à l’échelle
• invariance d’échelle (cf fractales)
• La densité et la centralisation y sont similaires.
• la distance moyenne entre deux nœuds est proportionnelle au logarithme du
nombre de nœuds,
• Quelle caractéristique doivent-ils avoir pour vérifier ces propriétés?
16
Scale-free networks
• Les réseaux invariants d’échelle (scale-free networks sont une classe de
réseau dont la structure est insensible à l’échelle
• invariance d’échelle (cf fractales)
• La densité et la centralisation y sont similaires.
• la distance moyenne entre deux nœuds est proportionnelle au logarithme du
nombre de nœuds,
• Quelle caractéristique doivent-ils avoir pour vérifier ces propriétés?
• La distribution des degrés suit une Loi de puissance
• La probabilité d’avoir un noeud de degré k suit la loi : P(k) ∼ k −γ
16
Scale-free networks
• Les réseaux invariants d’échelle (scale-free networks sont une classe de
réseau dont la structure est insensible à l’échelle
• invariance d’échelle (cf fractales)
• La densité et la centralisation y sont similaires.
• la distance moyenne entre deux nœuds est proportionnelle au logarithme du
nombre de nœuds,
• Quelle caractéristique doivent-ils avoir pour vérifier ces propriétés?
• La distribution des degrés suit une Loi de puissance
• La probabilité d’avoir un noeud de degré k suit la loi : P(k) ∼ k −γ
• Watts et Strogatz (1998, Nature) : les réseaux réels sont souvent “petit
monde”
• Barabasi & Albert (1999, Science) : Expliquent pourquoi
16
Scale-free networks
• Les réseaux invariants d’échelle (scale-free networks sont une classe de
réseau dont la structure est insensible à l’échelle
• invariance d’échelle (cf fractales)
• La densité et la centralisation y sont similaires.
• la distance moyenne entre deux nœuds est proportionnelle au logarithme du
nombre de nœuds,
• Quelle caractéristique doivent-ils avoir pour vérifier ces propriétés?
• La distribution des degrés suit une Loi de puissance
• La probabilité d’avoir un noeud de degré k suit la loi : P(k) ∼ k −γ
• Watts et Strogatz (1998, Nature) : les réseaux réels sont souvent “petit
monde”
• Barabasi & Albert (1999, Science) : Expliquent pourquoi
1. Extension par rajout de nouveaux noeuds (et pas seulement liens)
2. attachement préférentiel (et non aléatoire) : les nouveaux noeuds se
connectent davantage aux plus centraux.
16
Small world network
Le réseau “petit monde” est un exemple de réseau invariant d’échelle
• Origine : 6 degrés de séparation (Milgram) (cf vidéo moodle)
• Watts & Strogatz (1998) : plusieurs réseaux (sociaux, mais aussi
neuronaux, électriques, etc) affichent ces propriétés de “petit monde”
• En particulier : faible diamètre, faible distance moyenne.
• Le diamètre est proportionel au log(N) (d ∼ ln(N) )
• Par rapport à un réseau aléatoire ou régulier, retrouver ce schéma ne
nécessite que très peu de déviations.
• Granovetter : “The strength of weak ties” : quelques liens permettent de
connecter des “grappes” éloignées, réduisant le chemin nécessaire pour les relier.
17
Small world network
Le réseau “petit monde” est un exemple de réseau invariant d’échelle
• Origine : 6 degrés de séparation (Milgram) (cf vidéo moodle)
• Watts & Strogatz (1998) : plusieurs réseaux (sociaux, mais aussi
neuronaux, électriques, etc) affichent ces propriétés de “petit monde”
• En particulier : faible diamètre, faible distance moyenne.
• Le diamètre est proportionel au log(N) (d ∼ ln(N) )
• Par rapport à un réseau aléatoire ou régulier, retrouver ce schéma ne
nécessite que très peu de déviations.
• Granovetter : “The strength of weak ties” : quelques liens permettent de
connecter des “grappes” éloignées, réduisant le chemin nécessaire pour les relier.
• Les propriétés de “petit monde” se retrouvent pour les réseaux invariants
d’echelle (lire ici (en anglais) )
17
Coeur-Périphérie
Core - Pheriphery
• Les réseaux petits monde et plus largement les réseaux invariants d’échelle
se traduisent par des structures dites “coeur-périphérie”
• Peu de noeuds sont très centraux (coeur, hubs), mais car très connectés, ils
permettent de relier facilement les périphéries (éloignées les unes des
autres).
• L’attachement préférentiel des nouveaux noeuds au coeur permet
d’expliquer cette invariance d’échelle
18
Core - Pheriphery
• Les réseaux petits monde et plus largement les réseaux invariants d’échelle
se traduisent par des structures dites “coeur-périphérie”
• Peu de noeuds sont très centraux (coeur, hubs), mais car très connectés, ils
permettent de relier facilement les périphéries (éloignées les unes des
autres).
• L’attachement préférentiel des nouveaux noeuds au coeur permet
d’expliquer cette invariance d’échelle
• Exemple: Trading partners (countries)
18
Core - Pheriphery
• Les réseaux petits monde et plus largement les réseaux invariants d’échelle
se traduisent par des structures dites “coeur-périphérie”
• Peu de noeuds sont très centraux (coeur, hubs), mais car très connectés, ils
permettent de relier facilement les périphéries (éloignées les unes des
autres).
• L’attachement préférentiel des nouveaux noeuds au coeur permet
d’expliquer cette invariance d’échelle
• Exemple: Trading partners (countries)
• Plus globalement, l’économie mondiale répond souvent à une structure
coeur-périphérie (cf Braudel, Walerstein, CEPAL).
18
Assortativité et coeur-périphérie
• Un réseau à la structure coeur-périphérie
• Se repère par une distribution très inégale de la connectivité des noeuds.
19
Assortativité et coeur-périphérie
• Un réseau à la structure coeur-périphérie
• Se repère par une distribution très inégale de la connectivité des noeuds.
• Ainsi que par une assortativité négative
19
Assortativité et coeur-périphérie
• Un réseau à la structure coeur-périphérie
• Se repère par une distribution très inégale de la connectivité des noeuds.
• Ainsi que par une assortativité négative
• : Corrélation négative entre le degré d’un noeud et celui de ses voisins:
• Les noeuds principaux ont principalement des voisins périphériques (peu
connectés) et les peu connectés sont surtout connectés aux hubs.
19
réseaux multi-coeur
• Il se peut que les réseaux soient constitués de plusieurs structure
coeur-périphérie
• exmple : réseau des professions françaises
20
réseaux multi-coeur
• Il se peut que les réseaux soient constitués de plusieurs structure
coeur-périphérie
• exmple : réseau des professions françaises
• Détection des communautés : au prochain cours
20
Conclusion
Conclusion
• Un réseau a des propriétés qui dépassent les caractéristiques des noeuds ou
des liens pris inviduellement
• Caractériser la structure d’ensemble.
21
Conclusion
• Un réseau a des propriétés qui dépassent les caractéristiques des noeuds ou
des liens pris inviduellement
• Caractériser la structure d’ensemble.
• Parmi eux, la densité et la centralisation sont deux éléments essentiels
21
Conclusion
• Un réseau a des propriétés qui dépassent les caractéristiques des noeuds ou
des liens pris inviduellement
• Caractériser la structure d’ensemble.
• Parmi eux, la densité et la centralisation sont deux éléments essentiels
• Les réseaux de type small world ou plus largement invariants d’echelle se
retrouvent dans de nombreux cas de réseaux réels.
21
Conclusion
• Un réseau a des propriétés qui dépassent les caractéristiques des noeuds ou
des liens pris inviduellement
• Caractériser la structure d’ensemble.
• Parmi eux, la densité et la centralisation sont deux éléments essentiels
• Les réseaux de type small world ou plus largement invariants d’echelle se
retrouvent dans de nombreux cas de réseaux réels.
• Identifier de telles structures permet de mieux comprendre comment
circule l’information/les biens dans le réseau et de mieux cibler les
interventions potentielles.
21
Conclusion
• Un réseau a des propriétés qui dépassent les caractéristiques des noeuds ou
des liens pris inviduellement
• Caractériser la structure d’ensemble.
• Parmi eux, la densité et la centralisation sont deux éléments essentiels
• Les réseaux de type small world ou plus largement invariants d’echelle se
retrouvent dans de nombreux cas de réseaux réels.
• Identifier de telles structures permet de mieux comprendre comment
circule l’information/les biens dans le réseau et de mieux cibler les
interventions potentielles.
• Ces types de structure ne surgissent pas aléatoirement : on peut alors
retracer un processus de fonctionnement du réseau.
• Coeurs : noeuds les plus anciens, accroissement par attachement préférentiel
21
References i
References
Freeman, L. C. Centrality in social networks conceptual clarification. Social networks, 1(3):
215–239, 1979.
Barabási, A. L., Albert, R. (1999). Emergence of scaling in random networks. science, 286(5439),
509-512.
Broido, A.D., Clauset, A. Scale-free networks are rare. Nat Commun 10, 1017 (2019).
Duncan J. Watts et Steven H. Strogatz, Collective dynamics of ‘small-world’ networks , Nature,
vol. 393, no 6684, juin 1998, p. 440–442
22