Distribution des degrés

thumb|right|320px|Distribution de degrés intrant/sortant du réseau des liens hypertextes de Wikipedia (échelles logarithmiques) La distribution des degrés est, dans l'étude des graphes et des réseaux, une distribution probabiliste des degrés de chaque sommet du réseau. Le degré d'un sommet est le nombre de liens entre ce sommet et d'autres sommets du graphe. 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 nk de ceux-ci ont un degré k, cela donne P(k) = nk/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: (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é.