Distribution des degrés

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.

Distribution de degrés intrant/sortant du réseau des liens hypertextes de Wikipedia (échelles logarithmiques)

Définition

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).

Distribution de degrés observé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:

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].

Voir aussi

Références

(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).

Barabási, A.-L. and R. Albert, Science 286, 509 (1999).
R. Albert, and A.L. Barabási, Phys. Rev. Lett. 85, 5234(2000).
S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhim, cond-mat/0011115.
Angelica Pachon, Laura Sacerdote et Shuyi Yang, « Scale-free behavior of networks with the copresence of preferential and uniform attachment rules », Physica D: Nonlinear Phenomena,‎ 2018 (DOI 10.1016/j.physd.2018.01.005, Bibcode 2018PhyD..371....1P, arXiv 1704.08597)

Portail des mathématiques
Portail de l’informatique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[BA-1] Barabási, A.-L. and R. Albert, Science 286, 509 (1999).

[AB-2] R. Albert, and A.L. Barabási, Phys. Rev. Lett. 85, 5234(2000).

[Doro-3] S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhim, cond-mat/0011115.

[PSY-4] Angelica Pachon, Laura Sacerdote et Shuyi Yang, « Scale-free behavior of networks with the copresence of preferential and uniform attachment rules », Physica D: Nonlinear Phenomena,‎ 2018 (DOI 10.1016/j.physd.2018.01.005, Bibcode 2018PhyD..371....1P, arXiv 1704.08597)