To see the other types of publications on this topic, follow the link: Graphons de probabilités.
Dissertations / Theses on the topic 'Graphons de probabilités'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Graphons de probabilités.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Weibel, Julien. "Graphons de probabilités, limites de graphes pondérés aléatoires et chaînes de Markov branchantes cachées." Electronic Thesis or Diss., Orléans, 2024. http://www.theses.fr/2024ORLE1031.
Full textAbstract:
Les graphes sont des objets mathématiques qui servent à modéliser tout type de réseaux, comme les réseaux électriques, les réseaux de communications et les réseaux sociaux. Formellement un graphe est composé d'un ensemble de sommets et d'un ensemble d'arêtes reliant des paires de sommets. Les sommets représentent par exemple des individus, tandis que les arêtes représentent les interactions entre ces individus. Dans le cas d'un graphe pondéré, chaque arête possède un poids ou une décoration pouvant modéliser une distance, une intensité d'interaction, une résistance. La modélisation de réseaux réels fait souvent intervenir de grands graphes qui ont un grand nombre de sommets et d'arêtes.La première partie de cette thèse est consacrée à l'introduction et à l'étude des propriétés des objets limites des grands graphes pondérés : les graphons de probabilités. Ces objets sont une généralisation des graphons introduits et étudiés par Lovász et ses co-auteurs dans le cas des graphes sans poids sur les arêtes. À partir d'une distance induisant la topologie faible sur les mesures, nous définissons une distance de coupe sur les graphons de probabilités. Nous exhibons un critère de tension pour les graphons de probabilités lié à la compacité relative dans la distance de coupe. Enfin, nous prouvons que cette topologie coïncide avec la topologie induite par la convergence en distribution des sous-graphes échantillonnés. Dans la deuxième partie de cette thèse, nous nous intéressons aux modèles markoviens cachés indexés par des arbres. Nous montrons la consistance forte et la normalité asymptotique de l'estimateur de maximum de vraisemblance pour ces modèles sous des hypothèses standards. Nous montrons un théorème ergodique pour des chaînes de Markov branchantes indexés par des arbres avec des formes générales. Enfin, nous montrons que pour une chaîne stationnaire et réversible, le graphe ligne est la forme d'arbre induisant une variance minimale pour l'estimateur de moyenne empirique parmi les arbres avec un nombre donné de sommetsGraphs are mathematical objects used to model all kinds of networks, such as electrical networks, communication networks, and social networks. Formally, a graph consists of a set of vertices and a set of edges connecting pairs of vertices. The vertices represent, for example, individuals, while the edges represent the interactions between these individuals. In the case of a weighted graph, each edge has a weight or a decoration that can model a distance, an interaction intensity, or a resistance. Modeling real-world networks often involves large graphs with a large number of vertices and edges.The first part of this thesis is dedicated to introducing and studying the properties of the limit objects of large weighted graphs : probability-graphons. These objects are a generalization of graphons introduced and studied by Lovász and his co-authors in the case of unweighted graphs. Starting from a distance that induces the weak topology on measures, we define a cut distance on probability-graphons. We exhibit a tightness criterion for probability-graphons related to relative compactness in the cut distance. Finally, we prove that this topology coincides with the topology induced by the convergence in distribution of the sampled subgraphs. In the second part of this thesis, we focus on hidden Markov models indexed by trees. We show the strong consistency and asymptotic normality of the maximum likelihood estimator for these models under standard assumptions. We prove an ergodic theorem for branching Markov chains indexed by trees with general shapes. Finally, we show that for a stationary and reversible chain, the line graph is the tree shape that induces the minimal variance for the empirical mean estimator among trees with a given number of vertices
2
Selig, Thomas. "Convergence de cartes et tas de sable." Thesis, Bordeaux, 2014. http://www.theses.fr/2014BORD0286/document.
Full textAbstract:
Cette thèse est dédiée à l'étude de divers problèmes se situant à la frontière entre combinatoire et théorie des probabilités. Elle se compose de deux parties indépendantes : la première concerne l'étude asymptotique de certaines familles de \cartes" (en un sens non traditionnel), la seconde concerne l'étude d'une extension stochastique naturelle d'un processus dynamique classique sur un graphe appelé modèle du tas de sable. Même si ces deux parties sont a priori indépendantes, elles exploitent la même idée directrice, à savoir les interactions entre les probabilités et la combinatoire, et comment ces domaines sont amenés à se rendreservice mutuellement. Le Chapitre introductif 1 donne un bref aperçu des interactions possibles entre combinatoire et théorie des probabilités, et annonce les principaux résultats de la thèse. Le Chapitres 2 donne une introduction au domaine de la convergence des cartes. Les contributions principales de cette thèse se situent dans les Chapitres 3, 4 (pour les convergences de cartes) et 5 (pour le modèle stochastique du tas de sable)This Thesis studies various problems located at the boundary between Combinatorics and Probability Theory. It is formed of two independent parts. In the first part, we study the asymptotic properties of some families of \maps" (from a non traditional viewpoint). In thesecond part, we introduce and study a natural stochastic extension of the so-called Sandpile Model, which is a dynamic process on a graph. While these parts are independent, they exploit the same thrust, which is the many interactions between Combinatorics and Discrete Probability, with these two areas being of mutual benefit to each other. Chapter 1 is a general introduction to such interactions, and states the main results of this Thesis. Chapter 2 is an introduction to the convergence of random maps. The main contributions of this Thesis can be found in Chapters 3, 4 (for the convergence of maps) and 5 (for the Stochastic Sandpile model)
3
Budzinski, Thomas. "Cartes aléatoires hyperboliques." Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLS426/document.
Full textAbstract:
Cette thèse s'inscrit dans la théorie des cartes planaires aléatoires, active depuis une quizaine d'années, et plus précisément dans l'étude de modèles de nature hyperbolique.Dans un premier temps, nous nous intéressons à un modèle de triangulations aléatoires dynamiques basé sur les flips d'arêtes, et nous montrons une borne inférieure sur le temps de mélange de ce modèle.Dans la suite, l'objet d'étude principal est une famille de triangulations aléatoires hyperboliques, appelées PSHT. Il s'agit de variantes de la triangulation uniforme du plan (UIPT), qui ont été introduites en 2014 par Nicolas Curien. Nous commençons par établir un résultat de limite d'échelle quasi-critique : si on renormalise les distances tout en faisant tendre le paramètre d'hyperbolicité vers sa valeur critique, les triangulations étudiées convergent vers un espace métrique aléatoire appelé plan brownien hyperbolique. Nous étudions également des propriétés métriques fines des PSHT et du plan brownien hyperbolique, et notamment la structure de leurs géodésiques infinies. Nous présentons aussi de nouvelles propriétés de la frontière de Poisson des PSHT.Enfin, nous nous intéressons à un autre modèle naturel de cartes aléatoires hyperboliques : les cartes causales surcritiques, qui sont construites à partir d'arbres de Galton--Watson surcritiques, en ajoutant des arêtes entre sommets de même hauteur. Nous établissons des résultats d'hyperbolicité métrique, ainsi que des propriétés de la marche aléatoire sur ces cartes, dont un résultat de vitesse positive. Certaines des propriétés obtenues sont robustes, et peuvent se généraliser à n'importe quelle carte planaire contenant un arbre de Galton--Watson surcritiqueThis thesis falls into the theory of random planar maps, which has been active in the last fifteen years, and more precisely into the study of hyperbolic models.We are first interested in a model of dynamical random triangulations based on edge-flips, where we prove a lower bound on the mixing time.In the rest of this thesis, the main objects that we study are the random hyperbolic triangulations called PSHT. These are hyperbolic variants of the Uniform Infinite Planar Triangulation (UIPT), and were introduced by Nicolas Curien in 2014. We first establish a near-critical scaling limit result: if we let the hyperbolicity parameter go to its critical value at the same time as the distances are renormalized, the PSHT converge to a random metric space that we call the hyperbolic Brownian plane. We also study precise metric properties of the PSHT and of the hyperbolic Brownian plane, such as the structure of their infinite geodesics. We obtain as well new properties of the Poisson boundary of the PSHT.Finally, we are interested in another natural model of hyperbolic random maps: supercritical causal maps, which are obtained from supercritical Galton--Watson trees by adding edges between vertices at the same height. We establish metric hyperbolicity results about these maps, as well as properties of the simple random walk (including a positive speed result). Some of the properties we obtain are robust, and may be generalized to any planar map containing a supercritical Galton--Watson tree
4
Ravelomanana, Vlady. "Graphes multicycliques étiquetés : aspects combinatoires et probabilistes." Amiens, 2000. http://www.theses.fr/2000AMIE0122.
Full text
5
Broutin, Nicolas. "Random trees, graphs and recursive partitions." Habilitation à diriger des recherches, Université Pierre et Marie Curie - Paris VI, 2013. http://tel.archives-ouvertes.fr/tel-00842019.
Full textAbstract:
Je présente dans ce mémoire mes travaux sur les limites d'échelle de grandes structures aléatoires. Il s'agit de décrire les structures combinatoires dans la limite des grandes tailles en prenant un point de vue objectif dans le sens où on cherche des limites des objets, et non pas seulement de paramètres caractéristiques (même si ce n'est pas toujours le cas dans les résultats que je présente). Le cadre général est celui des structures critiques pour lesquelles on a typiquement des distances caractéristiques polynomiales en la taille, et non concentrées. Sauf exception, ces structures ne sont en général pas adaptées aux applications informatiques. Elles sont cependant essentielles de part l'universalité de leurs propriétés asymptotiques, prouvées ou attendues. Je parle en particulier d'arbres uniformément choisis, de graphes aléatoires, d'arbres couvrant minimaux et de partitions récursives de domaines du plan:Arbres aléatoires uniformes. Il s'agit ici de mieux comprendre un objet limite essentiel, l'arbre continu brownien (CRT). Je présente quelques résultats de convergence pour des modèles combinatoires ''non-branchants'' tels que des arbres sujets aux symétries et les arbres à distribution de degrés fixée. Je décris enfin une nouvelle décomposition du CRT basée sur une destruction partielle.
Graphes aléatoires. J'y décris la construction algorithmique de la limite d'échel-le des graphes aléatoires du modèle d'Erdös--Rényi dans la zone critique, et je fais le lien avec le CRT et donne des constructions de l'espace métrique limite. Arbres couvrant minimaux. J'y montre qu'une connection avec les graphes aléatoires permet de quantifier les distances dans un arbre convrant aléatoire. On obtient non seulement l'ordre de grandeur de l'espérance du diamètre, mais aussi la limite d'échelle en tant qu'espace métrique mesuré. Partitions récursives. Sur deux exemples, les arbres cadrant et les laminations du disque, je montre que des idées basées sur des théorèmes de point fixe conduisent à des convergences de processus, où les limites sont inhabituelles, et caractérisées par des décompositions récursives.
6
El, Maftouhi Abdelhakim. "Méthodes probabilistes en combinatoire et théorie des graphes." Paris 11, 1994. http://www.theses.fr/1994PA112408.
Full textAbstract:
Cette thèse rassemble plusieurs travaux dont le point commun est l'utilisation de méthodes probabilistes. La première partie concerne l'étude des paramètres de domination et d'irredondance dans les graphes aléatoires de probabilité d'arête 1/2. Nos résultats apportent un point final à l'étude du trio: irredondance, domination et stabilité dans ces graphes. Dans la deuxième partie on délaisse momentanément les probabilités pour aborder les graphes signés. On s'intéresse plus particulièrement au problème de l'équilibre dans ces graphes. On introduit la notion de sous-graphes équilibrants dont on donne quelques caractérisations qui permettent d'obtenir de nouveaux résultats. Nous introduisons dans la troisième partie la notion de graphes signés aléatoires et nous étudions les principales propriétés statistiques de ces graphes. La quatrième partie est consacrée à l'énumération d'une classe d'ordres partiels. Nous donnons une procédure pour calculer le nombre d'ordres partiels gradués de largeur et de rang donnes. Pour une largeur fixée la procédure utilise un temps de calcul qui est une fonction linéaire du rang. Finalement, dans la dernière partie, on étudie le problème de la satisfiabilité d'un ensemble de 3-clauses aléatoires
7
Murat, Cécile. "Les problèmes d'optimisation combinatoire probabilistes dans les graphes." Paris 9, 1997. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1997PA090054.
Full textAbstract:
L'objet de cette thèse est l'optimisation combinatoire probabiliste de problèmes définis en termes de graphes. Dans ce cadre, un système de probabilités est associé aux sommets du graphe afin de traduire le fait que nous ne connaissons pas le sous-graphe pour lequel le problème sera à résoudre. L'approche utilisée consiste alors à définir une solution dite a priori, qui sous-entend que tous les éléments du graphe d'origine soient présents. Pour une sous-instance donnée, pour laquelle certains éléments du graphe sont absents, il faudra adapter la solution a priori, à l'aide d'un algorithme appelé stratégie de modification, afin qu'elle devienne solution de l'instance considérée. Après avoir situé ces problèmes, par rapport à ceux étudiés dans le cadre de la théorie des graphes aléatoires, nous présentons la méthodologie employée et la formalisons. Nous proposons alors, un état de l'art des travaux réalisés avec cette approche pour les problèmes dont l'instance est un graphe. Puis, nous présentons les résultats que nous avons établis pour les problèmes du stable probabiliste, de la couverture de sommets probabiliste et de plus longs chemins probabilistes. Ceci nous amène a opérer une première classification et structuration de problèmes d'optimisation combinatoire probabilistes selon leur complexité et résolution. La dernière partie de cette thèse, constitue un développement du formalisme du cadre d'étude. Pour cela, nous présentons nos premières réflexions concernant l'utilisation de nouveaux critères. Enfin, nous finissons en introduisant les premières notions nécessaires à la mise en place d'un cadre structure pour l'étude de l'approximation des problèmes d'optimisation combinatoire probabilistes.
8
Panafieu, Elie de. "Combinatoire analytique des graphes, hypergraphes et graphes inhomogènes." Paris 7, 2014. http://www.theses.fr/2014PA077167.
Full textAbstract:
Nous étudions deux modèles qui généralisent la notion de graphe : les hypergraphes non-uniformes et les graphes inhomogènes. Ces modèles sont proches de ceux définis par Darling et Norris (2004) et Sôderberg (2002). Nous étudions leur énumération et leur structure typique avant et autour de la naissance de la composante géante. Nous montrons que les graphes inhomogènes sont un cadre idéal pour la modélisation de nombreux problèmes de satisfaction de contraintes (CSP) de complexité polynomiale, tels que la 2-colorabilité, la satisfaisabilité de formules 2- Xor et de formules 2-Xor quantifiées. Nous relions la probabilité de satisfaisabilité de ces problèmes à l'énumération des graphes inhomogènes. En application, plusieurs résultats de transition de phase anciens et nouveaux reçoivent une preuve dans un cadre unifié. Enfin, nous proposons une nouvelle preuve simple du nombre de multigraphes connexes possédant un nombre d'arêtes proportionnel au nombre de sommets, Ce résultat a été obtenu dans le cadre des graphes simples par Bender, Canfield et McKay (1990). L'outil principale de cette thèse est la combinatoire analytique, telle que définie par Flajolet et Sedgewick dans leur livre (2009)We investigate two graph-like models: the non-uniform hypergraphs and the inhomogeneous graphs. They are close to the models defined by Darling and Norris (2004) and Sôderberg (2002). We enumerate them and derive structure information before and near the birth of the giant component. The inhomogeneous graph model proves to be a convenient framework for the modeling of several tractable constraint satisfaction problems (CSP), such as the 2-colorability problem, the satisfiability of 2-Xor formulas and of quantified 2-Xor formulas. We link the probability of satisfiability of those problems to the enumeration of inhomogeneous graphs. As an application, proofs of old and new phase transition results are derived in a unified framework. Finally, we derive a new simple proof for the asymptotic number of connected multigraphs with a number of edges proportional to the number of vertices. This result was first derived for simple graphs by Bender, Canfield and McKay (1990). The main tool of this thesis is analytic combinatorics, as defined by Flajolet and Sedgewick in their book (2009)
9
Hutchcroft, Thomas. "Discrete probability and the geometry of graphs." Thesis, University of British Columbia, 2017. http://hdl.handle.net/2429/62595.
Full textAbstract:
We prove several theorems concerning random walks, harmonic functions, percolation, uniform spanning forests, and circle packing, often in combination with each other. We study these models primarily on planar graphs, on transitive graphs, and on unimodular random rooted graphs, although some of our results hold for more general classes of graphs. Broadly speaking, we are interested in the interplay between the geometry of a graph and the behaviour of probabilistic processes on that graph. Material taken from a total of nine papers is included. We have also included an extended introduction explaining the background and context to these papers.Science, Faculty of
Mathematics, Department of
Graduate
10
Mercier, Lucas. "Grands graphes et grands arbres aléatoires : analyse du comportement asymptotique." Thesis, Université de Lorraine, 2016. http://www.theses.fr/2016LORR0028/document.
Full textAbstract:
Cette thèse est consacrée à l'étude du comportement asymptotique de grands graphes et arbres aléatoires. Le premier modèle étudié est un modèle de graphe aléatoire inhomogène introduit par Bo Söderberg. Un chapitre de ce manuscrit est consacré à l'étude asymptotique de la taille des composantes connexes à proximité de la fenêtre critique, en le reliant à la longueur des excursions d'un mouvement brownien avec dérive parabolique, étendant les résultats obtenus par Aldous. Le chapitre suivant est consacré à un processus de graphes aléatoires proposé par Itai Benjamini, défini ainsi : les arêtes sont ajoutées indépendamment, à taux fixe. Lorsqu'un sommet atteint le degré k, toutes les arêtes adjacentes à ce sommet sont immédiatement supprimées. Ce processus n'est pas croissant, ce qui empêche d'utiliser directement certaines approches usuelles. L'utilisation de limites locales permet de montrer la présence (resp. l'absence) d'une composante géante à certaines étapes dans le cas k>=5 (resp. k<=3). Dans le cas k=4, ces résultats permettent de caractériser la présence d'une composante géante en fonction du caractère surcritique ou non d'un processus de branchement associé. Dans le dernier chapitre est étudiée la hauteur d'un arbre de Lyndon associé à un mot de Lyndon choisi uniformément parmi les mots de Lyndon de longueur n, prouvant que cette hauteur est approximativement c ln n, avec c=5,092... la solution d'un problème d'optimisation. Afin d'obtenir ce résultat, nous couplons d'abord l'arbre de Lyndon à un arbre de Yule, que nous étudions ensuite à l'aide de techniques provenant des théories des marches branchantes et des grandes déviationsThis thesis is dedicated to the study of the asymptotic behavior of some large random graphs and trees. First is studied a random graph model introduced by Bo Söderberg in 2002. One chapter of this manuscript is devoted to the study of the asymptotic behavior of the size of the connected components near the critical window, linking it to the lengths of excursion of a Brownian motion with parabolic drift. The next chapter talks about a random graph process suggested by Itai Benjamini, defined as follows: edges are independently added at a fixe rate. Whenever a vertex reaches degree k, all adjacent edges are removed. This process is non-increasing, preventing the use of some commonly used methods. By using local limits, in the spirit of the PWIT, we were able to prove the presence (resp. absence) of a giant component at some stages of the process when k>=5 (resp. k<=3). In the case k=4, these results allows to link the presence (resp. absence) of a giant component to the supercriticality (resp. criticality or subcriticality) of an associated branching process. In the last chapter, the height of random Lyndon tree is studied, and is proven to be approximately c ln n, in which c=5.092... the solution of an optimization problem. To obtain this result, we couple the Lyndon tree with a Yule tree, then studied with the help of branching walks and large deviations
11
Launay, Mickaël. "Urnes interagissantes." Thesis, Aix-Marseille, 2012. http://www.theses.fr/2012AIXM4775/document.
Full textAbstract:
Nous nous intéressons au comportement asymptotique de plusieurs urnes de type Polya fortement renforcées et interagissantes. Le principal de notre étude porte sur les renforcements exponentiels ou assimilés ainsi que sur les interactions temporelles, c'est-à-dire lors desquelles les urnes n'interagissent qu'à certains instants aléatoires. Dans ce cas, nous mettons en évidence une transition de phase selon la fréquence des interactions. Si celle ci est supérieure à 1/2, les urnes se fixent toutes sur la même couleur tandis que si elle est inférieure à 1/2, une couleur majoritaire se dégage mais certaines urnes peuvent continuer à tirer une autre couleur aux instants où il n'y a pas interaction. Lorsque le renforcement devient infini, nous pouvons calculer la loi du nombre d'urnes se comportant de cette dernière façon quand le nombre total d'urnes est égal à deux ou est un nombre impair.Quand l'interaction est totale, c'est-à-dire quand toutes les urnes interagissent à tout instant, nous montrons alors qu'un renforcement fort et croissant, mais plus nécessairement exponentiel, suffit à obtenir la fixation de toutes les urnes sur la même couleur.Pour finir, nous discutons brièvement du modèle d'interaction spatiale dans lequel les urnes sont situées sur les sommets d'un graphe et n'interagissent qu'avec leurs voisines. Nous dégageons alors quelques propriétés préliminaires concernant les sous-graphes susceptibles de se fixer sur une couleur avec une probabilité positiveWe study the asymptotic behavior of several Polya-type strongly reinforced interacting urns. The main results deal with exponential or exponential-like reinforcements and temporal interactions, that is when the urns interact only at some random times. In that case, we show the existence of a transition of phase depending on the frequency of interactions. If this frequency is larger than 1/2, all the urns eventually fixate on the same color, while if it is smaller than 1/2, a majority color will be fixed after some finite random time but while some of the urns eventually draw only the majority color, there can be other urns that still draw other colors at times where there is no interactions. When the reinforcement becomes infinite, we can calculate the law of the number of urns of later type when the total number of urns is two or an odd integer greater than two.When the interaction is maximal, that is when all the urns interact at any time, we show that a strong and non-decreasing reinforcement, but not necessarily exponential, suffices to obtain the fixation of all the urns on the same color.At the end, we consider briefly the spatial interaction model in which the urns are located on the vertices of a graph and interact only with their neighbors. In that case, we discuss some properties of sub-graphs that can fixate on one color with positive probability
12
Faÿ, Armelle. "Sur la propagation de l'information dans les réseaux probabilistes." Paris 6, 1997. http://www.theses.fr/1997PA066770.
Full text
13
Gaertig-Stahl, Alice. "Modèles probabilistes de feux de forêt sur des graphes infinis." Toulouse 3, 2012. http://thesesups.ups-tlse.fr/1884/.
Full textAbstract:
Cette thèse concerne l'étude de modèles de feux de forêt d'un point de vue probabiliste. Les modèles que nous avons étudiés ont été introduits dans le cadre de l'étude des systèmes critiques auto-organisés à la fin des années 80. Il s'agit de systèmes de particules, les arbres, définis sur un graphe connecté. Leur évolution est régie par deux familles de processus de Poisson, l'une pour la croissance des arbres, l'autre pour leur disparition via l'action de la foudre. L'influence de la foudre est caractérisée par un paramètre lambda > 0. Ces modèles ont été beaucoup étudiés sur Z. Par contre sur des graphes infinis plus généraux, seules son existence et son unicité ont été montrées jusqu'à présent. Dans cette thèse, nous avons étudié ces modèles sur Zd pour d > 2 et sur les arbres binaires, dans deux directions. La première concerne l'existence de mesures invariantes. La deuxième concerne l'étude de ce modèle lorsque le paramètre lambda tend vers 0. Dans la première partie, nous montrerons que pour tous les paramètres lambda > 0, les processus de feux de forêt sur Zd pour d > 2 possèdent au moins une mesure invariante. Les processus de feux de forêt sont des processus de Markov non Feller, donc on ne peut pas appliquer les théorèmes usuels de l'étude des systèmes de particules. De plus, la géométrie de Zd ne permet pas d'utiliser les mêmes arguments que dans le cas de Z. Nous utiliserons des outils développés lors de l'étude de ces modèles sur Zd. Dans une seconde partie, nous nous consacrerons à la problématique de l'existence d'un processus limite lorsque lambda tend vers 0, sur les arbres binaires. Dans un premier temps, nous étudierons un modèle sans feux pour mieux comprendre comment grossissent les composantes connexes d'arbres. En se plaçant dans une nouvelle échelle de temps et d'espace, nous montrerons la convergence en loi de la taille d'un ensemble de sites construit à partir d'une boule de rayon n et des composantes connexes qui l'intersectent, au bout d'un temps t(n) > 0. Dans un deuxième temps, nous rajouterons l'action de feux, en définissant un modèle différent du modèle initial. Dans ce modèle modifié, les composantes connexes autres que celle de l'origine suivront une loi stationnaire à laquelle on s'attend à la limite, et non la dynamique du modèle de feux de forêt initial. Pour ce modèle, nous montrerons la convergence en loi de la taille renormalisée de la composante connexe de l'origine au moment où elle brûle pour la première foisThis work is concerned with a probabilistic study of forest-fire models. The models studied here were introduced in the context of self-organized criticality at the end of the eighties. These models are systems of particles, the trees, defined on connected graphs. Their evolution is governed by two families of Poisson processes, one for the growth of trees, the other one for the ignition of trees by lightning. The influence of lightning is characterized by a parameter lambda > 0. These models were widely studied on Z. However, only the existence and uniqueness of more general infinitevolume forest-fire processes have been proven yet. In this thesis, we studied forest-fire models on Zd for d > 2 and on binary trees, in two directions. The first one is concerned with the existence of stationary measures. The second one is concerned with the study of these processes when the parameter lambda tends to zero. In the first part, we will show the existence of at least one stationary measure for forest-fire processes on Zd, d > 2, for all parameters lambda > 0. The forest-fire processes are Markov processes but not Feller processes, so the usual arguments cannot be used here. Moreover, the geometry of Zd does not allow using the same arguments as for Z. Tools developed while studying these processes on Zd will be used here. In the second part, we will study the behavior of the forest-fire processes on binary trees when the parameter lambda tends to zero. We will begin with the study of a model without any fires, in order to understand better how the clusters of trees grow. We will show a convergence in law of the number of sites of a set construct from a ball of radius and the intersecting clusters, after a time tn > 0, for processes rescaled in space and time. Then, we will add fires and define a modified forest-fire model. In this new model, apart from the cluster of the origin, the clusters evolve under a stationary measure which we expect at the limit in lambda, and not under the dynamic of the initial forest-fire model. For this model, we will show a convergence in law of the rescaled size of the cluster of the origin when it burns for the first time
14
Gatta, Alessandro. "Diagrammes d'influence : Méthodologie et logiciel pour la résolution de graphes de décision." Paris 6, 1992. http://www.theses.fr/1992PA066720.
Full text
15
Loynes, Basile de. "Graphes & marches aléatoires." Rennes 1, 2012. https://ecm.univ-rennes1.fr/nuxeo/site/esupversions/2c2ff4a7-cb0d-4f16-bdaa-3e8ec028fa8d.
Full textAbstract:
The study of random walks demonstrates connections between their algebraic, combinatorial, geometric and stochastic properties. The first example of such a connection was given in a theorem of P\'olya dealing with nearest neighbourhood random walks on the space of N-dimensional integers. Random walks on groups provide with many examples, however it should be interesting to have such rigid results in the case of weaker algebraic structures such that semigroupoids and groupoids. In this thesis, one example of semigroupoid and one example of groupoid are considered; they are both defined as constrained subgraphs of the Cayley graph of a group, the first one is genuinely directed contrary to the second one which is undirected. For this first example, it has been shown by Campanino and Petritis that the simple random walk is transient. Here, we refine this statement by determining the Martin boundary of this process and show its triviality. In the second example, we consider quasi-periodic tilings of the Euclidean spaces obtained with the help of the cut-and-project scheme. We have considered the simple random walk along the sides of the polytopes constituting the tiling and answered the question of its type, i. E. We determined whether the random walk is recurrent or transient. This result is a consequence of isoperimetric inequalities. This strategy allow us to obtain estimates of the rate of convergence of the heat kernel which could not have been done with the help of the Nash-Williams criterionL'étude des marches aléatoires fait apparaître des connexions entre leurs propriétés algébriques, géométriques ou encore combinatoires et leurs propriétés stochastiques. Si les marches aléatoires sur les groupes - ou sur des espaces homogènes - fournissent beaucoup d'exemples, il serait appréciable d'obtenir de tels résultats de rigidité sur des structures algébriques plus faibles telles celles de semi-groupoide ou de groupoide. Dans cette thèse il est considéré un exemple de semi-groupoide et un exemple de groupoide, tous les deux sont définis a partir de sous-graphes contraints du graphe de Cayley d'un groupe - le premier graphe est dirige alors que le second ne l'est pas. Pour ce premier exemple, on précise un résultat de Campanino et Petritis (ils ont montre que la marche aléatoire simple était transiente pour cet exemple de graphe dirigé) en déterminant la frontière de Martin associée à cette marche et établissant sa trivialité Dans le second exemple apparaissant dans ce manuscrit, on considère des pavages quasi-périodiques de l'espace euclidien obtenus à l'aide de la méthode de coupe et projection. Nous considérons la marche aléatoire simple le long des arêtes des polytopes constituant le pavage, et nous répondons a la question du type de celle-ci, c'est-à-dire nous déterminons si elle est récurrente ou transiente. Nous montrons ce résultat en établissant des inégalités isopérimétriques Cette stratégie permet d'obtenir des estimées de la vitesse de décroissance du noyau de la chaleur, ce que n'aurait pas permis l'utilisation d'un critère de type Nash-Williams
16
Mercier, Lucas. "Grands graphes et grands arbres aléatoires : analyse du comportement asymptotique." Electronic Thesis or Diss., Université de Lorraine, 2016. http://www.theses.fr/2016LORR0028.
Full textAbstract:
Cette thèse est consacrée à l'étude du comportement asymptotique de grands graphes et arbres aléatoires. Le premier modèle étudié est un modèle de graphe aléatoire inhomogène introduit par Bo Söderberg. Un chapitre de ce manuscrit est consacré à l'étude asymptotique de la taille des composantes connexes à proximité de la fenêtre critique, en le reliant à la longueur des excursions d'un mouvement brownien avec dérive parabolique, étendant les résultats obtenus par Aldous. Le chapitre suivant est consacré à un processus de graphes aléatoires proposé par Itai Benjamini, défini ainsi : les arêtes sont ajoutées indépendamment, à taux fixe. Lorsqu'un sommet atteint le degré k, toutes les arêtes adjacentes à ce sommet sont immédiatement supprimées. Ce processus n'est pas croissant, ce qui empêche d'utiliser directement certaines approches usuelles. L'utilisation de limites locales permet de montrer la présence (resp. l'absence) d'une composante géante à certaines étapes dans le cas k>=5 (resp. k<=3). Dans le cas k=4, ces résultats permettent de caractériser la présence d'une composante géante en fonction du caractère surcritique ou non d'un processus de branchement associé. Dans le dernier chapitre est étudiée la hauteur d'un arbre de Lyndon associé à un mot de Lyndon choisi uniformément parmi les mots de Lyndon de longueur n, prouvant que cette hauteur est approximativement c ln n, avec c=5,092... la solution d'un problème d'optimisation. Afin d'obtenir ce résultat, nous couplons d'abord l'arbre de Lyndon à un arbre de Yule, que nous étudions ensuite à l'aide de techniques provenant des théories des marches branchantes et des grandes déviationsThis thesis is dedicated to the study of the asymptotic behavior of some large random graphs and trees. First is studied a random graph model introduced by Bo Söderberg in 2002. One chapter of this manuscript is devoted to the study of the asymptotic behavior of the size of the connected components near the critical window, linking it to the lengths of excursion of a Brownian motion with parabolic drift. The next chapter talks about a random graph process suggested by Itai Benjamini, defined as follows: edges are independently added at a fixe rate. Whenever a vertex reaches degree k, all adjacent edges are removed. This process is non-increasing, preventing the use of some commonly used methods. By using local limits, in the spirit of the PWIT, we were able to prove the presence (resp. absence) of a giant component at some stages of the process when k>=5 (resp. k<=3). In the case k=4, these results allows to link the presence (resp. absence) of a giant component to the supercriticality (resp. criticality or subcriticality) of an associated branching process. In the last chapter, the height of random Lyndon tree is studied, and is proven to be approximately c ln n, in which c=5.092... the solution of an optimization problem. To obtain this result, we couple the Lyndon tree with a Yule tree, then studied with the help of branching walks and large deviations
17
Foulger, Iain. "Quantum walks and quantum search on graphene lattices." Thesis, University of Nottingham, 2014. http://eprints.nottingham.ac.uk/27717/.
Full textAbstract:
This thesis details research I have carried out in the field of quantum walks, which are the quantum analogue of classical random walks. Quantum walks have been shown to offer a significant speed-up compared to classical random walks for certain tasks and for this reason there has been considerable interest in their use in algorithmic settings, as well as in experimental demonstrations of such phenomena. One of the most interesting developments in quantum walk research is their application to spatial searches, where one searches for a particular site of some network or lattice structure. There has been much work done on the creation of discrete- and continuous-time quantum walk search algorithms on various lattice types. However, it has remained an issue that continuous-time searches on two-dimensional lattices have required the inclusion of additional memory in order to be effective, memory which takes the form of extra internal degrees of freedom for the walker. In this work, we describe how the need for extra degrees of freedom can be negated by utilising a graphene lattice, demonstrating that a continuous-time quantum search in the experimentally relevant regime of two-dimensions is possible. This is achieved through alternative methods of marking a particular site to previous searches, creating a quantum search protocol at the Dirac point in graphene. We demonstrate that this search mechanism can also be adapted to allow state transfer across the lattice. These two processes offer new methods for channelling information across lattices between specific sites and supports the possibility of graphene devices which operate at a single-atom level. Recent experiments on microwave analogues of graphene that adapt these ideas, which we will detail, demonstrate the feasibility of realising the quantum search and transfer mechanisms on graphene.
18
Iriarte, Giraldo Benjamin. "Combinatorics of acyclic orientations of graphs : algebra, geometry and probability." Thesis, Massachusetts Institute of Technology, 2015. http://hdl.handle.net/1721.1/99325.
Full textAbstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2015.Cataloged from PDF version of thesis.
Includes bibliographical references (pages 96-99).
This thesis studies aspects of the set of acyclic orientations of a simple undirected graph. Acyclic orientations of a graph may be readily obtained from bijective labellings of its vertex-set with a totally ordered set, and they can be regarded as partially ordered sets. We will study this connection between acyclic orientations of a graph and the theory of linear extensions or topological sortings of a poset, from both the points of view of poset theory and enumerative combinatorics, and of the geometry of hyperplane arrangements and zonotopes. What can be said about the distribution of acyclic orientations obtained from a uniformly random selection of bijective labelling? What orientations are thence more probable? What can be said about the case of random graphs? These questions will begin to be answered during the first part of the thesis. Other types of labellings of the vertex-set, e.g. proper colorings, may be used to obtain acyclic orientations of a graph, as well. Motivated by our first results on bijective labellings, in the second part of the thesis, we will use eigenvectors of the Laplacian matrix of a graph, in particular, those corresponding to the largest eigenvalue, to label its vertex-set and to induce partial orientations of its edge-set. What information about the graph can be gathered from these partial orientations? Lastly, in the third part of the thesis, we will delve further into the structure of acyclic orientations of a graph by enhancing our understanding of the duality between the graphical zonotope and the graphical arrangement with the lens of Alexander duality. This will take us to non-crossing trees, which arguably vastly subsume the combinatorics of this geometric and algebraic duality. We will then combine all of these tools to obtain probabilistic results about the number of acyclic orientations of a random graph, and about the uniformly random choice of an acyclic orientation of a graph, among others.
by Benjamin Iriarte Giraldo.
Ph. D.
19
El, Hibaoui Abdelaaziz. "Analyse de quelques algorithmes probabilistes à délais aléatoires." Bordeaux 1, 2006. http://www.theses.fr/2006BOR13323.
Full textAbstract:
Dans la première partie de cette étude, nous proposons et analysons des algorithmes probabilistes d'élection uniforme dans des graphes de types arbres, les k-arbres et les polyominoïdes. Ces algorithmes utilisent des durées de vie aléatoires associées aux sommets découverts (sommets feuilles ou simpliciaux). Ces durées sont des variables aléatoires indépendantes et sont localement engendrées au fur et à mesure que les sommets sont découverts. Dans la seconde partie, nous analysons un algorithme probabiliste de synchronisation pour le problème de rendez-vous avec agendas dynamiques. L'objectif est de trouver un couplage maximal dans un graphe donné. Ensuite, nous proposons et étudions un modèle de diffusion à délai aléatoire pour la transmission d'un message dans un réseau. Finalement, dans la dernière partie, nous exposons les outils utilisés pour implémenter la simulation des algorithmes distribués.
20
Bertacchi, D., and Andreas Cap@esi ac at. "Random Walks on Diestel--Leader Graphs." ESI preprints, 2001. ftp://ftp.esi.ac.at/pub/Preprints/esi1004.ps.
Full text
21
Nyberg, Brodda Carl-Fredrik. "Deterministic and Random Pebbling of Graphs." Thesis, Uppsala universitet, Analys och sannolikhetsteori, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-325833.
Full text
22
Williams, Trevor K. "Combinatorial Games on Graphs." DigitalCommons@USU, 2017. https://digitalcommons.usu.edu/etd/6502.
Full textAbstract:
Combinatorial games are intriguing and have a tendency to engross students and lead them into a serious study of mathematics. The engaging nature of games is the basis for this thesis. Two combinatorial games along with some educational tools were developed in the pursuit of the solution of these games.
The game of Nim is at least centuries old, possibly originating in China, but noted in the 16th century in European countries. It consists of several stacks of tokens, and two players alternate taking one or more tokens from one of the stacks, and the player who cannot make a move loses. The formal and intense study of Nim culminated in the celebrated Sprague-Grundy Theorem, which is now one of the centerpieces in the theory of impartial combinatorial games. We study a variation on Nim, played on a graph. Graph Nim, for which the theory of Sprague-Grundy does not provide a clear strategy, was originally developed at the University of Colorado Denver. Graph Nim was first played on graphs of three vertices.
The winning strategy, and losing position, of three vertex Graph Nim has been discovered, but we will expand the game to four vertices and develop the winning strategies for four vertex Graph Nim.
Graph Theory is a markedly visual field of mathematics. It is extremely useful for graph theorists and students to visualize the graphs they are studying. There exists software to visualize and analyze graphs, such as SAGE, but it is often extremely difficult to learn how use such programs. The tools in GeoGebra make pretty graphs, but there is no automated way to make a graph or analyze a graph that has been built. Fortunately GeoGebra allows the use of JavaScript in the creation of buttons which allow us to build useful Graph Theory tools in GeoGebra. We will discuss two applets we have created that can be used to help students learn some of the basics of Graph Theory.
The game of thrones is a two-player impartial combinatorial game played on an oriented complete graph (or tournament) named after the popular fantasy book and TV series. The game of thrones relies on a special type of vertex called a king. A king is a vertex, k, in a tournament, T, which for all x in T either k beats x or there exists a vertex y such that k beats y and y beats x. Players take turns removing vertices from a given tournament until there is only one king left in the resulting tournament. The winning player is the one which makes the final move. We develop a winning position and classify those tournaments that are optimal for the first or second-moving player.
23
Pineau, Edouard. "Contributions to representation learning of multivariate time series and graphs." Electronic Thesis or Diss., Institut polytechnique de Paris, 2020. http://www.theses.fr/2020IPPAT037.
Full textAbstract:
Les algorithmes de machine learning sont construits pour apprendre, à partir de données, des modèles statistiques de décision ou de prédiction, sur un large panel de tâches. En général, les modèles appris sont des approximations d'un "vrai" modèle de décision, dont la pertinence dépend d'un équilibre entre la richesse du modèle appris, la complexité de la distribution des données et la complexité de la tâche à résoudre à partir des données. Cependant, il est souvent nécessaire d'adopter des hypothèses simplificatrices sur la donnée (e.g. séparabilité linéaire, indépendance des observations, etc.). Quand la distribution des donnée est complexe (e.g. grande dimension avec des interactions non-linéaires entre les variables observées), les hypothèses simplificatrices peuvent être contre-productives. Il est alors nécessaire de trouver une représentation alternatives des données avant d'apprendre le modèle de décision. L'objectif de la représentation des données est de séparer l'information pertinente du bruit, en particulier quand l'information est latente (i.e. cachée dans la donnée), pour aider le modèle statistique de décision. Jusqu'à récemment, beaucoup de représentations standards étaient construites à la main par des experts. Avec l'essor des techniques nouvelles de machine learning, et en particulier l'utilisation de réseaux de neurones, des techniques d'apprentissage de représentation ont surpassées les représentations manuelles dans de nombreux domaines. Dans cette thèse, nous nous sommes intéressés à l'apprentissage de représentation de séries temporelles multivariées (STM) et de graphes. STM et graphes sont des objets complexes qui ont des caractéristiques les rendant difficilement traitables par des algorithmes standards de machine learning. Par exemple, ils peuvent avoir des tailles variables et ont des alignements non-triviaux, qui empêchent l'utilisation de métriques standards pour les comparer entre eux. Il est alors nécessaire de trouver pour les échantillons observés (STM ou graphes) une représentation alternatives qui les rend comparables. Les contributions de ma thèses sont un ensemble d'analyses, d'approches pratiques et de résultats théoriques présentant des nouvelles manières d'apprendre une représentation de STM et de graphes. Deux méthodes de représentation de STM ont dédiées au suivi d'état caché de systèmes mécaniques. La première propose une représentation basée "model-based" appelée Sequence-to-graph (Seq2Graph). Seq2Graph se base sur l'hypothèse que les données observées ont été généré par un modèle causal simple, dont l'espace des paramètres sert d'espace de représentation. La second méthode propose une méthode générique de détection de tendances dans des séries temporelles, appelée Contrastive Trend Estimation (CTE), qui fait l'hypothèse que le vieillissement d'un système mécanique est monotone. Une preuve d'identifiabilité et une extension à des problèmes d'analyse de survie rendent cette approche puissante pour le suivi d'état de système mécaniques. Deux méthodes de représentation de graphes pour la classification sont aussi proposées. Une première propose de voir les graphes comme des séquences de nœuds et donc de les traiter avec un outil standard de représentation de séquences : un réseau de neurones récurrents. Une second méthode propose une analyse théorique et pratique du spectre du Laplacien pour la classification de graphesMachine learning (ML) algorithms are designed to learn models that have the ability to take decisions or make predictions from data, in a large panel of tasks. In general, the learned models are statistical approximations of the true/optimal unknown decision models. The efficiency of a learning algorithm depends on an equilibrium between model richness, complexity of the data distribution and complexity of the task to solve from data. Nevertheless, for computational convenience, the statistical decision models often adopt simplifying assumptions about the data (e.g. linear separability, independence of the observed variables, etc.). However, when data distribution is complex (e.g. high-dimensional with nonlinear interactions between observed variables), the simplifying assumptions can be counterproductive. In this situation, a solution is to feed the model with an alternative representation of the data. The objective of data representation is to separate the relevant information with respect to the task to solve from the noise, in particular if the relevant information is hidden (latent), in order to help the statistical model. Until recently and the rise of modern ML, many standard representations consisted in an expert-based handcrafted preprocessing of data. Recently, a branch of ML called deep learning (DL) completely shifted the paradigm. DL uses neural networks (NNs), a family of powerful parametric functions, as learning data representation pipelines. These recent advances outperformed most of the handcrafted data in many domains.In this thesis, we are interested in learning representations of multivariate time series (MTS) and graphs. MTS and graphs are particular objects that do not directly match standard requirements of ML algorithms. They can have variable size and non-trivial alignment, such that comparing two MTS or two graphs with standard metrics is generally not relevant. Hence, particular representations are required for their analysis using ML approaches. The contributions of this thesis consist of practical and theoretical results presenting new MTS and graphs representation learning frameworks.Two MTS representation learning frameworks are dedicated to the ageing detection of mechanical systems. First, we propose a model-based MTS representation learning framework called Sequence-to-graph (Seq2Graph). Seq2Graph assumes that the data we observe has been generated by a model whose graphical representation is a causality graph. It then represents, using an appropriate neural network, the sample on this graph. From this representation, when it is appropriate, we can find interesting information about the state of the studied mechanical system. Second, we propose a generic trend detection method called Contrastive Trend Estimation (CTE). CTE learns to classify pairs of samples with respect to the monotony of the trend between them. We show that using this method, under few assumptions, we identify the true state underlying the studied mechanical system, up-to monotone scalar transform.Two graph representation learning frameworks are dedicated to the classification of graphs. First, we propose to see graphs as sequences of nodes and create a framework based on recurrent neural networks to represent and classify them. Second, we analyze a simple baseline feature for graph classification: the Laplacian spectrum. We show that this feature matches minimal requirements to classify graphs when all the meaningful information is contained in the structure of the graphs
24
Lehéricy, Thomas. "Cycles séparants, isopérimétrie et modifications de distances dans les grandes cartes planaires aléatoires." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLS476/document.
Full textAbstract:
Les cartes planaires sont des graphes planaires dessinés sur la sphère et vus à déformation près. De nombreuses propriétés des cartes sont supposées universelles, dans le sens où elles ne dépendent pas des détails du modèle choisi. Nous commençons par établir une inégalité isopérimétrique dans la quadrangulation infinie du plan. Nous confirmons également une conjecture de Krikun portant sur la longueur des cycles les plus courts séparant la boule de rayon $r$ de l'infini. Dans un deuxième temps, nous nous intéressons à l'effet de modifications de distances sur la géométrie à grande échelle des quadrangulations uniformes, élargissant la classe d'universalité de la carte brownienne. Nous montrons également que la bijection de Tutte, entre quadrangulations et cartes planaires, est asymptotiquement une isométrie. Enfin, nous établissons une borne supérieure sur le temps de mélange de la marche aléatoire dans les cartes aléatoiresPlanar maps are planar graphs drawn on the sphere and seen up to deformation. Many properties of maps are conjectured to be universal, in the sense that they do not depend on the details of the model.We begin by establishing an isoperimetric inequality in the infinite quadrangulation of the plane. We also confirm a conjecture by Krikun concerning the length of the shortest cycles separating the ball of radius $r$ from infinity. We then consider the effect of modifications of distances on the large-scale geometry of uniform quadrangulations, extending the universality class of the Brownian map. We also show that the Tutte bijection, between quadrangulations and planar maps, is asymptotically an isometry. Finally, we establish an upper bound on the mixing time of the random walk in random maps
25
Bellalouna, Monia. "Problèmes d'optimisation combinatoires probabilistes." Phd thesis, Ecole Nationale des Ponts et Chaussées, 1993. http://pastel.archives-ouvertes.fr/pastel-00568759.
Full textAbstract:
L'étude du domaine récent que constituent les problèmes d'optimisation combinatoires probabilistes (POCPs) forme le sujet de cette thèse. Les POCPs sont des généralisations des problèmes d'optimisation combinatoires classiques dont les formulations contiennent explicitement des éléments probabilistes. Plusieurs motivations ont provoqué cette étude. Deux d'entre elles sont particulièrement importantes. La première correspond au désir de formuler et d'analyser des modèles qui sont plus appropriés pour des problèmes pratiques pour lesquels l'aléatoire est une source constante de préoccupations, les modèles de nature probabiliste sont plus particulièrement attractifs comme abstraction mathématique des systèmes réels. La seconde motivation est d'analyser la stabilité des solutions optimales des problèmes déterministes lorsque les exemplaires sont perturbés : les perturbations sont simulées par la présence ou l'absence de sous-ensembles des données. Notre étude s'appuie sur certains de ces problèmes et en particulier : problème du voyageur de commerce; problème d'ordonnancement des travaux probabiliste et le problème du bin-packing probabiliste. Les questions soulevées et les résultats obtenus sont dans les domaines suivants : complexités des problèmes et analyse d'heuristiques pour les POCPs ; analyse du comportement asymptotique des problèmes lorsque les exemplaires correspondent à des problèmes de grandes tailles ; dégager une méthodologie générale d'étude de la stabilité des solutions des problèmes d'optimisation combinatoires classiques.
26
De, Loynes Basile. "Graphes et marches al��atoires." Phd thesis, Universit�� Rennes 1, 2012. http://tel.archives-ouvertes.fr/tel-00726504.
Full textAbstract:
L'��tude des marches al ��atoires fait appara��tre des connexions entre leurs propri��t��s alg ebriques, g ��om ��triques ou encore combinatoires et leurs propri��t��s stochastiques. Le premier exemple de telles connexions est donn �� par le th ��or��me de P olya concernant les marches al��atoires aux plus proches voisins sur le groupe Z^N. Si les marches al��atoires sur les groupes - ou sur des espaces homog��nes - fournissent beaucoup d'exemples, il serait appr��ciable d'obtenir de tels r��sultats de rigidit �� sur des structures alg��briques plus faibles telles celles de semi-groupo��de ou de groupo��de. Dans cette th��se il est consid��r�� un exemple de semi-groupo��de et un exemple de groupo��de, tous les deux sont d��fi nis �� partir de sous-graphes contraints du graphe de Cayley d'un groupe - le premier graphe est dirig�� alors que le second ne l'est pas. Pour ce premier exemple, on pr��cise un r��sultat de Campanino et Petritis - ils ont montr�� que la marche al��atoire simple etait transiente pour cet exemple de graphe dirig�� - en d ��terminant la fronti��re de Martin associ ��e �� cette marche et ��tablissant sa trivialit��. Dans le second exemple apparaissant dans ce manuscrit, on consid��re des pavages quasi-p��riodiques de l'espace euclidien obtenus �� l'aide de la m��thode de coupe et projection. Nous consid��rons la marche al��atoire simple le long des ar��tes des polytopes constituant le pavage, et nous r epondons a la question du type de celle-ci, c'est-��-dire nous d��terminons si elle est r��currente ou transiente. Nous montrons ce r esultat en etablissant des in egalit es isop erim etriques. Cette strat egie permet d'obtenir des estim��es de la vitesse de d ecroissance du noyau de la chaleur, ce que n'aurait pas permis l'utilisation d'un crit��re de type Nash-Williams.
27
Weld, Christopher. "Computational Graphics and Statistical Analysis: Mixed Type Random Variables, Confidence Regions, and Golden Quantile Rank Sets." W&M ScholarWorks, 2019. https://scholarworks.wm.edu/etd/1563898977.
Full textAbstract:
This dissertation has three principle areas of research: mixed type random variables, confidence regions, and golden quantile rank sets. While each offers a specific focus, some common themes persist; broadly stated, there are three. First, computational graphics play a critical role. Second, software development facilitates implementation and accessibility. Third, statistical analysis---often attributable to the aforementioned automation---provides valuable insights and applications. Each of the principle research areas are briefly summarized next. Mixed type random variables are a hybrid of continuous and discrete random variables, having components of both continuous probability density and discrete probability mass. This dissertation illustrates the challenges inherent in plotting mixed type distributions, and introduces an algorithm that addresses those issues. It considers sums and products of mixed type random variables, and supports its conclusions using Monte Carlo simulation experiments. Lastly, it introduces MixedAPPL, a computer algebra system software package designed for manipulating mixed type random variables. Confidence regions are a multi-dimensional version of a confidence interval. They are helpful to visualize and quantify uncertainty surrounding a point estimate. We begin by developing efficient plot algorithms for two-dimensional confidence regions. This research focuses specifically on likelihood-ratio based confidence regions for two-parameter univariate probability models, although the plot techniques are transferable to any two-dimensional setting. The R package 'conf' is introduced, which automates these confidence region plot algorithms for complete and right-censored data sets. Among its benefits, 'conf' provides access to Monte Carlo simulation experiments for confidence region coverage to an extent not possible previously. The corresponding coverage analysis results include reference tables for the Weibull, normal, and log-logistic distributions. These reference tables yield confidence region plots with exact coverage. The final topic is the introduction and analysis of a golden quantile rank set (GQRS). The term quantile rank set is used here to denote the population cumulative distribution function values corresponding to a sample. A GQRS can be thought of as "perfectly" representative of their population distribution because samples corresponding to a GQRS result in an estimator(s) matching the associated true population parameter(s). This unique characteristic is not applicable for all estimators and/or distributions, but when present, provides valuable insights and applications. Specifically, applications include an alternative (and at times computationally superior) method for parameter estimation and an exact actual coverage methodology for confidence regions (at times in which currently only estimates exist). Distributions with a GQRS associated with maximum likelihood estimation include the normal, exponential, Weibull, log logistic, and one-parameter exponential power distributions.
28
Lindström, Alfred Minh. "Cutting and Destroying Graphs using k-cuts." Thesis, Uppsala universitet, Analys och sannolikhetsteori, 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-395663.
Full text
29
Roques, Olivier. "Tirages économes de structures combinatoires." Bordeaux 1, 2001. http://www.theses.fr/2001BOR12402.
Full textAbstract:
Les travaux menés dans cette thèse ont pour but de concevoir des algorithmes efficaces en temps et en mémoire pour engendrer des objets combinatoires de grandes tailles. Notre approche consiste à utiliser une méthode, dite méthode à rejet, qui nous permet d'engendrer des structures combinatoires sans calculer ni manipuler les nombres qui les énumèrent. Nous avons ainsi engendré des arbres à plusieurs millions de nœuds ainsi que différentes familles de chemins du plan à plusieurs millions de pas, en quelques secondes sur un ordinateur de bureau. Nous faisons une analyse détaillée des algorithmes proposés et nous montrons que la complexité moyenne en temps et en espace est linéaire en la taille objets.
30
Mosbah, Mohamed. "Constructions d'algorithmes pour les graphes structurés par des méthodes algébriques et logiques." Bordeaux 1, 1992. http://www.theses.fr/1992BOR10511.
Full textAbstract:
Ce travail definit, au moyen de la logique monadique du second-ordre et d'homomorphismes de semi-anneaux, des fonctions calculables efficacement, sur les graphes structures en arbres, de largeur arborescente bornee. Nous obtenons, ainsi, des algorithmes polynomiaux et meme lineaires pour plusieurs problemes, dont beaucoup sont np-complets, lorsqu'ils sont restreints aux graphes structures en arbres, de largeur bornee. Cette approche est etendue a d'autres fonctions telles que le diametre, et est appliquee aux grammaires de graphes probabilistes. Nous presentons, en particulier, des methodes pour calculer la valeur moyenne d'une fonction, de la classe consideree, sur une grammaire de graphes probabiliste
31
Baki, Bassam. "Planification et ordonnancement probabilistes sous contraintes temporelles." Phd thesis, Université de Caen, 2006. http://tel.archives-ouvertes.fr/tel-00127880.
Full textAbstract:
Cette thèse est consacrée au problème de la planification et de l'ordonnancement des tâches sous contraintes temporelles et incertitude. Les contraintes temporelles que nous traitons sont de deux types : qualitatives et quantitatives. L'incertitude sur la durée des tâches se traduit par une distribution de probabilités sur un ensemble fini.Les tâches et les contraintes sont représentées à l'aide d'un graphe ET/OU et les durées des tâches sont pondérées par des probabilités d'exécution. Celles-ci expriment une incertitude sur la connaissance exacte des durées d'exécution des tâches qui ne seront réellement connues que lors de l'exécution effective. Ainsi, une tâche s'exécute durant l'une de ses durées d'exécution possibles avec la probabilité associée à celle-ci. Étant donné ce graphe, notre objectif est de déterminer un plan de tâches qui satisfait toutes les contraintes et qui répond aux critères de choix exigés par l'utilisateur en terme de temps, de coût et de probabilité. L'application de ce plan doit garantir le monde de façon que le but soit atteint tout en satisfaisant les contraintes du domaine.
Nous avons appliqué notre méthode de planification à un cas pratique relativement complexe qui concerne la planification d'un ensemble d'agents travaillant ensemble dans un lieu afin d'atteindre un but donné tout en respectant les délais et les contraintes du domaine (temps, coût, probabilité, disponibilité, spécialité,...).
32
Bosi, Gianluca <1991>. "Simple random walks on some partially directed planar graphs." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2019. http://amsdottorato.unibo.it/8914/1/bosi_gianluca_tesi.pdf.
Full textAbstract:
In this thesis we analyze the recurrence behavior of simple random walks on some classes of directed planar graphs. Our first model is a version of the honeycomb lattice, where the horizontal edges are randomly oriented according to families of random variables: depending on their distribution, we prove a.s. transience in some cases, and a.s. recurrence in other ones. Our results extend those obtained by Campanino and Petritis (’03 and ’14) for partially oriented square grid lattices.
Furthermore, we consider two directed square grid lattices on which, because of the direction imposed by the oriented edges, the simple random walk is bound to revolve clockwise: we prove recurrence for one of the graphs, solving a conjecture of Menshikov et al. (’17), and we give a new proof of transience for the other one.
33
Pirot, Francois. "Coloration de graphes épars." Electronic Thesis or Diss., Université de Lorraine, 2019. http://www.theses.fr/2019LORR0153.
Full textAbstract:
Cette thèse a pour thème la coloration de diverses classes de graphes épars. Shearer montra en 1983 [She83] que le ratio d'indépendance des graphes sans triangle de degré maximal d est au moins (1-o(1))ln d/d, et 13 ans plus tard Johansson [Joh96] démontra que le nombre chromatique de ces graphes est au plus O(d/ln d) quand d tend vers l'infini. Ce dernier résultat fut récemment amélioré par Molloy [Mol19], qui montra que la borne (1+o(1))d/ln d est valide quand d tend vers l'infini.Tandis que le résultat de Molloy s'exprime à l'aide d'un paramètre global, le degré maximal du graphe, nous montrons qu'il est possible de l'étendre à la coloration locale. Il s'agit de la coloration par liste, où la taille de la liste associée à chaque sommet ne dépend que de son degré. Avec une méthode différente se basant sur les propriétés de la distribution hard-core sur les ensembles indépendants d'un graphe, nous obtenons un résultat similaire pour la coloration fractionnaire locale, avec des hypothèses plus faibles. Nous démontrons également un résultat concernant la coloration fractionnaire locale des graphes où chaque sommet est contenu dans un nombre borné de triangles, et une borne principalement optimale sur le taux d'occupation — la taille moyenne des ensembles indépendants — de ces graphes. Nous considérons également les graphes de maille 7, et prouvons des résultats similaires qui améliorent les bornes précédemment connues quand le degré maximal du graphe est au plus 10^7. Finalement, pour les graphes d-réguliers où d vaut 3, 4, ou 5, de maille g variant entre 6 et 12, nous démontrons de nouvelles bornes inférieures sur le ratio d'indépendance.Le Chapitre 2 est dédié à la coloration à distance t d'un graphe, qui généralise la notion de coloration forte des arêtes. Nous cherchons à étendre le théorème de Johansson à la coloration à distance t, par l'exclusion de certains cycles. Le résultat de Johansson s'obtient par exclusion des triangles, ou des cycles de taille k pour n'importe quelle valeur de k. Nous montrons que l'exclusion des cycles de taille 2k, pour n'importe quel k>t, a un effet similaire sur le nombre chromatique à distance t, et sur l'indice chromatique à distance t+1. En outre, quand t est impair, une conclusion similaire peut se faire pour le nombre chromatique à distance t par l'exclusion des cycles de d'une taille impaire fixée valant au moins 3t. Nous étudions l'optimalité de ces résultats à l'aide de constructions de nature combinatoire, algébrique, et probabiliste.Dans le Chapitre 3, nous nous intéressons à la densité bipartie induite des graphes sans triangle, un paramètre relaxant celui de la coloration fractionnaire. Motivés par une conjecture de Esperet, Kang, et Thomassé [EKT19], qui prétend que la densité bipartie induite de graphes sans triangle de degré moyen d est au moins de l'ordre de ln d, nous démontrons cette conjecture quand d est suffisamment grand en termes du nombre de sommets n, à savoir d est au moins de l'ordre de (n ln n)^(1/2). Ce résultat ne pourrait être amélioré que par une valeur de l'ordre de ln n, ce que nous montrons à l'aide d'une construction reposant sur le processus sans triangle. Nos travaux se ramènent à un problème intéressant, celui de déterminer le nombre chromatique fractionnaire maximal d'un graphe épars à n sommets. Nous prouvons des bornes supérieures non triviales pour les graphes sans triangle, et pour les graphes dont chaque sommet appartient à un nombre borné de triangles.Cette thèse est reliée aux nombres de Ramsey. À ce jour, le meilleur encadrement connu sur R(3,t) nous est donné par le résultat de Shearer, et par une analyse récente du processus sans triangle [BoKe13+,FGM13+], ce qui donne(1-o(1)) t²/(4 ln t) < R(3,t) < (1+o(1)) t²/ln t. (1)Beaucoup de nos résultats ne pourraient être améliorés à moins d'améliorer par la même occasion (1), ce qui constituerait une révolution dans la théorie de Ramsey quantitativeThis thesis focuses on generalisations of the colouring problem in various classes of sparse graphs.Triangle-free graphs of maximum degree d are known to have independence ratio at least (1-o(1))ln d/d by a result of Shearer [She83], and chromatic number at most O(d/ln d) by a result of Johansson [Joh96], as d grows to infinity. This was recently improved by Molloy, who showed that the chromatic number of triangle-free graphs of maximum degree d is at most (1+o(1))d/ln d as d grows to infinity.While Molloy's result is expressed with a global parameter, the maximum degree of the graph, we first show that it is possible to extend it to local colourings. Those are list colourings where the size of the list associated to a given vertex depends only on the degree of that vertex. With a different method relying on the properties of the hard-core distribution on the independent sets of a graph, we obtain a similar result for local fractional colourings, with weaker assumptions. We also provide an analogous result concerning local fractional colourings of graphs where each vertex is contained in a bounded number of triangles, and a sharp bound for the occupancy fraction — the average size of an independent set — of those graphs. In another direction, we also consider graphs of girth 7, and prove related results which improve on the previously known bounds when the maximum degree does not exceed 10^7. Finally, for d-regular graphs with d in the set {3,4,5}, of girth g varying between 6 and 12, we provide new lower bounds on the independence ratio.The second chapter is dedicated to distance colourings of graphs, a generalisation of strong edge-colourings. Extending the theme of the first chapter, we investigate minimal sparsity conditions in order to obtain Johansson-like results for distance colourings. While Johansson's result follows from the exclusion of triangles — or actually of cycles of any fixed length — we show that excluding cycles of length 2k, provided that k>t, has a similar effect for the distance-t chromatic number and the distance-(t+1) chromatic index. When t is odd, the same holds for the distance-t chromatic number by excluding cycles of fixed odd length at least 3t. We investigate the asymptotic sharpness of our results with constructions of combinatorial, algebraic, and probabilistic natures.In the third chapter, we are interested in the bipartite induced density of triangle-free graphs, a parameter which conceptually lies between the independence ratio and the fractional chromatic number. Motivated by a conjecture of Esperet, Kang, and Thomassé [EKT19], which states that the bipartite induced density of a triangle-free graph of average degree d should be at least of the order of ln d, we prove that the conjecture holds for when d is large enough in terms of the number of vertices n, namely d is at least of the order of (n ln n)^(1/2). Our result is shown to be sharp up to term of the order of ln n, with a construction relying on the triangle-free process. Our work on the bipartite induced density raises an interesting related problem, which aims at determining the maximum possible fractional chromatic number of sparse graph where the only known parameter is the number of vertices. We prove non trivial upper bounds for triangle-free graphs, and graphs where each vertex belongs to a bounded number of triangles.All the content of this thesis is a collection of specialisations of the off-diagonal Ramsey theory. To this date, the best-known bounds on the off-diagonal Ramsey number R(3,t) come from the aforementioned result of Shearer for the upper-bound, and a recent analysis of the triangle-free process [BoKe13+,FGM13+] for the lower bound, giving(1-o(1)) t²/(4 ln t) < R(3,t) < (1+o(1)) t²/ln t. (1)Many of our results are best possible barring an improvement of (1), which would be a breakthrough in off-diagonal Ramsey theory
34
Male, Camille. "Forte et fausse libertés asymptotiques de grandes matrices aléatoires." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2011. http://tel.archives-ouvertes.fr/tel-00673551.
Full textAbstract:
Cette thèse s'inscrit dans la théorie des matrices aléatoires, à l'intersection avec la théorie des probabilités libres et des algèbres d'opérateurs. Elle s'insère dans une démarche générale qui a fait ses preuves ces dernières décennies : importer les techniques et les concepts de la théorie des probabilités non commutatives pour l'étude du spectre de grandes matrices aléatoires. On s'intéresse ici à des généralisations du théorème de liberté asymptotique de Voiculescu. Dans les Chapitres 1 et 2, nous montrons des résultats de liberté asymptotique forte pour des matrices gaussiennes, unitaires aléatoires et déterministes. Dans les Chapitres 3 et 4, nous introduisons la notion de fausse liberté asymptotique pour des matrices déterministes et certaines matrices hermitiennes à entrées sous diagonales indépendantes, interpolant les modèles de matrices de Wigner et de Lévy.
35
De, Loynes Basile. "Graphes et marches aléatoires." Phd thesis, Université Rennes 1, 2012. http://tel.archives-ouvertes.fr/tel-00726483.
Full textAbstract:
L'étude des marches aléatoires fait apparaître des connexions entre leurs propriétés algébriques, géométriques ou encore combinatoires et leurs propriétés stochastiques. Si les marches aléatoires sur les groupes - ou sur des espaces homogènes - fournissent beaucoup d'exemples, il serait appréciable d'obtenir de tels résultats de rigidité sur des structures algébriques plus faibles telles celles de semi-groupoide ou de groupoide. Dans cette thèse il est considéré un exemple de semi-groupoide et un exemple de groupoide, tous les deux sont définis a partir de sous-graphes contraints du graphe de Cayley d'un groupe - le premier graphe est dirige alors que le second ne l'est pas. Pour ce premier exemple, on précise un résultat de Campanino et Petritis (ils ont montre que la marche aléatoire simple était transiente pour cet exemple de graphe dirigé) en déterminant la frontière de Martin associée à cette marche et établissant sa trivialité Dans le second exemple apparaissant dans ce manuscrit, on considère des pavages quasi-périodiques de l'espace euclidien obtenus à l'aide de la méthode de coupe et projection. Nous considérons la marche aléatoire simple le long des arêtes des polytopes constituant le pavage, et nous répondons a la question du type de celle-ci, c'est-à-dire nous déterminons si elle est récurrente ou transiente. Nous montrons ce résultat en établissant des inégalités isopérimétriques Cette stratégie permet d'obtenir des estimées de la vitesse de décroissance du noyau de la chaleur, ce que n'aurait pas permis l'utilisation d'un critère de type Nash-Williams.
36
Jin, Xiong. "Construction et analyse multifractale de fonctions aléatoires et de leurs graphes." Phd thesis, Université Paris Sud - Paris XI, 2010. http://tel.archives-ouvertes.fr/tel-00841501.
Full textAbstract:
Cette thèse est consacrée à la construction et l'analyse multifractale de fonctions aléatoires et de leurs graphes. La construction de ces objets se fait dans le cadre de la théorie des T-martingales de Kahane, et plus spécifiquement des [0, 1]-martingales. Cette théorie est fréquemment utilisée pour construire des martingales à valeurs dans les mesures de Borel positives dont la limite soit presque sûrement singulière par rapport à la mesure de Lebesgue. Ceci se fait en perturbant cette dernière à l'aide d'une suite de densités aléatoires qui sont des martingales positives d'espérance 1. Ici, nous autorisons ces martingales à prendre des valeurs complexes, et plutôt que des martingales à valeurs dans les mesures, nous considérons des martingales à valeurs dans les fonctions continues à valeurs complexes, puis la question de leur convergence uniforme presque sûre. Nous obtenons une condition suffisante de convergence pour les éléments d'une large classe de [0, 1]-martingales complexes. Les limites non dégénérées sont toutes candidates à être des fonctions multifractales. L'étude de leur nature multifractale révèle de nouvelles diffiultés. Nous la menons de façon complète dans le cas des "cascades b-adiques indépendantes" complexes. Ceci conduit à de nouveaux phénomènes. En particulier, nous construisons des fonctions continues statistiquement autosimilaires dont le spectre de singularité est croissant et entièrement supporté par l'intervalle [0;\infty]. Nous considérons également de nouveaux spectres de singularité associés au graphe, à l'image, ainsi qu'aux ensembles de niveau d'une fonction multifractale f donnée. Ces spectres s'obtiennent de la façon suivante. Soit Eh l'ensemble iso-Hölder de f associé à l'exposant h. Soit h le sous-ensemble du graphe de f obtenu en y relevant Eh. Pour tout h, on cherche la dimension de Hausdorff de h, celle de f(Eh), et celle des ensembles du type h \ Ly, où Ly est l'ensemble de niveau y de f. Pour les cascades b-adiques indépendantes non conservatives à valeurs réelles, nous obtenons presque sûrement les spectres associés au graphe et à l'image, et pour les spectres associés aux ensembles de niveau, nous obtenons un résultat en regardant des lignes de niveau dans "Lebesgue presque toute direction". Enfin, nous considérons les mêmes questions que précédemment pour une autre classe de foncions aléatoires multifractales obtenues comme séries d'ondelettes pondérées par des mesures de Gibbs. Nous obtenons presque sûrement les spectres associés au graphe et à l'image.
37
Wang, Xiaomin. "Décider du type de distribution de degré d'un graphe (réseau) à partir des mesures traceroute-like." Paris 6, 2011. http://www.theses.fr/2011PA066608.
Full textAbstract:
La distribution des degrés de la topologie d'Internet est considéré comme l'un de ses principales propriétés. Cependant, on ne connaît une estimation biaisée par une procédure de mesure. Cette mesure comme la première approximation est modélisé par un arbre de BFS (parcours en largeur). Nous explorons ici, notre capacité à inférer le type (soit Poisson soit la loi de puissance) de la distribution des degrés d'une telle connaissance limitée. Nous les procédures de conception qui estiment la distribution des degrés d'un graphe à partir d'un ou plusieurs BFS, et de montrer expérimentalement (sur les graphes du modèle et les graphes du monde réel) que notre méthodologie réussit à distinguer Poisson et la loi de puissance et dans certains cas nous peuvons également estimer le nombre de liens. De plus, nous établissons une méthode, qui est une urne décroissante, pour analyser la procédure de la file d'attente. Nous analysons le profil de l'arbre BFS d'un graphe aléatoire avec une distribution des degrés donnée. Le nombre de nœuds et le nombre de liens invisibles à chaque niveau de l'arbre BFS sont deux principaux résultats que nous obtenons. Grâce à ces informations, nous proposons deux autres méthodologies pour décider du type plus précisement. The degree distribution of the Internet topology is considered as one of its main properties. However, it is only known through a measurement procedure which gives a biased estimate. This measurement may in first approximation be modeled by a BFS (Breadth-First Search) tree. We explore here our ability to infer the type (Poisson or power-law) of the degree distribution from such a limited knowledge. We design procedures which estimate the degree distribution of a graph from a BFS or multi-BFS trees, and show experimentally (on models and real-world data) that our approaches succeed in making the difference between Poisson and power-law degree distribution and in some cases can also estimate the number of links. In addition, we establish a method, which is a diminishing urn, to analyze the procedure of the queue. We analyze the profile of the BFS tree from a random graph with a given degree distribution. The expected number of nodes and the expected number of invisible links at each level of BFS tree are two main results that we obtain. Using these informations, we propose two new methodologies to decide on the type of the underlying graph.
38
Rousselle, Arnaud. "Marches au hasard sur des graphes géométriques aléatoires engendrés par des processus ponctuels." Rouen, 2014. http://www.theses.fr/2014ROUES038.
Full textAbstract:
Les marches aléatoires sur des graphes aléatoires plongés dans Rd apparaissent naturellement dans de nombreux problèmes issus de la mécanique statistique tels que la description de flux, de diffusions de molécules ou de chaleur dans des milieux aléatoires et irréguliers. L’idée générale est d’étendre des résultats connus sur la grille Zd ou des perturbations aléatoires de celle-ci à des graphes engendrés par des processus ponctuels dans Rd. Dans cette thèse, on considère des marches au plus proche voisin sur des graphes dépendant de la géométrie d’un ensemble aléatoire et infini de points. Plus précisément, étant donnée une réalisation d’un processus ponctuel simple et stationnaire dans Rd, un graphe G, connexe, infini et localement fini, est construit. Ce graphe est ensuite muni éventuellement d’une fonction de conductance C, c’est-à-dire une fonction strictement positive définie sur son ensemble d’arêtes. Les exemples de graphes géométriques étudiés dans ce manuscrit sont la triangulation de Delaunay, le graphe de Gabriel, les creek-crossing graphs et le squelette de la mosaïque de Voronoï engendrés par le processus ponctuel. On étudie les propriétés la marche simple et la marche associée à la conductance C sur de tels graphes. Les principaux résultats portent sur la caractérisation de la récurrence ou de la transience presque sûre des marches aléatoires et sur la description de leurs limites diffusives. On montre que, sous des hypothèses convenables sur le processus ponctuel sous-jacent et la fonction de conductance, les marches aléatoires sur la triangulation de Delaunay, le graphe de Gabriel et le squelette de la mosaïque de Voronoï engendrés par presque toute réalisation de ce processus ponctuel sont récurrentes si d = 2 et transitoires si d ≥ 3. On établit aussi un principe d’invariance annealed (ou en moyenne) pour les marches simples partant de l’origine sur la triangulation de Delaunay et le graphe de Gabriel engendrés par les mesures de Palm de certains processus ponctuels ainsi qu’un principe d’invariance quenched (ou presque sûr) pour les marches simples sur des triangulations de Delaunay engendrées par des processus ponctuels. Cette thèse exploite à la fois des outils de géométrie aléatoire (processus ponctuels, mesures de Palm, mosaïques et graphes aléatoires. . . ) et de la théorie des marches aléatoires (liens avec les réseaux électriques, l’environnement vu par la particule)Random walks on random graphs embedded in Rd appear naturally in problems arising from statistical mechanics such that the description of flows, molecules or heat diffusions in random and irregular environments. The general idea is to extend known results for random walks on Zd or on random perturbations of the grid to results for random walks on graphs generated by point processes in Rd. In this thesis, we consider nearest neighbor random walks on graphs depending on the geometry of a random infinite locally finite set of points. More precisely, given a realisation of a simple stationary point process in Rd, a connected infinite and locally finite graph G is constructed. This graph is then possibly equipped with a conductance function C, that is a positive function defined on its edge set. Examples of graphs studied in this manuscript are the Delaunay triangulation, the Gabriel graph, the creek-crossing graphs and the skeleton of the Voronoi tiling generated by the point process. We study properties of the simple random walk or of a random walk associated with the conductance C on such graphs. The main results concern the characterisation of the recurrence or transience of the random walks and the description of their diffusive scaling limits. Under suitable assumptions on the underlying point process and the conductance function, we show that the random walks on the Delaunay triangulation, the Gabriel graph and the skeleton of the Voronoi tiling generated by almost every realisation of the point process are recurrent if d = 2 and transient if d ≥ 3. We state an annealed invariance principle for simple random walks starting from the origin on the Delaunay triangulation, the Gabriel graph and the creek-crossing graphs generated by Palm measures of suitable point processes. Finally, we show a quenched invariance principle for simple random walks on random Delaunay triangulations. This thesis uses tools from both stochastic geometry (point processes, Palm measures, random graphs. . . ) and the theory of random walks (links with electrical networks theory, the environment seen from the particle,. . . )
39
Gillet, Florent. "Etude d'algorithmes stochastiques et arbres." Nancy 1, 2003. http://www.theses.fr/2003NAN10191.
Full textAbstract:
Cette thèse est consacrée à l'analyse de plusieurs problèmes issus de l'informatique et de la combinatoire. Dans une première partie, nous étudions les effets que produisent des erreurs de comparaison lorsque l'on traite une liste avec l'algorithme de tri Quicksort. Lorsque une comparaison est erronée avec une probabilité p, on montre que le nombre d'inversions de la liste restituée par Quicksort est de l'ordre de grandeur de n2p. Dans la deuxième partie, nous démontrons la convergence d'un processus appelé watermelon vers un processus défini par des équations différentielles stochastiques. Nous donnons également quelques propriétés de ce processus limite : la loi de sa norme, quelques moments, un lien avec les valeurs propres de matrices aléatoires,. . . La dernière partie est consacrée à l'étude du comportement asymptotique des lois locales des arbres simples. Nous montrons que la loi des arbres simples de taille n converge vers une mesure de probabilité que nous décrivonsThis thesis deals with the probabilistic analysis of some problems comming from computer science and combinatoric. In a first part, we study the effects of errors of comparison when we sort an input list with the sorting algorithm Quicksort. When a comparison can err with probability p, we show that the number of inversions in the output list of Quicksort has the order of magnitude n2p. In the second part, we prove the convergence of a process known as watermelon to a process defined by stochastic differential equations. We also give some properties of this limit process: the law of his norm, some moments, a link with the eigen values of random matrices,. . . The last part deals with the study of the asymptotic behaviour of the local laws of simple trees. We show that the law of simple trees with n vertices converges to a probablity measure we describe
40
Bailey, Sean. "To Dot Product Graphs and Beyond." DigitalCommons@USU, 2016. https://digitalcommons.usu.edu/etd/5029.
Full textAbstract:
We will introduce three new classes of graphs; namely bipartite dot product graphs, probe dot product graphs, and combinatorial orthogonal graphs. All of these representations were inspired by a vector representation known as a dot product representation.
Given a bipartite graph G = (X, Y, E), the bipartite dot product representation of G is a function ƒ : X ∪ Y → Rk and a positive threshold t such that for any κ ∈ Χ and γ ∈ Υ , κγ ∈ ε if and only if f(κ) · f(γ) ≥ t. The minimum k such that a bipartite dot product representation exists for G is the bipartite dot product dimension of G, denoted bdp(G). We will show that such representations exist for all bipartite graphs as well as give an upper bound for the bipartite dot product dimension of any graph. We will also characterize the bipartite graphs of bipartite dot product dimension 1 by their forbidden subgraphs.
An undirected graph G = (V, E) is a probe C graph if its vertex set can be parti-tioned into two sets, N (nonprobes) and P (probes) where N is independent and there exists E' ⊆ N × N such that G' = (V, E ∪ E) is a C graph. In this dissertation we introduce probe k-dot product graphs and characterize (at least partially) probe 1-dot product graphs in terms of forbidden subgraphs and certain 2-SAT formulas. These characterizations are given for the very different circumstances: when the partition into probes and nonprobes is given, and when the partition is not given.
Vectors κ = (κ1, κ2, . . . , κn)T and γ = (γ1, γ2, . . . , γn)T are combinatorially orthogonal if |{i : κiγi = 0}| ≠ 1. An undirected graph G = (V, E) is a combinatorial orthogonal graph if there exists ƒ : V → Rn for some n ∈ Ν such that for any u, υ &Isin; V , uv ∉ E iff ƒ(u) and ƒ(v) are combinatorially orthogonal. These representations can also be limited to a mapping g : V → {0, 1}n such that for any u,v ∈ V , uv ∉ E iff g(u) · g(v) = 1. We will show that every graph has a combinatorial orthogonal representation. We will also state the minimum dimension necessary to generate such a representation for specific classes of graphs.
41
McKinnon, Melissa Taylor. "Probability and Statistics for Third through Fifth Grade Classrooms." Digital Commons @ East Tennessee State University, 2007. https://dc.etsu.edu/etd/2118.
Full textAbstract:
This document contains a variety of lesson plans that can be readily used by a teacher of intermediate students. This thesis contains two units in Probability and one unit in Statistics. Any educator can supplement this document with any curriculum to teach lessons from vocabulary to concept.
42
Pirot, Francois. "Coloration de graphes épars." Thesis, Université de Lorraine, 2019. http://www.theses.fr/2019LORR0153/document.
Full textAbstract:
Cette thèse a pour thème la coloration de diverses classes de graphes épars. Shearer montra en 1983 [She83] que le ratio d'indépendance des graphes sans triangle de degré maximal d est au moins (1-o(1))ln d/d, et 13 ans plus tard Johansson [Joh96] démontra que le nombre chromatique de ces graphes est au plus O(d/ln d) quand d tend vers l'infini. Ce dernier résultat fut récemment amélioré par Molloy [Mol19], qui montra que la borne (1+o(1))d/ln d est valide quand d tend vers l'infini.Tandis que le résultat de Molloy s'exprime à l'aide d'un paramètre global, le degré maximal du graphe, nous montrons qu'il est possible de l'étendre à la coloration locale. Il s'agit de la coloration par liste, où la taille de la liste associée à chaque sommet ne dépend que de son degré. Avec une méthode différente se basant sur les propriétés de la distribution hard-core sur les ensembles indépendants d'un graphe, nous obtenons un résultat similaire pour la coloration fractionnaire locale, avec des hypothèses plus faibles. Nous démontrons également un résultat concernant la coloration fractionnaire locale des graphes où chaque sommet est contenu dans un nombre borné de triangles, et une borne principalement optimale sur le taux d'occupation — la taille moyenne des ensembles indépendants — de ces graphes. Nous considérons également les graphes de maille 7, et prouvons des résultats similaires qui améliorent les bornes précédemment connues quand le degré maximal du graphe est au plus 10^7. Finalement, pour les graphes d-réguliers où d vaut 3, 4, ou 5, de maille g variant entre 6 et 12, nous démontrons de nouvelles bornes inférieures sur le ratio d'indépendance.Le Chapitre 2 est dédié à la coloration à distance t d'un graphe, qui généralise la notion de coloration forte des arêtes. Nous cherchons à étendre le théorème de Johansson à la coloration à distance t, par l'exclusion de certains cycles. Le résultat de Johansson s'obtient par exclusion des triangles, ou des cycles de taille k pour n'importe quelle valeur de k. Nous montrons que l'exclusion des cycles de taille 2k, pour n'importe quel k>t, a un effet similaire sur le nombre chromatique à distance t, et sur l'indice chromatique à distance t+1. En outre, quand t est impair, une conclusion similaire peut se faire pour le nombre chromatique à distance t par l'exclusion des cycles de d'une taille impaire fixée valant au moins 3t. Nous étudions l'optimalité de ces résultats à l'aide de constructions de nature combinatoire, algébrique, et probabiliste.Dans le Chapitre 3, nous nous intéressons à la densité bipartie induite des graphes sans triangle, un paramètre relaxant celui de la coloration fractionnaire. Motivés par une conjecture de Esperet, Kang, et Thomassé [EKT19], qui prétend que la densité bipartie induite de graphes sans triangle de degré moyen d est au moins de l'ordre de ln d, nous démontrons cette conjecture quand d est suffisamment grand en termes du nombre de sommets n, à savoir d est au moins de l'ordre de (n ln n)^(1/2). Ce résultat ne pourrait être amélioré que par une valeur de l'ordre de ln n, ce que nous montrons à l'aide d'une construction reposant sur le processus sans triangle. Nos travaux se ramènent à un problème intéressant, celui de déterminer le nombre chromatique fractionnaire maximal d'un graphe épars à n sommets. Nous prouvons des bornes supérieures non triviales pour les graphes sans triangle, et pour les graphes dont chaque sommet appartient à un nombre borné de triangles.Cette thèse est reliée aux nombres de Ramsey. À ce jour, le meilleur encadrement connu sur R(3,t) nous est donné par le résultat de Shearer, et par une analyse récente du processus sans triangle [BoKe13+,FGM13+], ce qui donne(1-o(1)) t²/(4 ln t) < R(3,t) < (1+o(1)) t²/ln t. (1)Beaucoup de nos résultats ne pourraient être améliorés à moins d'améliorer par la même occasion (1), ce qui constituerait une révolution dans la théorie de Ramsey quantitativeThis thesis focuses on generalisations of the colouring problem in various classes of sparse graphs.Triangle-free graphs of maximum degree d are known to have independence ratio at least (1-o(1))ln d/d by a result of Shearer [She83], and chromatic number at most O(d/ln d) by a result of Johansson [Joh96], as d grows to infinity. This was recently improved by Molloy, who showed that the chromatic number of triangle-free graphs of maximum degree d is at most (1+o(1))d/ln d as d grows to infinity.While Molloy's result is expressed with a global parameter, the maximum degree of the graph, we first show that it is possible to extend it to local colourings. Those are list colourings where the size of the list associated to a given vertex depends only on the degree of that vertex. With a different method relying on the properties of the hard-core distribution on the independent sets of a graph, we obtain a similar result for local fractional colourings, with weaker assumptions. We also provide an analogous result concerning local fractional colourings of graphs where each vertex is contained in a bounded number of triangles, and a sharp bound for the occupancy fraction — the average size of an independent set — of those graphs. In another direction, we also consider graphs of girth 7, and prove related results which improve on the previously known bounds when the maximum degree does not exceed 10^7. Finally, for d-regular graphs with d in the set {3,4,5}, of girth g varying between 6 and 12, we provide new lower bounds on the independence ratio.The second chapter is dedicated to distance colourings of graphs, a generalisation of strong edge-colourings. Extending the theme of the first chapter, we investigate minimal sparsity conditions in order to obtain Johansson-like results for distance colourings. While Johansson's result follows from the exclusion of triangles — or actually of cycles of any fixed length — we show that excluding cycles of length 2k, provided that k>t, has a similar effect for the distance-t chromatic number and the distance-(t+1) chromatic index. When t is odd, the same holds for the distance-t chromatic number by excluding cycles of fixed odd length at least 3t. We investigate the asymptotic sharpness of our results with constructions of combinatorial, algebraic, and probabilistic natures.In the third chapter, we are interested in the bipartite induced density of triangle-free graphs, a parameter which conceptually lies between the independence ratio and the fractional chromatic number. Motivated by a conjecture of Esperet, Kang, and Thomassé [EKT19], which states that the bipartite induced density of a triangle-free graph of average degree d should be at least of the order of ln d, we prove that the conjecture holds for when d is large enough in terms of the number of vertices n, namely d is at least of the order of (n ln n)^(1/2). Our result is shown to be sharp up to term of the order of ln n, with a construction relying on the triangle-free process. Our work on the bipartite induced density raises an interesting related problem, which aims at determining the maximum possible fractional chromatic number of sparse graph where the only known parameter is the number of vertices. We prove non trivial upper bounds for triangle-free graphs, and graphs where each vertex belongs to a bounded number of triangles.All the content of this thesis is a collection of specialisations of the off-diagonal Ramsey theory. To this date, the best-known bounds on the off-diagonal Ramsey number R(3,t) come from the aforementioned result of Shearer for the upper-bound, and a recent analysis of the triangle-free process [BoKe13+,FGM13+] for the lower bound, giving(1-o(1)) t²/(4 ln t) < R(3,t) < (1+o(1)) t²/ln t. (1)Many of our results are best possible barring an improvement of (1), which would be a breakthrough in off-diagonal Ramsey theory
43
Phadnis, Miti. "Statistical Analysis of Linear Analog Circuits Using Gaussian Message Passing in Factor Graphs." DigitalCommons@USU, 2009. https://digitalcommons.usu.edu/etd/504.
Full textAbstract:
This thesis introduces a novel application of factor graphs to the domain of analog circuits. It proposes a technique of leveraging factor graphs for performing statistical yield analysis of analog circuits that is much faster than the standard Monte Carlo/Simulation Program With Integrated Circuit Emphasis (SPICE) simulation techniques. We have designed a tool chain to model an analog circuit and its corresponding factor graph and then use a Gaussian message passing approach along the edges of the graph for yield calculation. The tool is also capable of estimating unknown parameters of the circuit given known output statistics through backward message propagation in the factor graph. The tool builds upon the concept of domain-specific modeling leveraged for modeling and interpreting different kinds of analog circuits. Generic Modeling Environment (GME) is used to design modeling environment for analog circuits. It is a configurable tool set that supports creation of domain-specific design environments for different applications. This research has developed a generalized methodology that could be applied towards design automation of different kinds of analog circuits, both linear and nonlinear. The tool has been successfully used to model linear amplifier circuits and a nonlinear Metal Oxide Semiconductor Field Effect Transistor (MOSFET) circuit. The results obtained by Monte Carlo simulations performed on these circuits are used as a reference in the project to compare against the tool's results. The tool is tested for its efficiency in terms of time and accuracy against the standard results.
44
Ahlquist, Blair 1979. "Probability on graphs: A comparison of sampling via random walks and a result for the reconstruction problem." Thesis, University of Oregon, 2010. http://hdl.handle.net/1794/11144.
Full textAbstract:
vi, 48 p. : ill. A print copy of this thesis is available through the UO Libraries. Search the library catalog for the location and call number.We compare the relaxation times of two random walks - the simple random walk and the metropolis walk - on an arbitrary finite multigraph G. We apply this result to the random graph with n vertices, where each edge is included with probability p = [Special characters omitted.] where λ > 1 is a constant and also to the Newman-Watts small world model. We give a bound for the reconstruction problem for general trees and general 2 × 2 matrices in terms of the branching number of the tree and some function of the matrix. Specifically, if the transition probabilities between the two states in the state space are a and b , we show that we do not have reconstruction if Br( T ) [straight theta] < 1, where [Special characters omitted.] and Br( T ) is the branching number of the tree in question. This bound agrees with a result obtained by Martin for regular trees and is obtained by more elementary methods. We prove an inequality closely related to this problem.
Committee in charge: David Levin, Chairperson, Mathematics; Christopher Sinclair, Member, Mathematics; Marcin Bownik, Member, Mathematics; Hao Wang, Member, Mathematics; Van Kolpin, Outside Member, Economics
45
Sahnoun, Réda. "Composition asymptotique de processus d'urne de Pólya et applications à l'algorithmique." Versailles-St Quentin en Yvelines, 2010. http://www.theses.fr/2010VERS0051.
Full textAbstract:
Les processus de Pólya sont des marches aléatoires à temps discret dans R^d, généralisations naturelles des urnes de Pólya-Eggenberger. Dans ce dernier modèle, une urne peut contenir des boules de d couleurs différentes, et une matrice (déterministe) à coefficients entiers relatifs décrit les règles de remplacement après chaque tirage. De nombreuses situations issues de l'informatique (structures arborescentes) ou de la physique théorique (percolation, fragmentation) se modélisent par ces objets. Le comportement asymptotique de ces processus fait apparaître une famille de nouvelles lois de probabilité, certaines d'entre elles sont déterminées par leurs moments; tandis que pour d'autre, la série génératrice des moments diverge. Ceci témoigne de la richesse de ce modèle, cependant, les cas étudiés permettent de dégager la combinatoire complexe du cas généralPolya processes are discrete-time random walks in R^d, natural generalizations of Pólya-Eggenberger urns. In this latter model, a urn may contain balls of different colors and a matrix (deterministic) with integer coefficients describes the rules for replacement after each draw. Many situations from the computer sciences (tree structures) or theoretical physics (percolation fragmentation) are modeled by these objects. The asymptotic behavior of these processes reveals a new family of probability laws, some of them are determined by their moments, while for the other, the exponential generating function of moments diverges. This attests to the richness of this model, however, the cases reviewed permit to identify the complex combinatorics of the general case
46
Rombach, Michaela Puck. "Colouring, centrality and core-periphery structure in graphs." Thesis, University of Oxford, 2013. http://ora.ox.ac.uk/objects/uuid:7326ecc6-a447-474f-a03b-6ec244831ad4.
Full textAbstract:
Krivelevich and Patkós conjectured in 2009 that χ(G(n, p)) ∼ χ=(G(n, p)) ∼ χ∗=(G(n, p)) for C/n < p < 1 − ε, where ε > 0. We prove this conjecture for n−1+ε1 < p < 1 − ε2 where ε1, ε2 > 0. We investigate several measures that have been proposed to indicate centrality of nodes in networks, and find examples of networks where they fail to distinguish any of the vertices nodes from one another. We develop a new method to investigate core-periphery structure, which entails identifying densely-connected core nodes and sparsely-connected periphery nodes. Finally, we present an experiment and an analysis of empirical networks, functional human brain networks. We found that reconfiguration patterns of dynamic communities can be used to classify nodes into a stiff core, a flexible periphery, and a bulk. The separation between this stiff core and flexible periphery changes as a person learns a simple motor skill and, importantly, it is a good predictor of how successful the person is at learning the skill. This temporally defined core-periphery organisation corresponds well with the core- periphery detected by the method that we proposed earlier the static networks created by averaging over the subjects dynamic functional brain networks.
47
Averous, Jean, and Michel Meste. "Famille de boules centrales d'une probabilité sur un espace de Banach. Application aux ordres et mesures de dissymétrie et de kurtosis." Toulouse 3, 1992. http://www.theses.fr/1992TOU30017.
Full textAbstract:
Pour une probabilite sur un espace de banach, les auteurs introduisent une famille de boules centrales, indicee par leur rayon; ce sont les boules fermees dont le centre minimise un critere qui, si le rayon est nul, est celui qui sert a definir la mediane spatiale. Les proprietes de cette mediane ont ete etudiees par kemperman en 1987. Il est montre que ces proprietes, en particulier celles de robustesse et de convergence, sont conservees par les boules centrales. Les proprietes plus specifiques des fonctions de centrage et de dispersion qui associent au rayon d'une boule centrale respectivement le centre et la probabilite de cette boule, sont detaillees. Ces proprietes sont utilisees pour definir, d'une part une dissymetrie par rapport a la mediane dans la direction d'un cone convexe ainsi qu'un ordre et des mesures pour ce concept, d'autre part une fonction de kurtosis sur laquelle les auteurs fondent un ordre ne necessitant pas la symetrie centrale des lois. Des exemples de ces fonctions sont donnes pour des lois usuelles. Centre, dispersion, dissymetrie et kurtosis sont ainsi analyses de facon coherente avec la norme. Dans le cas particulier de lois reelles ils generalisent les m-parametres de centrage par des intervalles centraux optimaux, et definissent pour la s-moyenne un poids des queues coherent avec ce centre. Ce dernier concept leur sert a definir, pour toute loi de s-moyenne finie, une fonction de repartition de loi continue unimodale dont l'analyse exploratoire par des methodes fondees sur les quantiles fournit une description de la loi initiale au sens s-moyenne. Ce concept leur sert egalement a unifier la classification des familles nonparametriques de lois de duree de vie et a preciser leur structure hierarchique
48
Rangel, Walteros Pedro Andres. "A non-asymptotic study of low-rank estimation of smooth kernels on graphs." Diss., Georgia Institute of Technology, 2014. http://hdl.handle.net/1853/52988.
Full textAbstract:
This dissertation investigates the problem of estimating a kernel over a large graph based on a sample of noisy observations of linear measurements of the kernel. We are interested in solving this estimation problem in the case when the sample size is much smaller than the ambient dimension of the kernel. As is typical in high-dimensional statistics, we are able to design a suitable estimator based on a small number of samples only when the target kernel belongs to a subset of restricted complexity. In our study, we restrict the complexity by considering scenarios where the target kernel is both low-rank and smooth over a graph. Using standard tools of non-parametric estimation, we derive a minimax lower bound on the least squares error in terms of the rank and the degree of smoothness of the target kernel. To prove the optimality of our lower-bound, we proceed to develop upper bounds on the error for a least-square estimator based on a non-convex penalty. The proof of these upper bounds depends on bounds for estimators over uniformly bounded function classes in terms of Rademacher complexities. We also propose a computationally tractable estimator based on least-squares with convex penalty. We derive an upper bound for the computationally tractable estimator in terms of a coherence function introduced in this work. Finally, we present some scenarios wherein this upper bound achieves a near-optimal rate. The motivations for studying such problems come from various real-world applications like recommender systems and social network analysis.
49
Favier, Aurélie. "Décompositions fonctionnelles et structurelles dans les modèles graphiques probabilistes appliquées à la reconstruction d'haplotypes." Toulouse 3, 2011. http://thesesups.ups-tlse.fr/1527/.
Full textAbstract:
Cette thèse s'articule autour de deux thèmes : la décomposition dans les modèles graphiques que sont, entre autres, les réseaux bayésiens et les réseaux de fonctions de coûts (WCSP) et la reconstruction d'haplotypes dans les pedigrees. Nous appliquons les techniques des WCSP pour traiter les réseaux bayésiens, en exploitant les propriétés structurelles et fonctionnelles, de manière exacte et approchée, des instances dans le cadre de l'inférence (ou d'un problème proche, celui de compter le nombre de solutions) et de l'optimisation. Nous définissons en particulier une décomposition de fonctions qui produit des fonctions portant sur un plus petit nombre de variables. Un exemple d'application en optimisation est la reconstruction d'haplotypes. Elle est essentielle pour une meilleure prédiction de la gravité de maladie ou pour comprendre des caractères physiques particuliers. La reconstruction d'haplotypes se modélise sous forme d'un réseau bayésien. La décomposition fonctionnelle permet de réduire ce réseau bayésien en un problème d'optimisation WCSP (Max-2SAT)This thesis is based on two topics : the decomposition in graphical models which are, among others, Bayesian networks and cost function networks (WCSP) and the haplotype reconstruction in pedigrees. We apply techniques of WCSP to treat Bayesian network. We exploit stuctural and fonctional properties, in an exact and approached methods. Particulary, we define a decomposition of function which produces functions with a smaller variable number. An application example in optimization is the haplotype reconstruction. It is essential for a best prediction of seriousness of disease or to understand particular physical characters. Haplotype reconstruction is represented with a Bayesian network. The functionnal decomposition allows to reduce this Bayesian network in an optimization problem WCSP (Max-2SAT)
50
Zappella, G. "LEARNING ON GRAPHS: ALGORITHMS FOR CLASSIFICATION AND SEQUENTIAL DECISIONS." Doctoral thesis, Università degli Studi di Milano, 2014. http://hdl.handle.net/2434/234167.
Full textAbstract:
In recent years, networked data have become widespread due to the increasing importance of social networks and other web-related applications. This growing interest is driving researchers to design new algorithms for solving important problems that involve networked data.
In this thesis we present a few practical yet principled algorithms for learning and sequential decision-making on graphs.
Classification of networked data is an important problem that has recently received a great deal of attention from the machine learning community. This is due to its many important practical applications: computer vision, bioinformatics, spam detection and text categorization, just to cite a few of the more conspicuous examples.
We focus our attention on the task called ``node classification'', often studied in the semi-supervised (transductive) setting. We present two algorithms, motivated by different theoretical frameworks. The first algorithm is studied in the well-known online adversarial setting, within which it enjoys an optimal mistake bound (up to logarithmic factors). The second algorithm is based on a game-theoretic approach, where each node of the network is maximizing its own payoff. The setting corresponds to a Graph Transduction Game in which the graph is a tree. For this special case, we show that the Nash Equilibrium of the game can be reached in linear time.
We complement our theoretical findings with an extensive set of experiments using datasets from many different domains.
In the second part of the thesis, we present a rapidly emerging theme in the analysis of networked data: signed networks, graphs whose edges carry a label encoding the positive or negative nature of the relationship between the connected nodes. For example, social networks and e-commerce offer several examples of signed relationships: Slashdot users can tag other users as friends or foes, Epinions users can rate each other positively or negatively, Ebay users develop trust and distrust towards sellers in the network. More generally, two individuals that are related because they rate similar products in a recommendation website may agree or disagree in their ratings.
Many heuristics for link classification in social networks are based on a form of social balance summarized by the motto “the enemy of my enemy is my friend”. This is equivalent to saying that the signs on the edges of a social graph tend to be consistent with some two-clustering structure of the nodes, where edges connecting nodes from the same cluster are positive and edges connecting nodes from different clusters are negative.
We present algorithms for the batch transductive active learning setting, where the topology of the graph is known in advance and our algorithms can ask for the label of some specific edges during the training phase (before starting with the predictions).
These algorithms can achieve different tradeoffs between the number of mistakes during the test phase and the number of labels required during the training phase.
We also presented an experimental comparison against some state-of-the-art spectral heuristics presented in a previous work, where we show that the simplest or our algorithms is already competitive with the best of these heuristics.
In the last chapter we present another way to exploit relational information for sequential predictions: the networks of bandits.
Contextual bandits adequately formalize the exploration-exploitation trade-offs arising in several industrially relevant applications, such online advertisement and recommendation systems.
Many practical applications have a strong social component whose integration in the bandit algorithm could lead to a significant performance improvement: for example, since often friends have similar taste, we may want to serve contents to a group of users by taking advantage of an underlying network of social relationships among them.
We introduce a novel algorithmic approach to a particular networked bandit problem. More specifically, we run a bandit algorithm on each network node (e.g., user), allowing it to ``share'' feedback signals with the other nodes by employing the multi-task kernel.
We derive the regret analysis of this algorithm and, finally, we report on the results of an experimental comparison between our approach and the state of the art techniques, on both artificial and real-world social networks.