Vérifier les ordres de grandeur

1. Le degré moyen d'un graphe non orienté vaut $\frac{1}{n}{\sum }_{s}d(s)=\frac{2m}{n}$, par le lemme des poignées de main. Avec $n=10^7$ et $m=2\cdot 10^7$ : $2m/n=4$. Le chiffre du chapitre est exact — et il est vrai du monde : un carrefour relie quatre routes en moyenne.

Le remplissage est la proportion de cases non nulles de la matrice : $m/n^2=2\cdot 10^7/10^{14}=2\cdot 10^{-7}$. Exact également. Autrement dit, sur dix millions de cases, deux portent un $1$.

2. Les quatre graphes. Mesuré :

Les quatre sont creux, et c'est le point du tableau. Un graphe est creux quand $m=O(n)$, c'est-à-dire quand le degré moyen est borné — et non quand $m$ est petit. Le réseau social a un degré moyen de $333$, ce qui est beaucoup, et il reste creux : $333\ll 3\cdot 10^9$. Son remplissage vaut $5,6\cdot 10^{-8}$.

On ne connaît pratiquement pas de grand graphe dense. La raison est physique : un sommet ne peut entretenir qu'un nombre borné de relations — un carrefour a quatre routes, un humain quelques centaines d'amis, une page quelques dizaines de liens. La densité exigerait que ce nombre croisse avec la taille du graphe, ce qu'aucun système réel ne fait.

3. La mémoire. Mesuré, avec $4$ octets par entier :

Un facteur $3\cdot 10^6$. La matrice n'est pas seulement lente : elle ne tient sur aucune machine, ni même sur une grappe de machines. Les listes, elles, tiennent dans la mémoire vive d'un ordinateur portable — et c'est ainsi qu'un calculateur d'itinéraires fonctionne.

Même en ne réservant qu'un bit par case, la matrice occuperait $12,5$ téraoctets. Le choix de représentation n'est pas une optimisation, c'est ce qui décide si le programme peut exister.