2.3 Distance et diamètre

Pour étudier le flu d’information ou le transport d’un objet sur un graphe, le voisinage direct d’un noeud n’est pas suffisant, mais on s’intéresse aux chemins qui lient ou pas deux noeuds quelconques dans un graphe. La longueur de ses chemins indique le coût ou la durée pour aller d’un noeud vers l’autre.

Definition 2.4 (Chemins et cycles) Un chemin dans \(G=(V,E)\) un graphe non orienté entre les sommets \(i\) et \(j \in V\) est une suite d’arêtes \(e_1,\dots,e_k\in E\) telle que

  • pour tout \(1\le t\le k-1\), les arêtes \(e_t\) et \(e_{t+1}\) partagent un noeud dans \(V\);
  • \(e_1\) est issue de \(i\);
  • \(e_t\) est issue de \(j\).

Un cycle dans \(G\) est un chemin d’un noeud \(i\) à lui même.

Dans un graphe orienté, on peut définir la notion de chemin orienté entre \(i\) et \(j\). Il se peut alors qu’il existe un chemin orienté de \(i\) vers \(j\) sans chemin orienté de \(j\) vers \(i\).

La longueur d’un chemin entre \(i\) et \(j\) est le nombre d’arêtes qui le composent.
En général, on ne s’intéresse qu’aux plus courts chemins.
Definition 2.5 (Distance et diamètre) Si deux noeuds \(i\) et \(j\) sont connectés dans \(G\), alors la distance \(\ell_{ij}\) entre \(i\) et \(j\) est la longueur du plus court chemin qui les relie dans le graphe. Si les deux noeuds ne sont pas connectés dans \(G\) alors \(\ell_{ij}=+\infty\). La distance moyenne des chemins est définie par \[ \bar \ell = \frac 1 {n(n-1)}\sum_{i=1}^n \sum_{j=1}^n \ell_{ij} = \frac 2 {n(n-1)}\sum_{i,j ; i<j} \ell_{ij} . \] Le diamètre d’un graphe \(G\) est la plus grande distance entre deux noeuds du graphe \[ \text{diam}(G)=\max \{\ell_{ij} ; i,j\in V\}. \] Cette quantité n’est finie que pour les graphes connexes.

Le diamètre décrit le pire des cas pour envoyer de l’information ou une autre ressource dans le réseau. Un petit diamètre indique que de l’information circule rapidement dans le graphe entier. Le réseau est alors compact ou efficace.

Exemple. Pour le réseau physique de l’internet, la distance moyenne entre deux routeurs est environ 9 (Yook, Jeong, and Barabasi (2001)).

Propriété petit monde (small-world property)

Un réseau a la propriété dit petit monde si la distances moyenne \(\bar\ell\) est proportionnelle à \(\log(|V|)\). Cette propriété traduit le fait que dans certains réseaux même très grands, la distance entre deux noeuds pris au hasard reste relativement petite. C’est le cas de beaucoup de réseaux sociaux.

En 1967, Stanley Milgram (1967) étudie le réseau de connaissances entre des personnes aux USA et conclu au phénomène des six degrees of separation (Milgram (1967)), i.e. \(\bar\ell\approx6\). Plus récemment, à l’ère de facebook, Bhagat et al. (2016) estiment que parmi les membres de facebook du monde entier on est passé à \(\bar\ell\approx3,5\) (three and a half degrees of separation).

Un autre réseau qui a la propriété de petit monde est le réseau des acteurs Holywoodiens reliés par leur co-apparition dans un film. La distance moyenne y est de \(\bar \ell=3\).

References

Bhagat, Smriti, Moira Burke, Carlos Diuk, Ismail Onur Filiz, and Sergey Edunov. 2016. “Three and a Half Degrees of Separation.” facebook research blog https://research.fb.com/three-and-a-half-degrees-of-separation/.

Milgram, Stanley. 1967. “The Small World Problem.” Psychology Today 1 (60): –.

Yook, Soon-Hyung, Hawoong Jeong, and Albert-Laszlo Barabasi. 2001. “Modeling the Internet’s Large-Scale Topology.”