Dans de nombreux phénomènes régis par le hasard, le résultat de l'observation provient de la combinaison aléatoire d'événements élémentaires : le gain d'un joueur au jeu de pile ou face est le résultat de parties successives, mélanger un jeu de cartes s'effectue en plusieurs battages consécutifs, l'enchevêtrement d'une molécule d'ADN dans une cellule est le produit, entre autres, de croisements successifs. Ces événements élémentaires ont la particularité d'être réversibles (gagner/perdre au pile ou face, croiser/décroiser des brins d'ADN) et l'aléa régissant leur combinaison possède une certaine indépendance (l'issue d'une partie de pile ou face n'a a priori aucune influence sur la suivante). Un modèle possible pour ces phénomènes consiste à considérer un groupe G, fini ou dénombrable, que l'on munit d'une mesure de probabilité μ. On effectue des tirages successifs d'éléments dans G avec les hypothèses suivantes : les tirages sont indépendants, et, pour chaque tirage, μ(g) est la probabilité de tirer l'élément g. Si g1, g2,...,gn est le résul- tat de n tirages, on forme le produit g1.g2. ... . gn. C'est, par définition, la position à l'instant n de la marche aléatoire sur G de loi μ, et la question est : que peut-on dire du comportement asymptotique de g1.g2. ... .gn lorsque n augmente in- définiment ? La marche aléatoire s'en va-t'elle à l'infini ? Si oui, dans quelle direction ? Et à quelle vitesse ? Mes travaux depuis 2003 sont consacrés, pour l'essentiel, à l'étude du comportement asymptotique des marches aléatoires dans trois familles de groupes infinis, non abéliens et de type fini : les produits libres de groupes finis, les groupes d'Artin diédraux, ainsi que certaines extensions des groupes libres. Ils sont le fruit de collaborations avec Jean Mairesse (CNRS, Paris VI) et François Gautero (Université de Nice). Dans le cas des produits libres de groupes finis, nous décrivons précisément la mesure harmonique pour les marches aléatoires au plus proche voisin dans ces groupes, ce qui permet de calculer la vitesse et l'entropie asymptotique. En particulier, ces quantités dépendent de façon analytique des coefficients de μ. Considérant l'inégalité fondamentale de Yves Guivarc'h entre vitesse, entropie et croissance, nous montrons que les générateurs canoniques des produits libres de groupes finis sont extrémaux au sens de Vershik. Les groupes d'Artin diédraux forment une classe de groupes d'Artin qui généralise le groupe de tresses à trois brins B3 et pour laquelle nous donnons une description précise des géodésiques. La connaissance de la vitesse de fuite des marches aléatoires au plus proche voisin dans le groupe B3 est un premier outil de mesure de la complexité asymptotique d'une tresse aléatoire. Dans ce cas, on montre que la vitesse dépend de façon lipschitzienne mais non différentiable de μ, faisant apparaître certaines transitions de phase. Enfin, en ce qui concerne les extensions du groupe libre, nous montrons que, dans certains cas (comprenant notamment les extensions cycliques) les fonctions μ-harmoniques bornées sont entièrement décrites via le bord du groupe libre sous-jacent. La preuve repose sur l'existence d'actions non triviales de ces groupes sur des arbres réels, couplée à des critères généraux sur les compactifications des groupes développés par Vadim Kaimanovich.

Cette thèse est consacrée à la modélisation de la formation spontanée de chemins préférentiels par des marcheurs déposant des traces attractives sur leurs trajectoires. Plus précisément, par une démarche pluridisciplinaire couplant modélisation et expérimentation, elle vise à dégager un ensemble de règles minimales individuelles permettant l'apparition d'un tel phénomène. Dans ce but, nous avons étudié sous différents angles les modèles minimaux que sont les marches aléatoires renforcées (MAR).Ce travail comporte deux parties principales. La première démontre de nouveaux résultats dans le domaine des probabilités et statistiques. Nous avons généralisé le travail publié par M. Benaïm et O. Raimond en 2010 afin d'étudier l'asymptotique d'une classe de MAR auxquelles les demi-tours sont interdits. Nous avons également développé une procédure statistique permettant, sous certaines conditions adéquates de régularité, d'estimer les paramètres de MAR paramétrées et d'évaluer des marges d'erreur.Dans la seconde partie, sont décrits les résultats et analyses d'une étude comportementale et expérimentale de la fourmi Linepithema humile. Une partie de notre réflexion est centrée sur le rôle et la valeur des paramètres du modèle proposé par J.-L. Deneubourg et al. en 1990. Nous nous sommes aussi demandés dans quelle mesure une MAR peut reproduire les déplacements d'une fourmi dans un réseau. Dans ces objectifs, nous avons mené des expériences confrontant des fourmis à des réseaux à une ou plusieurs bifurcations. Nous avons appliqué aux données expérimentales les outils statistiques développés dans cette thèse. Nous avons aussi effectué une étude comparative entre les simulations de plusieurs modèles et les expériences. / This thesis is devoted to the modelisation of the spontaneous formation of preferential paths by walkers that deposit attractive trails on their trajectories. More precisely, through a multidisciplinary approach, which combines modelisation and experimentation, this thesis aims to bring out a set of minimal individual rules that allow the apparition of this phenomena. In this purpose, we study in several ways the minimal models, which are the Reinforced Random Walks (RRW).This work contains two main parts. The first one proves some new results in the field of probability and statistics. We have generalized the work published by M. Benaïm and O. Raimond in 2010 in order to study the asymptotics of a class of RRW, to which U-turns are forbidden. We developped also a statistical procedure that allows under some appropriate regularity hypotheses to estimate the parameters of parametized RRW and to evaluate margins of error.In the second part, we describe the results and the analyses of a experimental and behavioral study of the Linepithema humile ants. One part of our reflection is centered on the role and the value of the parameters of the model defined by J.-L. Deneubourg et al. in 1990. We investigated also the extent to which RRW could reproduce the moving of an ant in a network. To these purposes, we performed experiments that confront ants to a network of one or several forks. We applied to experimental data the statistical tools developed in this thesis and we performed a comparative study between experiments and simulations of several models.

La nécessité de protéger les véhicules de rentrée atmosphérique a conduit à la sélection des matériaux carbonés pour les applications les plus extrêmes [1, 2]. Au vu du coût prohibitif des essais en conditions réelles [1], la simulation permet de prédire et comprendre le comportement du matériau lors de la rentrée atmosphérique. Les modèles de l’ablation du carbone n’ont cessé de se complexifier [1, 3, 4, 5, 6]. Cependant, ils ne donnent pas de descriptions fines de la surface du matériau. C’est pour remédier à cela que plusieurs études ont été lancées au Laboratoire des Composites Thermostructuraux (LCTS) [7, 8]. Le Plasmatron du VKI est le moyen à haut flux de chaleur et à haute vitesse utilisé pour cette thèse [9, 10]. Dans cette étude, des échantillons sont testés sous des flux de chaleur allant jusqu’à 2800 kW/m2. Ces essais sur le composite 3D carbone/carbone (Cf/C) ont mené à des résultats très intéressants sur la morphologie du composite lors de l’ablation. Le four à image d’arc est le moyen à très haut flux de chaleur et à convection nulle utilisé au cours de cette thèse. Des flux de chaleurs de 10 MW m-2 ont pu être appliqués à des échantillons de 3D Cf/C. Les observations MEB couplées à la reconstruction numérique du four ont permis de noter les différences entre l’oxydation et la sublimation du composite. Un code de diffusion/ablation est développé depuis plusieurs années au LCTS [7, 11, 12, 13, 14] : AMA. Il permet de simuler l’ablation d’un matériau en carbone. Ce code a été validé par J. Lachaud sans prise en compte de l’écoulement [7]. Un nouveau couplage avec le code Open-Foam [15] a été développé et validé. Le code AMA a été utilisé afin de déterminer les paramètres influençant la rugosité du 3D Cf/C sous un écoulement laminaire. / Carbonaceous materials have been selected to protect atmospheric re-entry vehicles under the most extremes conditions [1, 2]. Because real flight experiments are very expensive [1], simulation is an important means to predict and understand the material behaviour during atmospheric re-entry. The models of carbonaceous materials ablation have become more and more complex [1, 3, 4, 5, 6]. However, they are not accurate to describe finely the material surface. To find a solution to this problem, several studies have been conducted at the Laboratoire des Composites Thermostructuraux (LCTS) [7, 8]. The Plasmatron of the VKI is the experimental means which has been used in this doctoral thesis. It can reach moderately high heat flux under high speed flow [9, 10]. In this study, several samples have been tested under an heat flux up to 2800 kW/m2. These tests on the 3D carbon/carbon (Cf/C) composite have given very interesting results about the material morphology during ablation. An arc image furnace, which can reach very high heat flux but without important flow field, has been used during this doctoral study. 3D Cf/C samples have been ablated under heat flux up to 10 MW m-2. SEM observations with the help of a numerical simulation of the furnace, have put the differences between oxidation and sublimation forward. A diffusion/ablation code has been developed at LCTS for several years [7, 11, 12, 13, 14] : AMA. This piece of software is designed to simulate the ablation of a carbonaceous material. It has been validated without flow field by J. Lachaud [7]. A new coupling method between AMA and Open-Foam [15] has been developed and validated. Finally, AMA has been used to point out the parameters which drive the 3D Cf/C surface recession under laminar flow field.

Cette thèse est consacrée à l’étude des trajectoires quantiques issues de la théorie desmesures continues en mécanique quantique non relativiste. On y présente de nouveaux résultatsthéoriques ainsi que des exemples d’applications. Sur le front théorique, on étudie principalementla limite de mesure «forte» dans laquelle on met en évidence l’émergence de sauts quantiques etd’échardes quantiques, deux phénomènes dont on précise la statistique. Hors de la limite forte, onpropose une méthode d’extraction optimale d’information pour un registre de qubits. Sur le frontdes applications, on introduit une méthode originale de contrôle utilisant l’intensité de la mesurecomme unique variable et on explique la transition balistique-diffusif dans les marches aléatoiresquantiques ouvertes; deux sous produits de l’étude théorique préalable des situations de mesureforte. On s’intéresse aussi au problème de la gravité semi-classique et montre que la théorie desmesures continues peut permettre d’en construire un modèle cohérent à la limite newtonienne. Onsuggère enfin quelques extensions possibles de la théorie à l’estimation a posteriori et d’éventuellesgénéralisations des résultats théoriques à des situations de mesures répétées discrètes. Dans laprésentation des résultats, l’accent est mis davantage sur l’explicitation des liens entre les multiplespoints de vue possibles sur les trajectoires quantiques (parallèles avec la théorie classique du filtrageet les modèles de collapse objectif utilisés dans les fondements) que sur la rigueur mathématique. / This thesis is devoted to the study of the quantum trajectories obtained from thetheory of continuous measurement in non relativistic quantum mechanics. New theoretical resultsas well as examples of applications are presented. On the theoretical front, we study mostly thelimit of «strong» measurement where we put forward the emergence of quantum jumps and quantumspikes, two phenomena we characterize in detail. Out of the strong measurement limit, weinvestigate a method to extract information from a register of qubits optimally. On the applicationfront, we introduce an original method to control quantum systems exploiting only the freedomof changing the measurement intensity and we explain the transition between a ballistic and adiffusive behavior in open quantum random walks; two byproduct of the theoretical study of thestrong measurement regime. We further study the problem of semi-classical gravity and show thatcontinuous measurement theory allows to construct a consistent model in the Newtonian regime.We eventually suggest possible extensions of the formalism to a posteriori estimation and hint atgeneralizations of the results for the strong measurement limit in the wider context of discreterepeated measurements. In the course of our presentation, we emphasize the link with other approachesto the theory of continuous measurement (parallels with stochastic filtering and collapsemodels in foundations) rather than aim for mathematical rigor.

Nous nous ici intéressons à la propagation d'états non-classiques de la lumière à travers des milieux désordonnés, comme les couches de peinture ou les fibres multimodes. Ces milieux sont généralement considérés comme des obstacles à la propagation de la lumière: par exemple, la diffusion de la lumière dans les tissus biologiques diminue considérablement les capacités des systèmes d'imagerie optique. C'est donc un phénomène duquel on souhaite généralement s'affranchir. Au contraire, dans notre étude nous exploitons ce désordre et utilisons ces milieux comme des "mélangeurs" de lumière. La lumière qui y pénètre est fortement diffusée et ses propriétés spectrales, spatiales et de polarisation sont complètement redistribuées. Cette redistribution est associée à un phénomène de propagation d'onde et d'interférence complexe qui est donc déterministe. Nous pouvons alors utiliser des méthodes de manipulation de front d'onde pour étudier ou contrôler ce mélange. Associés à des états non-classiques, ces systèmes permettent de réaliser des marches aléatoires quantiques dans des environnements bien plus complexes que ceux qui existent actuellement. Les méthodes de contrôle de front d'onde nous ont permis d'étudier et de manipuler ces marches aléatoires. Nous avons notamment montré qu'il est possible de guider les photons en manipulant les interférences classiques et quantiques. Ce travail nous a permis d'étudier de nouveaux aspects de la physique des milieux complexes, mais aussi d'explorer un nouveau type de plateformes pour marches aléatoires quantiques qui pourraient jouer un rôle important dans le développement des nouvelles applications pour traitement de l'information. / Light is not only an ideal medium to transmit information, but also a very interesting physical system to process it. In this respect, quantum optics has recently emerged as a highly promising domain for the development of new computing applications that can surpass the performances of currently available systems. In this respect, quantum walk of photons has recently emerged as a very powerful model for quantum information science, and integrated photonic devices have proven a versatile architecture for their implementation. While these waveguide structures allow only near-neighbor coupling between up to a few tens of modes, complex linear systems, such as white paint layer or multimode fiber, enable to couple efficiently a huge numbers of optical modes. Unstable and lossy, these systems have always been considered unpractical for quantum optics experiments. Wavefront shaping methods, developed in the last decade to control light propagating in complex media, allow moving beyond these limitations and make them exploitable with non-classical light. In our work, we demonstrate the implementation of quantum walks in a layer of paint and a multimode fiber using single-photons and photon-pairs. For this purpose, we extend wavefront shaping methods, originally developed to control classical light propagation in complex media, to non-classical light. This capability to manipulate photons allows building new controllable highly multimode optical platforms. Such systems pave the way for the next generation of quantum information processing devices.

Soit G un groupe dénombrable, qui se scinde en un produit libre de la forme G=G_1*...*G_k*F, où F est un groupe libre de type fini, et les G_i sont librement indécomposables et non isomorphes à Z. Nous montrons que le groupe Out(G) des automorphismes extérieurs de G satisfait l'alternative de Tits, dès lors que chacun des groupes G_i et Out(G_i) la satisfait. Par des méthodes similaires, nous montrons aussi l'alternative suivante pour tout sous-groupe H de Out(F_N), due à Handel et Mosher lorsque H est de type fini : soit H fixe virtuellement la classe de conjugaison d'un facteur libre propre de F_N, soit H contient un automorphisme complètement irréductible. Nos méthodes, géométriques, utilisent l'étude de la dynamique de l'action de certains sous-groupes de Out(G) sur des espaces hyperboliques. Nous décrivons notamment l'adhérence de l'outre-espace de G relatif aux G_i, et le bord de Gromov du complexe (hyperbolique) des scindements cycliques relatifs associé. Nous étudions par ailleurs les marches aléatoires sur Out(F_N). Sous un certain nombre de conditions sur la mesure de probabilité mu, nous montrons que presque toute trajectoire de la marche aléatoire sur (Out(F_N),mu) converge vers un point du bord de Gromov du complexe des facteurs libres de F_N, que nous identifions au bord de Poisson de (Out(F_N),mu). Par ailleurs, nous décrivons l'horofrontière de l'outre-espace. Ceci a des applications à l'étude de la croissance des classes de conjugaison de F_N sous l'effet de produits aléatoires d'automorphismes extérieurs. / Let G be a countable group that splits as a free product of the form G=G_1*...*G_k*F, where F is a finitely generated free group, and the groups G_i are freely indecomposable and not isomorphic to Z. We show that Out(G) satisfies the Tits alternative, as soon as all the groups G_i and Out(G_i) do. Similar techniques also yield another alternative for subgroups H of Out(F_N), due to Handel and Mosher when H is finitely generated, namely: either H virtually fixes the conjugacy class of some proper free factor of F_N, or H contains a fully irreducible automorphism. Our methods are geometric, and require understanding the dynamics of the action of some subgroups of Out(G) on Gromov hyperbolic spaces. In particular, we determine the closure of the outer space of G relative to the G_i's, as well as the Gromov boundary of the (hyperbolic) complex of relative cyclic splittings of G. We also study random walks on Out(F_N). Given a probability measure mu on Out(F_N) (satisfying some conditions), we prove that almost every sample path of the random walk on (Out(F_N),mu) converges to a point of the Gromov boundary of the free factor complex of F_N, which we identify with the Poisson boundary of (Out(F_N),mu). We also describe the horoboundary of outer space, and give applications to growth of conjugacy classes of F_N under random products of outer automorphisms.

Cette thèse est consacrée à l'étude des processus stochastiques décentralisés. Parmi les exemples typiques de ces processus figurent la dynamique météorologique, la circulation automobile, la façon dont nous rencontrons nos amis, etc. Dans cette thèse, nous exploitons une large palette d'outils probabilistes permettant d'analyser des chaînes de Markov afin d'étudier un large éventail de ces processus distribués : modèle des feux de forêt (réseaux sociaux), balls-into-bins avec suppression, et des dynamiques et protocoles de consensus fondamentaux tels que Voter Model, 2-Choices, et 3-Majority. / This thesis is devoted to the study of stochastic decentralized processes. Typical examples in the real world include the dynamics of weather and temperature, of traffic, the way we meet our friends, etc. We take the rich tool set from probability theoryfor the analysis of Markov Chains and employ it to study a wide range of such distributed processes: Forest Fire Model (social networks), Balls-into-Bins with Deleting Bins, and fundamental consensus dynamics and protocols such as the Voter Model, 2-Choices, and 3-Majority.

Le modèle de dimères, également connu sous le nom de modèle de couplage parfait, est un modèle probabiliste introduit à l'origine dans la mécanique statistique. Une configuration de dimères d'un graphe est un sous-ensemble des arêtes tel que chaque sommet est incident à exactement une arête. Un poids est attribué à chaque arête et la probabilité d'une configuration est proportionnelle au produit des poids des arêtes présentes. Dans cette thèse, nous étudions principalement deux modèles qui sont liés au modèle de dimères, et plus particulièrement leur comportements limites. Le premier est le modèle des forêts couvrantes enracinées sur des cycles (CRSF) sur le tore, qui sont en bijection avec les configurations de dimères via la bijection de Temperley. Dans la limite quand la taille du tore tend vers l'infini, la mesure sur les CRSF converge vers une mesure de Gibbs ergodique sur le plan tout entier. Nous étudions la connectivité de l'objet limite, prouvons qu'elle est déterminée par le changement de hauteur moyen de la mesure de Gibbs ergodique et donnons un diagramme de phase. Le second est le modèle de perles, un processus ponctuel sur $\mathbb{Z}\times\mathbb{R}$ qui peut être considéré comme une limite à l'échelle du modèle de dimères sur un réseau hexagonal. Nous formulons et prouvons un principe variationnel similaire à celui du modèle dimère \cite{CKP01}, qui indique qu'à la limite de l'échelle, la fonction de hauteur normalisée d'une configuration de perles converge en probabilité vers une surface $h_0$ qui maximise une certaine fonctionnelle qui s'appelle "entropie". Nous prouvons également que la forme limite $h_0$ est une limite de l'échelle des formes limites de modèles de dimères. Il existe une correspondance entre configurations de perles et (skew) tableaux de Young standard, qui préserve la mesure uniforme sur les deux ensembles. Le principe variationnel du modèle de perles implique une forme limite d'un tableau de Young standard aléatoire. Ce résultat généralise celui de \cite{PR}. Nous dérivons également l'existence d'une courbe arctique d'un processus ponctuel discret qui encode les tableaux standard, defini dans \cite{Rom}. / The dimer model, also known as the perfect matching model, is a probabilistic model originally introduced in statistical mechanics. A dimer configuration of a graph is a subset of the edges such that every vertex is incident to exactly one edge of the subset. A weight is assigned to every edge, and the probability of a configuration is proportional to the product of the weights of the edges present. In this thesis we mainly study two related models and in particular their limiting behavior. The first one is the model of cycle-rooted-spanning-forests (CRSF) on tori, which is in bijection with toroidal dimer configurations via Temperley's bijection. This gives rise to a measure on CRSF. In the limit that the size of torus tends to infinity, the CRSF measure tends to an ergodic Gibbs measure on the whole plane. We study the connectivity property of the limiting object, prove that it is determined by the average height change of the limiting ergodic Gibbs measure and give a phase diagram. The second one is the bead model, a random point field on $\mathbb{Z}\times\mathbb{R}$ which can be viewed as a scaling limit of dimer model on a hexagon lattice. We formulate and prove a variational principle similar to that of the dimer model \cite{CKP01}, which states that in the scaling limit, the normalized height function of a uniformly chosen random bead configuration lies in an arbitrarily small neighborhood of a surface $h_0$ that maximizes some functional which we call as entropy. We also prove that the limit shape $h_0$ is a scaling limit of the limit shapes of a properly chosen sequence of dimer models. There is a map form bead configurations to standard tableaux of a (skew) Young diagram, and the map is measure preserving if both sides take uniform measures. The variational principle of the bead model yields the existence of the limit shape of a random standard Young tableau, which generalizes the result of \cite{PR}. We derive also the existence of an arctic curve of a discrete point process that encodes the standard tableaux, raised in \cite{Rom}.

Dans cette thèse, on s'intéresse à des algorithmes d'analyse de données utilisant des marches aléatoires sur des graphes de voisinage, ou graphes géométriques aléatoires, construits à partir des données. On sait que les marches aléatoires sur ces graphes sont des approximations d'objets continus appelés processus de diffusion. Dans un premier temps, nous utilisons ce résultat pour proposer un nouvel algorithme de partitionnement de données flou de type recherche de modes. Dans cet algorithme, on définit les paquets en utilisant les propriétés d'un certain processus de diffusion que l'on approche par une marche aléatoire sur un graphe de voisinage. Après avoir prouvé la convergence de notre algorithme, nous étudions ses performances empiriques sur plusieurs jeux de données. Nous nous intéressons ensuite à la convergence des mesures stationnaires des marches aléatoires sur des graphes géométriques aléatoires vers la mesure stationnaire du processus de diffusion limite. En utilisant une approche basée sur la méthode de Stein, nous arrivons à quantifier cette convergence. Notre résultat s'applique en fait dans un cadre plus général que les marches aléatoires sur les graphes de voisinage et nous l'utilisons pour prouver d'autres résultats : par exemple, nous arrivons à obtenir des vitesses de convergence pour le théorème central limite. Dans la dernière partie de cette thèse, nous utilisons un concept de topologie algébrique appelé homologie persistante afin d'améliorer l'étape de "pooling" dans l'approche "sac-de-mots" pour la reconnaissance de formes 3D. / In this thesis, we study data analysis algorithms using random walks on neighborhood graphs, or random geometric graphs. It is known random walks on such graphs approximate continuous objects called diffusion processes. In the first part of this thesis, we use this approximation result to propose a new soft clustering algorithm based on the mode seeking framework. For our algorithm, we want to define clusters using the properties of a diffusion process. Since we do not have access to this continuous process, our algorithm uses a random walk on a random geometric graph instead. After proving the consistency of our algorithm, we evaluate its efficiency on both real and synthetic data. We then deal tackle the issue of the convergence of invariant measures of random walks on random geometric graphs. As these random walks converge to a diffusion process, we can expect their invariant measures to converge to the invariant measure of this diffusion process. Using an approach based on Stein's method, we manage to obtain quantitfy this convergence. Moreover, the method we use is more general and can be used to obtain other results such as convergence rates for the Central Limit Theorem. In the last part of this thesis, we use the concept of persistent homology, a concept of algebraic topology, to improve the pooling step of the bag-of-words approach for 3D shapes.

L’émergence récente de grands réseaux, surtout réseaux sociaux en ligne (OSN), a révélé la difficulté de crawler le réseau complet et a déclenché le développement de nouvelles techniques distribuées. Dans cette thèse, nous concevons et analysons des algorithmes basés sur les marches aléatoires et la diffusion pour l'échantillonnage, l'estimation et l'inférence des fonctions des réseaux. La thèse commence par le problème classique de trouver les valeurs propres dominants et leurs vecteurs propres de matrices de graphe symétriques, comme la matrice Laplacienne de graphes non orientés. En utilisant le fait que le spectre est associé à une équation de type différentiel Schrödinger, nous développons des techniques évolutives à l’aide de la diffusion sur le graphe. Ensuite, nous considérons l’échantillonnage des fonctions de réseau (comme somme et moyenne) en utilisant les marches aléatoires sur le graphe. Afin d'éviter le temps «burn-in» de marche aléatoire, avec l'idée de régénération à un nœud fixe, nous développons un estimateur de la fonction de somme qui est non asymptotiquement non-biaisé et dérivons une approximation à la postérieure Bayésienne. La dernière partie de la thèse étudie l'application de la théorie des valeurs extrêmes pour faire une inférence sur les événements extrêmes à partir des échantillons stationnaires des différentes marches aléatoires pour l’échantillonnage de réseau / The recent emergence of large networks, mainly due to the rise of online social networks, brought out the difficulty to gather a complete picture of a network and it prompted the development of new distributed techniques. In this thesis, we design and analyze algorithms based on random walks and diffusion for sampling, estimation and inference of the network functions, and for approximating the spectrum of graph matrices. The thesis starts with the classical problem of finding the dominant eigenvalues and the eigenvectors of symmetric graph matrices like Laplacian of undirected graphs. Using the fact that the eigenspectrum is associated with a Schrödinger-type differential equation, we develop scalable techniques with diffusion over the graph and with gossiping algorithms. They are also adaptable to a simple algorithm based on quantum computing. Next, we consider sampling and estimation of network functions (sum and average) using random walks on graph. In order to avoid the burn-in time of random walks, with the idea of regeneration at its revisits to a fixed node, we develop an estimator for the aggregate function which is non-asymptotically unbiased and derive an approximation to its Bayesian posterior. An estimator based on reinforcement learning is also developed making use of regeneration. The final part of the thesis deals with the use of extreme value theory to make inference from the stationary samples of the random walks. Extremal events such as first hitting time of a large degree node, order statistics and mean cluster size are well captured in the parameter “extremal index”. We theoretically study and estimate extremal index of different random walk sampling techniques