The mixing time of Newman-Watts small world

"Small worlds" are large networks in which any given node has only a few connections to other nodes, but possessing the property that all pairs of nodes are connected by a short path, typically logarithmic in the number of nodes. Small-world models are widely used in the physics literature for modeling various "real-world" networks, such as World Wide Web, power grid and neural network. When the network is too big to model completely, which is often the case for "real-world" network, we need other approaches which yield information about its typical or approximate structure. One such approach is to use random walks for sampling a uniform element from a large state space; to prove that such a technique works for a given network, a bound on the mixing time is required. However, little detailed information is known about the behavior of random walks on small-world models, though many predictions can be found in the physics literature. We survey the range of small-world models, existing information about them, introduce Markov chains, mixing times and a variety of techniques for bounding mixing times. Finally, the principal contribution of this thesis is to show that for a famous small-world random graph model known as the Newman--Watts small world, the mixing time is of order $\log^2 n$. This confirms a prediction of Richard Durrett, whoproved a lower bound of order $\log^2 n$ and an upper bound of order $\log^3 n$."De petits mondes" sont de larges réseaux au sein desquels chaque noeud donné n'a qu'un nombre limité de connexions à d'autres noeuds, mais ayant la propriété selon laquelle chaque paire de noeuds est connectée par un court parcours, typiquement de longueur logarithmique par rapport au nombre de noeuds du réseau. Les modèles de "petits mondes" sont couramment utilisés dans la littérature de physique pour modéliser divers réseaux de "mondes réels" tels que le réseau internet, le réseau électrique ainsi que les réseaux neuronaux. Lorsque le réseau est trop complexe pour être modélisé complètement, ce qui est souvent le cas des réseaux de "mondes réels", il nous faut d'autres approches qui nous renseignent sur sa structure typique ou approximative. Une telle approche consiste à utiliser la marche aléatoire pour échantillonner un élément uniforme d'un espace plus vaste. Afin de démontrer qu'une telle méthode convient pour un réseau donné, un seuil sur le temps de mélange est nécessaire. Toutefois, peu de détails sont connus quant ou comportement des marches aléatoires dans les modèles des "petits mondes" alors que de nombreuses prévisions peuvent être trouvées dans la littérature de physique. Nous citons une multitude de modèles de "petits mondes", les informations disponibles à leur égard, introduisons les chaines de Markov, temps de mélange et une variété de techniques pour les bornes des temps de mélange. Enfin, la principale contribution de cette thèse est de montrer qu'un modèle connu de graphe de "petit monde", connu sous le nom de Newman-Watts, le temps de mélange est de l'ordre de $\log^2 n$. Ceci confirme une prévision de Richard Durrett, qui a prouvé une borne inférieure de l'ordre de $\log^2 n$ et une borne supérieure de l'ordre de $\log^3 n$