Distribution des degrés

Le degré d'un sommet dans un réseau est égal au nombre de liens ou d'arêtes liant ce sommet à d'autres sommets. Si un réseau est orienté, ce qui signifie que des arcs pointent dans un sens, d'un sommet vers un autre, les sommets ont alors deux degrés différents: le degré intrant (in-degree), qui correspond au nombre d'arcs pointant vers lui, et le degré sortant (out-degree), qui décompte le nombre d'arcs partant dudit sommet.

La distribution de degrés P(k) d'un réseau est alors définie comme étant la fraction des sommets dans le réseau ayant un degré k. S'il y a n sommets au total dans un réseau et que n_k de ceux-ci ont un degré k, cela donne P(k) = n_k/n.

La même information est aussi parfois présentée sous la forme d'une distribution cumulative des degrés - la fraction des sommets ayant un degré plus petit que k - ou encore la distribution de degrés cumulative complémentaire - la fraction des sommets ayant un degré supérieur ou égal à k (1 - C si C est la distribution cumulative des degrés).

La distribution des degrés est très importante dans l'étude des réseaux réels comme Internet et les réseaux sociaux, ainsi que dans les réseaux théoriques. Le plus simple des modèles de réseaux, comme par exemple un graphe aléatoire dans lequel chacun des n sommets est relié (ou non) avec une probabilité indépendante p (ou 1 − p), a une distribution binominale de degré k:

${\displaystyle P(k)={n-1 \choose k}p^{k}(1-p)^{n-1-k},}$

(ou une distribution de Poisson dans les cas où n est vaste). La plupart des réseaux dans le monde réel présentent une distribution de degrés très différente de celle-ci. La plupart sont fortement asymétriques, ce qui signifie qu'une grande majorité des sommets ont un degré faible, tandis qu'un petit nombre, appelé "hubs", ont un degré élevé. Certains réseaux, notamment le world wide web, et quelques réseaux sociaux présentent une distribution de degré qui suit approximativement une loi de puissance: P(k) ~ k^−γ, où γ est une constante. Ce type de réseau est dit sans échelle et on leur porte une attention particulière pour leurs structures et leurs propriétés dynamiques[1] - [2] - [3] - [4].

• Théorie des graphes
• Théorie des réseaux
• Réseau invariant d'échelle
• Graphe aléatoire

• (Anglais) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Degree distribution » (voir la liste des auteurs).