Coefficient de clustering

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Exemples de coefficient de clustering

En théorie des graphes et en analyse des réseaux sociaux, le coefficient de clustering d'un graphe (aussi appelé coefficient d'agglomération, de connexion, de regroupement, d'agrégation ou de transitivité), est une mesure du regroupement des nœuds dans un réseau. Plus précisément ce coefficient mesure à quel point le voisinage d'un sommet est connecté.

C'est l'un des paramètres étudiés dans les réseaux « petit monde » (small world network) en particulier les réseaux sociaux.

Définitions[modifier | modifier le code]

Il existe deux définitions légèrement différentes du coefficient de clustering : une version globale (aussi appelée transitive) et une version locale en moyenne[1].

Coefficient global[modifier | modifier le code]

Le coefficient de clustering global est défini comme

où un triangle est un sous-graphe complet à trois nœuds, et un triplet connecté est un sous-graphe connexe à trois nœuds.

Coefficient local moyen[modifier | modifier le code]

Pour un nœud i, on peut définir le coefficient local comme :

est le voisinage du sommet i, de cardinal . Cette mesure peut être vue comme la probabilité que deux sommets pris au hasard indépendamment et uniformément soient reliés entre eux. Plus le coefficient est grand, plus le voisinage est proche d'une clique, on parle parfois de «cliquicité» (cliqueness).

En prenant la moyenne de ces coefficients locaux, on obtient le coefficient local moyen :

.

Propriétés et variantes[modifier | modifier le code]

Relation entre les deux versions et influence des petits degrés[modifier | modifier le code]

Ces deux coefficients ne sont pas égaux en général (le fait de prendre la moyenne et de faire le ratio ne commutent pas). Ils le sont si la moyenne de la version locale est repondérée en fonction du degré. Dans la version locale les nœuds de petits degrés ont plus d'influence que ceux de grands degrés[1].

Variantes[modifier | modifier le code]

Il existe des versions du coefficient adaptées à certain type de graphes, comme ceux ayant des arêtes pondérées[2] ou les graphes bipartis[3].

Analyse des réseaux[modifier | modifier le code]

Les réseaux petit monde sont parfois décrit comme ceux ayant un coefficient de clustering élevé (en plus d'une longueur moyenne de cheminement faible)[4],[5]. Par ailleurs, dans les réseaux invariants d'échelle, le coefficient diminue quand le degré augmente.

Historique[modifier | modifier le code]

Le coefficient global est souvent attribué[6] à Barrat et Weigt pour l'article On the properties of small-world network models publié en 2000[4]. Le coefficient moyen local est attribué à Watts et Strogatz, pour l'article Collective dynamics of ‘small-world’networks de 1998[5].

Voir aussi[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. a et b Mark E.J. Newman, « The structure and function of complex networks », SIAM review, SIAM, vol. 45, no 2,‎ , p. 167-256
  2. A. Barrat, M. Barthelemy, R. Pastor-Satorras et A. Vespignani, « The architecture of complex weighted networks », Proceedings of the National Academy of Sciences, vol. 101, no 11,‎ , p. 3747-3752 (PMID 15007165, PMCID 374315, DOI 10.1073/pnas.0400087101, arXiv cond-mat/0311416)
  3. M. Latapy, C. Magnien et N. Del Vecchio, « Basic Notions for the Analysis of Large Two-mode Networks », Social Networks, vol. 30, no 1,‎ , p. 31-48 (DOI 10.1016/j.socnet.2007.04.006)
  4. a et b Alain Barrat et Martin Weigt, « On the properties of small-world network models », The European Physical Journal B-Condensed Matter and Complex Systems, Springer, vol. 13, no 3,‎ , p. 547-560
  5. a et b Duncan J. Watts et Steven H Strogatz, « Collective dynamics of ‘small-world’networks », Nature, Nature Publishing Group, vol. 393, no 6684,‎ , p. 440-442}
  6. Par exemple dans (Newman 2003) et (Porter 2014)

Bibliographie[modifier | modifier le code]

  • (en) Mark E.J. Newman, « The structure and function of complex networks », SIAM review, SIAM, vol. 45, no 2,‎ , p. 167-256

Liens externes[modifier | modifier le code]