Dissertations / Theses on the topic 'Random graphs'
To see the other types of publications on this topic, follow the link: Random graphs.
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 'Random graphs.'
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
Ramos, Garrido Lander. "Graph enumeration and random graphs." Doctoral thesis, Universitat Politècnica de Catalunya, 2017. http://hdl.handle.net/10803/405943.
Full textAbstract:
In this thesis we use analytic combinatorics to deal with two related problems: graph enumeration and random graphs from constrained classes of graphs. We are interested in drawing a general picture of some graph families by determining, first, how many elements are there of a given possible size (graph enumeration), and secondly, what is the typical behaviour of an element of fixed size chosen uniformly at random, when the size tends to infinity (random graphs). The problems concern graphs subject to global conditions, such as being planar and/or with restrictions on the degrees of the vertices.
In Chapter 2 we analyse random planar graphs with minimum degree two and three. Using techniques from analytic combinatorics and the concepts of core and kernel of a graph, we obtain precise asymptotic estimates and analyse relevant parameters for random graphs, such as the number of edges or the size of the core, where we obtain Gaussian limit laws. More challenging is the extremal parameter equal to the size of the largest tree attached to the core. In this case we obtain a logarithmic estimate for the expected value together with a concentration result.
In Chapter 3 we study the number of subgraphs isomorphic to a fixed graph in subcritical classes of graphs. We obtain Gaussian limit laws with linear expectation and variance when the fixed graph is 2-connected. The main tool is the analysis of infinite systems of equations by Drmota, Gittenberger and Morgenbesser, using the theory of compact operators. Computing the exact constants for the first estimates of the moments is in general out of reach. For the class of series-parallel graphs we are able to compute them in some particular interesting cases.
In Chapter 4 we enumerate (arbitrary) graphs where the degree of every vertex belongs to a fixed subset of the natural numbers. In this case the associated generating functions are divergent and our analysis uses instead the so-called configuration model. We obtain precise asymptotic estimates for the number of graphs with given number of vertices and edges and subject to the degree restriction. Our results generalize widely previous special cases, such as d-regular graphs or graphs with minimum degree at least d.En aquesta tesi utilitzem l'analítica combinatòria per treballar amb dos problemes relacionats: enumeració de grafs i grafs aleatoris de classes de grafs amb restriccions. En particular ens interessa esbossar un dibuix general de determinades famílies de grafs determinant, en primer lloc, quants grafs hi ha de cada mida possible (enumeració de grafs), i, en segon lloc, quin és el comportament típic d'un element de mida fixa triat a l'atzar uniformement, quan aquesta mida tendeix a infinit (grafs aleatoris). Els problemes en què treballem tracten amb grafs que satisfan condicions globals, com ara ésser planars, o bé tenir restriccions en el grau dels vèrtexs. En el Capítol 2 analitzem grafs planar aleatoris amb grau mínim dos i tres. Mitjançant tècniques de combinatòria analítica i els conceptes de nucli i kernel d'un graf, obtenim estimacions asimptòtiques precises i analitzem paràmetres rellevants de grafs aleatoris, com ara el nombre d'arestes o la mida del nucli, on obtenim lleis límit gaussianes. També treballem amb un paràmetre que suposa un repte més important: el paràmetre extremal que es correspon amb la mida de l'arbre més gran que penja del nucli. En aquest cas obtenim una estimació logarítmica per al seu valor esperat, juntament amb un resultat sobre la seva concentració. En el Capítol 3 estudiem el nombre de subgrafs isomorfs a un graf fix en classes de grafs subcrítiques. Quan el graf fix és biconnex, obtenim lleis límit gaussianes amb esperança i variància lineals. L'eina principal és l'anàlisi de sistemes infinits d'equacions donada per Drmota, Gittenberger i Morgenbesser, que utilitza la teoria d'operadors compactes. El càlcul de les constants exactes de la primera estimació dels moments en general es troba fora del nostre abast. Per a la classe de grafs sèrie-paral·lels podem calcular les constants en alguns casos particulars interessants. En el Capítol 4 enumerem grafs (arbitraris) el grau de cada vèrtex dels quals pertany a un subconjunt fix dels nombres naturals. En aquest cas les funcions generatrius associades són divergents i la nostra anàlisi utilitza l'anomenat model de configuració. El nostre resultat consisteix a obtenir estimacions asimptòtiques precises per al nombre de grafs amb un nombre de vèrtexs i arestes donat, amb la restricció dels graus. Aquest resultat generalitza àmpliament casos particulars existents, com ara grafs d-regulars, o grafs amb grau mínim com a mínim d.
2
Seierstad, Taral Guldahl. "The phase transition in random graphs and random graph processes." Doctoral thesis, [S.l.] : [s.n.], 2007. http://deposit.ddb.de/cgi-bin/dokserv?idn=985760044.
Full text
3
Engström, Stefan. "Random acyclicorientations of graphs." Thesis, KTH, Matematik (Avd.), 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-116500.
Full text
4
Heckel, Annika. "Colourings of random graphs." Thesis, University of Oxford, 2016. https://ora.ox.ac.uk/objects/uuid:79e14d55-0589-4e17-bbb5-a216d81b8875.
Full textAbstract:
We study graph parameters arising from different types of colourings of random graphs, defined broadly as an assignment of colours to either the vertices or the edges of a graph. The chromatic number X(G) of a graph is the minimum number of colours required for a vertex colouring where no two adjacent vertices are coloured the same. Determining the chromatic number is one of the classic challenges in random graph theory. In Chapter 3, we give new upper and lower bounds for the chromatic number of the dense random graph G(n,p)) where p ∈ (0,1) is constant. These bounds are the first to match up to an additive term of order o(1) in the denominator, and in particular, they determine the average colour class size in an optimal colouring up to an additive term of order o(1). In Chapter 4, we study a related graph parameter called the equitable chromatic number. This is defined as the minimum number of colours needed for a vertex colouring where no two adjacent vertices are coloured the same and, additionally, all colour classes are as equal in size as possible. We prove one point concentration of the equitable chromatic number of the dense random graph G(n,m) with m = pn(n-1)/2, p < 1-1/e2 constant, on a subsequence of the integers. We also show that whp, the dense random graph G(n,p) allows an almost equitable colouring with a near optimal number of colours. We call an edge colouring of a graph G a rainbow colouring if every pair of vertices is joined by a rainbow path, which is a path where no colour is repeated. The least number of colours where this is possible is called the rainbow connection number rc(G). Since its introduction in 2008 as a new way to quantify how well connected a given graph is, the rainbow connection number has attracted the attention of a great number of researchers. For any graph G, rc(G)≥diam(G), where diam(G) denotes the diameter. In Chapter 5, we will see that in the random graph G(n,p), rainbow connection number 2 is essentially equivalent to diameter 2. More specifically, we consider G ~ G(n,p) close to the diameter 2 threshold and show that whp rc(G) = diam(G) ∈ {2,3}. Furthermore, we show that in the random graph process, whp the hitting times of diameter 2 and of rainbow connection number 2 coincide. In Chapter 6, we investigate sharp thresholds for the property rc(G)≤=r where r is a fixed integer. The results of Chapter 6 imply that for r=2, the properties rc(G)≤=2 and diam(G)≤=2 share the same sharp threshold. For r≥3, the situation seems quite different. We propose an alternative threshold and prove that this is an upper bound for the sharp threshold for rc(G)≤=r where r≥3.
5
Oosthuizen, Joubert. "Random walks on graphs." Thesis, Stellenbosch : Stellenbosch University, 2014. http://hdl.handle.net/10019.1/86244.
Full textAbstract:
Thesis (MSc)--Stellenbosch University, 2014.ENGLISH ABSTRACT: We study random walks on nite graphs. The reader is introduced to general Markov chains before we move on more specifically to random walks on graphs. A random walk on a graph is just a Markov chain that is time-reversible. The main parameters we study are the hitting time, commute time and cover time. We nd novel formulas for the cover time of the subdivided star graph and broom graph before looking at the trees with extremal cover times. Lastly we look at a connection between random walks on graphs and electrical networks, where the hitting time between two vertices of a graph is expressed in terms of a weighted sum of e ective resistances. This expression in turn proves useful when we study the cover cost, a parameter related to the cover time.
AFRIKAANSE OPSOMMING: Ons bestudeer toevallige wandelings op eindige gra eke in hierdie tesis. Eers word algemene Markov kettings beskou voordat ons meer spesi ek aanbeweeg na toevallige wandelings op gra eke. 'n Toevallige wandeling is net 'n Markov ketting wat tyd herleibaar is. Die hoof paramaters wat ons bestudeer is die treftyd, pendeltyd en dektyd. Ons vind oorspronklike formules vir die dektyd van die verdeelde stergra ek sowel as die besemgra ek en kyk daarna na die twee bome met uiterste dektye. Laastens kyk ons na 'n verband tussen toevallige wandelings op gra eke en elektriese netwerke, waar die treftyd tussen twee punte op 'n gra ek uitgedruk word in terme van 'n geweegde som van e ektiewe weerstande. Hierdie uitdrukking is op sy beurt weer nuttig wanneer ons die dekkoste bestudeer, waar die dekkoste 'n paramater is wat verwant is aan die dektyd.
6
Bienvenu, François. "Random graphs in evolution." Thesis, Sorbonne université, 2019. http://www.theses.fr/2019SORUS180.
Full textAbstract:
Cette thèse est composée de cinq projets de recherche indépendants, tous en lien soit avec les graphes aléatoires, soit avec la biologie évolutive - mais pour la plupart à l'interface de ces deux disciplines. Dans les Chapitres 2 et 3, nous introduisons deux modèles de graphes aléatoires correspondant à la distribution stationnaire d'une chaîne de Markov. Le premier de ces modèles, que nous appelons le graphe "split-and-drift", décrit la structure et la dynamique des réseaux d'interfécondité; le second est une forêt aléatoire inspirée du modèle de Moran, modèle central de la génétique des populations. Le Chapitre 4 est consacré à l'étude d'une nouvelle classe de réseaux phylogénétiques basée sur les "tree-child networks", que nous appelons "ranked tree-child networks" (RTCNs). Nous expliquons comment les énumérer et les échantillonner, puis étudions la structure des grands RTCNs uniformes. Dans le Chapitre 5, nous prouvons un résultat général à propos de la percolation dans les graphes orientés aléatoirement : l'association positive du cluster de percolation orientée. Enfin, le Chapitre 6 traite d'une des statistiques les plus utilisées en biologie des population : l'âge moyen auquel les parents donnent naissance. Nous détaillons plusieurs problèmes liés à l'une des méthodes les plus utilisées pour le quantifier et proposons une méthode alternativeThis thesis consists of five independent research projects, related either to random graphs or to evolutionary biology - and most often to both. Chapters 2 and 3 introduce two random graphs that are obtained as the stationary distributions of graph-valued Markov chains. The first of these, which we term the split-and-drift random graph, aims to describe the structure and dynamics of interbreeding-potential networks; the second one is a random forest that was inspired by the celebrated Moran model of population genetics. Chapter 4 is devoted to the study of a new class of phylogenetic networks that we term ranked tree-child networks, or RTCNs for short. These networks correspond to a subclass of tree-child networks that are endowed with an additional structure ensuring compatibility with a time-embedded evolutionary process, and are designed to model reticulated phylogenies. We focus on the enumeration and sampling of RTCNs before turning to the structural properties of large uniform RTCNs. In Chapter 5, we prove a general result about oriented percolation in randomly oriented graphs: the positive association of the percolation cluster. Finally, in Chapter 6 we focus on a widely used statistic of populations: the mean age at which parents give birth. We point out several problems with one of the most widely used way to compute it, and provide an alternative measure
7
Johansson, Tony. "Random Graphs and Algorithms." Research Showcase @ CMU, 2017. http://repository.cmu.edu/dissertations/938.
Full textAbstract:
This thesis is concerned with the study of random graphs and random algorithms. There are three overarching themes. One theme is sparse random graphs, i.e. random graphs in which the average degree is bounded with high probability. A second theme is that of finding spanning subsets such as spanning trees, perfect matchings and Hamilton cycles. A third theme is solving optimization problems on graphs with random edge costs.
8
Ross, Christopher Jon. "Properties of Random Threshold and Bipartite Graphs." The Ohio State University, 2011. http://rave.ohiolink.edu/etdc/view?acc_num=osu1306296991.
Full text
9
Pymar, Richard James. "Random graphs and random transpositions on a circle." Thesis, University of Cambridge, 2012. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.610350.
Full text
10
Crippa, Davide. "q-distributions and random graphs /." [S.l.] : [s.n.], 1994. http://e-collection.ethbib.ethz.ch/show?type=diss&nr=10923.
Full text
11
Weissl, Andreas Christian. "Random graphs with structural constraints /." Zürich : ETH, 2007. http://e-collection.ethbib.ethz.ch/show?type=diss&nr=17088.
Full text
12
Panagiotou, Konstantinos. "Colorability properties of random graphs /." Zürich : ETH, 2008. http://e-collection.ethbib.ethz.ch/show?type=diss&nr=17740.
Full text
13
Schickinger, Thomas. "Complete subgraphs of random graphs." [S.l. : s.n.], 2002. http://deposit.ddb.de/cgi-bin/dokserv?idn=966629353.
Full text
14
Weigel, Martin. "Vertex Models on Random Graphs." Doctoral thesis, Universitätsbibliothek Leipzig, 2004. http://nbn-resolving.de/urn:nbn:de:bsz:15-qucosa-37308.
Full textAbstract:
Diese Arbeit befaßt sich mit der Koppelung von Vertex-Modellen an die planaren $\phi^4$-Zufallsgraphen des Zugangs zur Quantengravitation über dynamische Polygonifizierungen. Das betrachtete System hat eine doppelte Bedeutung, einerseits als die Koppelung einer konformen Feldtheorie mit zentraler Ladung $C=1$ an zweidimensionale Euklidische Quantengravitation, andererseits als Anwendung von geometrischer, "annealed" Unordnung auf ein prototypisches Modell der statistischen Mechanik. Da das Modell mit Hilfe einer großangelegten Reihe von Monte Carlo Simulationen untersucht wird, müssen entsprechende Techniken für die Simulation von dynamischen Quadrangulierungen bzw. die dualen $\phi^4$-Graphen entwickelt werden. Hierzu werden verschiedene Algorithmen und die dazugehörigen Züge vorgeschlagen und hinsichtlich ihrer Ergodizität und Effizienz untersucht. Zum Vergleich mit exakten Ergebnissen werden die Verteilung der Koordinationszahlen bzw. bestimmte Analoga davon konstruiert. Für Simulationen des $F$-Modells auf $\phi^4$-Zufallsgraphen wird ein Ordnungsparameter für den antiferroelektrischen Phasenübergang mit Hilfe einer Plakettenspindarstellung formuliert. Ausführliche "finite-size scaling"-Analysen des Kosterlitz-Thouless-Phasenübergangs des $F$-Modells auf dem Quadratgitter und auf Zufallsgraphen werden vorgestellt und die Positionen der jeweiligen kritischen Punkte sowie die dazugehörigen kritischen Exponenten werden bestimmt. Die Rückreaktion des Vertex-Modells auf die Zufallsgraphen wird in Form der Koordinationszahlverteilung, der Verteilung der "Baby-Universen" und dem daraus resultierenden String-Suszeptibilitäts-Exponenten sowie durch die geometrische Zweipunktfunktion analysiert, die eine Schätzung der intrinsischen Hausdorff-Dimension des gekoppelten Systems liefertIn this thesis, the coupling of ice-type vertex models to the planar $\phi^4$ random graphs of the dynamical polygonifications approach to quantum gravity is considered. The investigated system has a double significance as a conformal field theory with central charge $C=1$ coupled to two-dimensional Euclidean quantum gravity and as the application of a special type of annealed connectivity disorder to a prototypic model of statistical mechanics. Since the model is analyzed by means of large-scale Monte Carlo simulations, suitable simulation techniques for the case of dynamical quadrangulations and the dual $\phi^4$ random graphs have to be developed. Different algorithms and the associated update moves are proposed and investigated with respect to their ergodicity and performance. For comparison to exact results, the co-ordination number distribution of the dynamical polygonifications model, or certain analogues of it, are constructed. For simulations of the 6-vertex $F$ model on $\phi^4$ random graphs, an order parameter for its anti-ferroelectric phase transitions is constructed in terms of a "plaquette spin" representation. Extensive finite-size scaling analyses of the Kosterlitz-Thouless point of the square-lattice and random graph $F$ models are presented and the locations of the critical points as well as the corresponding critical exponents are determined. The back-reaction of the coupled vertex model on the random graphs is investigated by an analysis of the co-ordination number distribution, the distribution of "baby universes" and the string susceptibility exponent as well as the geometric two-point function, yielding an estimate for the internal Hausdorff dimension of the coupled system
15
Penman, David Binnie. "Random graphs with correlation structure." Thesis, University of Sheffield, 1998. http://etheses.whiterose.ac.uk/14768/.
Full textAbstract:
In this thesis we consider models of random graphs where, unlike in the classical models G (n, p) the probability of an edge arising can be correlated with that of other edges arising. Attention focuses on graphs whose vertices are each assigned a colour (type) at random and where edges between differently coloured vertices subsequently arise with different probabilities (so-called RRC graphs), especially the special case with two colours. Various properties of these graphs are considered, often by comparing and contrasting them with the classical model with the same probability of each particular edge existing. Topics examined include the probabilities of trees and cycles, how the joint probability of two subgraphs compares with the product of their probabilities, the number of edges in the graph (including large deviations results), connectedness, connectivity, the number and order of complete graphs and cliques, and tournaments with correlation structure.
16
Dou, Carl C. Z. (Carl Changzhu). "Studies of random walks on groups and random graphs." Thesis, Massachusetts Institute of Technology, 1992. http://hdl.handle.net/1721.1/13243.
Full text
17
Kang, Mihyun. "Random planar structures and random graph processes." Doctoral thesis, [S.l.] : [s.n.], 2007. http://deposit.ddb.de/cgi-bin/dokserv?idn=985516585.
Full text
18
White, M. D. "Cycles in edge-coloured graphs and subgraphs of random graphs." Thesis, University of Oxford, 2011. http://ora.ox.ac.uk/objects/uuid:95ef351e-acb1-442c-adf5-970487e30a4d.
Full textAbstract:
This thesis will study a variety of problems in graph theory. Initially, the focus will be on finding minimal degree conditions which guarantee the existence of various subgraphs. These subgraphs will all be formed of cycles, and this area of work will fall broadly into two main categories. First to be considered are cycles in edge-coloured graphs and, in particular, two questions of Li, Nikiforov and Schelp. It will be shown that a 2-edge-coloured graph with minimal degree at least 3n/4 either is isomorphic to the complete 4-partite graph with classes of order n/4, or contains monochromatic cycles of all lengths between 4 and n/2 (rounded up). This answers a conjecture of Li, Nikiforov and Schelp. Attention will then turn to the length of the longest monochromatic cycle in a 2-edge-coloured graph with minimal degree at least cn. In particular, a lower bound for this quantity will be proved which is asymptotically best possible. The next chapter of the thesis then shows that a hamiltonian graph with minimal degree at least (5-sqrt7)n/6 contains a 2-factor with two components. The thesis then concludes with a chapter about X_H, which is the number of copies of a graph H in the random graph G(n,p). In particular, it will be shown that, for a connected graph H, the value of X_H modulo k is approximately uniformly distributed, provided that k is not too large a function of n.
19
Weinstein, Lee. "Empirical study of graph properties with particular interest towards random graphs." Diss., Connect to the thesis, 2005. http://hdl.handle.net/10066/1485.
Full text
20
Riordan, Oliver Maxim. "Subgraphs of the discrete torus, random graphs and general graph invariants." Thesis, University of Cambridge, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.624757.
Full text
21
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
22
Kurauskas, Valentas. "On two models of random graphs." Doctoral thesis, Lithuanian Academic Libraries Network (LABT), 2013. http://vddb.library.lt/obj/LT-eLABa-0001:E.02~2013~D_20131216_081822-36288.
Full textAbstract:
The dissertation consists of two parts. In the first part several asymptotic properties of random intersection graphs are studied. They include birth thresholds for small complete subgraphs in the binomial random intersection graph, the clique number in sparse random intersection graphs and the chromatic index of random uniform hypergraphs. Several new methods and theoretically and practically relevant algorithms are proposed. Some results are illustrated with data from real-world networks. The second part deals with asymptotic enumeration and properties of graphs from minor-closed classes in the case when the excluded minors are disjoint. The class of graphs without k+1 (vertex-)disjoint cycles and more general classes of graphs without k+1 disjoint excluded minors (satisfying a condition related to fans) are considered. Typical graphs in such classes are shown to have a simple “k apex vertex” structure. Other asymptotic properties (connectivity, number of components, chromatic number, vertex degrees) are also determined. Finally, it is shown that typical graphs without k+1 disjoint minors K4 have a more complicated “2k+1 apex vertex” structure, and properties of such graphs are investigated. Part of the results is proved in greater generality. A variety of methods from computer science, graph theory, combinatorics and the theory of generating functions are applied.Disertacijoje yra dvi pagrindinės dalys. Pirmojoje dalyje gaunami keli nauji rezultatai uždaviniams, susijusiems su atsitiktiniais sankirtų grafais. Nagrinėjamas pilnojo pografio gimimo slenkstis binominiame atsitiktiniame sankirtų grafe, didžiausios klikos eilė atsitiktiniame retame sankirtų grafe ir chromatinio indekso eilė atsitiktiniame reguliariajame hipergrafe. Sprendimams pasiūloma keletas naujų metodų, taip pat pateikiami teoriškai ir praktiškai svarbūs algoritmai. Kai kurie rezultatai iliustruojami duomenimis iš realių tinklų. Antrojoje dalyje pristatomi rezultatai grafų su uždraustaisiais minorais tematikoje, nagrinėjamas atvejis kai uždraustieji minorai yra nejungūs. Čia tiriamas asimptotinis grafų, neturinčių k+1 nepriklausomų ciklų, skaičius, rezultatai apibendrinami grafų, neturinčių k+1 uždraustųjų minorų, tačiau tenkinančių tam tikrą „vėduoklės“ apribojimą, klasėms. Įrodoma, kad tipiniai tokių klasių grafai turi paprastą „k dydžio blokatoriaus“ struktūrą, nustatomos kitos tokių grafų asimptotinės savybės (jungumas, komponenčių skaičius, viršūnių laipsniai). Galiausiai parodoma, kad tipiniai grafai, neturintys k+1 nepriklausomų minorų K4 turi sudėtingesnę „2k+1 dydžio blokatoriaus“ struktūrą ir ištiriamos kitos jų savybės. Dalis šių rezultatų įrodoma daug bendresniu atveju. Darbe pasitelkiami įvairūs informatikos, kombinatorikos, grafų, tikimybių ir generuojančiųjų funkcijų teorijos metodai.
23
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.
24
Beis, Michail. "Greedy algorithms for random regular graphs." Thesis, University of Liverpool, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.427021.
Full text
25
Bode, Michel. "Random graphs on the hyperbolic plane." Thesis, University of Birmingham, 2016. http://etheses.bham.ac.uk//id/eprint/6526/.
Full textAbstract:
In this thesis, we study a recently proposed model of random graphs that exhibit properties which are present in a wide range of networks arising in real world settings. The model creates random geometric graphs on the hyperbolic plane, where vertices are connected if they are within a certain threshold distance. We study typical properties of these graphs. We identify two critical values for one of the parameters that act as sharp thresholds. The three resulting intervals of the parameters that correspond to three possible phases of the random structure: A.a.s., the graph is connected; A.a.s., the graph is not connected, yet there is a giant component; A.a.s., every component is of sublinear size. Furthermore, we determine the behaviour at the critical values. We also consider typical distances between vertices and show that the ultra-small world phenomenon is present. Our results imply that most pairs of vertices that belong to the giant component are within doubly logarithmic distance.
26
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
27
Fraiman, Nicolás. "Connectivity of random graphs and networks." Thesis, McGill University, 2013. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=119575.
Full textAbstract:
In this manuscript we discuss connectivity and distance properties for several models of random graphs. The results we prove generalize well known theorems for the Erdös-Rényi model and percolation on a finite box. We show that for both Inhomogeneous Random Graphs and Distance Fading Grid Networks there is a sharp transition for connectivity and we find the corresponding threshold values. We also provide a bound for the diameter for the Random Connection Model when the underlying space is the torus in d dimensions.Dans cette thèse, on étudie les propriétés de connexité pour plusieurs modèles de graphes aléatoires. Les résultats généralisent des théorèmes bien connus pour le modèle Erdös-Rényi et la percolation dans une boîte finie. On montre que pour les "Inhomogeneous Random Graphs" et les "Distance Fading Grid Networks", il y a un seuil pour la propriété de connexité et on trouve les valeurs des seuils correspondants. On caractérise aussi le diamètre pour le "Random Connection Model" quand l'espace est le tore de dimension d.
28
Sylvester, John A. "Random walks, effective resistance and neighbourhood statistics in binomial random graphs." Thesis, University of Warwick, 2017. http://wrap.warwick.ac.uk/106467/.
Full textAbstract:
The binomial random graph model G(n; p), along with its near-twin sibling G(n; m), were the starting point for the entire study of random graphs and even probabilistic combinatorics as a whole. The key properties of these models are woven into the fabric of the field and their behaviour serves as a benchmark to compare any other model of random structure. In this thesis we contribute to the already rich literature on G(n; p) in a number of directions. Firstly, vertex to vertex hitting times of random walks in G(n; p) are considered via their interpretation as potential differences in an electrical network. In particular we show that in a graph satisfying certain connectivity properties the effective resistance between two vertices is typically determined, up to lower order terms, by the degrees of these vertices. We apply this to obtain the expected values of hitting times and several related indices in G(n; p), and to prove that these values are concentrated around their mean. We then study the statistics of the size of the r-neighbourhood of a vertex in G(n; p). We show that the sizes of these neighbourhoods satisfy a central limit theorem. We also bound the probability a vertex in G(n; p) has an r-neighbourhood of size k from above and below by functions of n; p and k which match up to constants. Finally, in the last chapter the extreme values of the r-degree sequence are studied. We prove a novel neighbourhood growth estimate which states that with high probability the size of a vertex's r neighbourhood is determined, up to lower order terms, by the size of its first neighbourhood. We use this growth estimate to bound the number of vertices attaining a smallest r-neighbourhood.
29
Wallén, Daniel. "Cover times of random walks on graphs." Thesis, Uppsala University, Department of Mathematics, 2010. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-125278.
Full text
30
Kakarlapudi, Geetha. "Analysis of beacon triangulation in random graphs." Texas A&M University, 2004. http://hdl.handle.net/1969.1/1447.
Full textAbstract:
Our research focusses on the problem of finding nearby peers in the Internet.
We focus on one particular approach, Beacon Triangulation that is widely used to
solve the peer-finding problem. Beacon Triangulation is based on relative distances
of nodes to some special nodes called beacons. The scheme gives an error when a
new node that wishes to join the network has the same relative distance to two or
more nodes. One of the reasons for the error is that two or more nodes have the
same distance vectors. As a part of our research work, we derive the conditions to
ensure the uniqueness of distance vectors in any network given the shortest path
distribution of nodes in that network. We verify our analytical results for G(n, p)
graphs and the Internet. We also derive other conditions under which the error in the
Beacon Triangulation scheme reduces to zero. We compare the Beacon Triangulation
scheme to another well-known distance estimation scheme known as Global Network
Positioning (GNP).
31
Sbihi, Amine M. (Amine Mohammed). "Covering times for random walks on graphs." Thesis, McGill University, 1990. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=74538.
Full textAbstract:
This thesis is a contribution to the covering times problems for random walks on graphs. By considering uniform random walks on finite connected graphs, the covering time is defined as the time (number of steps) taken by the random walk to visit every vertex. The motivating problem of this thesis is to find bounds for the expected covering times. We provide explicit bounds that are uniformly valid over all starting points and over large classes of graphs. In some cases the asymptotic distribution of the suitably normalized covering time is given as well.
32
Müller, Tobias. "Random geometric graphs : colouring and related topics." Thesis, University of Oxford, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.437019.
Full text
33
Dowden, Christopher Thomas. "Uniform random planar graphs with degree constraints." Thesis, University of Oxford, 2008. http://ora.ox.ac.uk/objects/uuid:f8a9afe3-30ad-4672-9a6c-4fb9ac9af041.
Full textAbstract:
Random planar graphs have been the subject of much recent work. Many basic properties of the standard uniform random planar graph $P_{n}$, by which we mean a graph chosen uniformly at random from the set of all planar graphs with vertex set $ { 1,2, ldots, n }$, are now known, and variations on this standard random graph are also attracting interest. Prominent among the work on $P_{n}$ have been asymptotic results for the probability that $P_{n}$ will be connected or contain given components/ subgraphs. Such progress has been achieved through a combination of counting arguments cite{mcd} and a generating function approach cite{gim}. More recently, attention has turned to $P_{n,m}$, the graph taken uniformly at random from the set of all planar graphs on ${ 1,2, ldots, n }$ with exactly $m(n)$ edges (this can be thought of as a uniform random planar graph with a constraint on the average degree). In cite{ger} and cite{gim}, the case when $m(n) =~!lfloor qn floor$ for fixed $q in (1,3)$ has been investigated, and results obtained for the events that $P_{n, lfloor qn floor}$ will be connected and that $P_{n, lfloor qn floor}$ will contain given subgraphs. In Part I of this thesis, we use elementary counting arguments to extend the current knowledge of $P_{n,m}$. We investigate the probability that $P_{n,m}$ will contain given components, the probability that $P_{n,m}$ will contain given subgraphs, and the probability that $P_{n,m}$ will be connected, all for general $m(n)$, and show that there is different behaviour depending on which `region' the ratio $rac{m(n)}{n}$ falls into. In Part II, we investigate the same three topics for a uniform random planar graph with constraints on the maximum and minimum degrees.
34
Gao, Rong. "Some colouring problems for Pseudo-Random Graphs." Thesis, University of Essex, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.494355.
Full text
35
Fastlund, Niklas. "The subgraph containment problem in random graphs." Thesis, Uppsala universitet, Algebra och geometri, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-260377.
Full text
36
Folz, Matthew Bryan. "Adapted metrics and random walks on graphs." Thesis, University of British Columbia, 2013. http://hdl.handle.net/2429/44947.
Full textAbstract:
This thesis discusses various aspects of continuous-time simple random walks on measure weighted graphs, with a focus on behaviors related to large-scale geometric properties of the underlying graph. In contrast to previous work in this area, the majority of the results presented here are applicable to random walks with unbounded generators. A recurring theme in this research is the use of novel distance functions for graphs known as adapted metrics, which are demonstrated to be a powerful tool for studying random walks on graphs.
Chapter 2 provides an overview of the relevant probabilistic and analytic theory, and provides multiple constructions of the heat kernel and a brief introduction to the theory of Dirichlet forms. Chapter 3 introduces adapted metrics, which play a central role in the following chapters, and which are especially useful in understanding random walks with unbounded generators. Chapter 4 discusses heat kernel estimates, and presents an overview of on-diagonal heat kernel estimates for graphs, as well as techniques for obtaining various off-diagonal estimates of the heat kernel. The off-diagonal estimates were proved by the author, and are notable for their use of adapted metrics. Chapter 5 introduces metric graphs, a continuous analogue of graphs which possess many desirable analytic properties, and analyzes the problem of constructing a Brownian motion on a metric graph which behaves similarly to a given continuous-time simple random walk. Chapter 6 analyzes recurrence and transience of graphs, and proves an original estimate relating adapted volume growth to recurrence of graphs. Chapter 7 discusses bounds for the bottom of the essential spectrum in terms of geometric inequalities such as volume growth estimates and isoperimetric inequalities. The main result of this chapter was proved by the author, and establishes sharp estimates for the bottom of the spectrum in terms of the adapted volume growth. Chapter 8 considers stochastic completeness of graphs and proves sharp criteria relating volume growth to stochastic completeness. The results of this chapter were proved by the author, using the machinery of metric graphs.
37
Suen, W. C. S. "Flows, cliques and paths in random graphs." Thesis, University of Bristol, 1985. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.354470.
Full text
38
Cerqueira, Andressa. "Statistical inference on random graphs and networks." Universidade de São Paulo, 2018. http://www.teses.usp.br/teses/disponiveis/45/45133/tde-04042018-094802/.
Full textAbstract:
In this thesis we study two probabilistic models defined on graphs: the Stochastic Block model and the Exponential Random Graph. Therefore, this thesis is divided in two parts. In the first part, we introduce the Krichevsky-Trofimov estimator for the number of communities in the Stochastic Block Model and prove its eventual almost sure convergence to the underlying number of communities, without assuming a known upper bound on that quantity. In the second part of this thesis we address the perfect simulation problem for the Exponential random graph model. We propose an algorithm based on the Coupling From The Past algorithm using a Glauber dynamics. This algorithm is efficient in the case of monotone models. We prove that this is the case for a subset of the parametric space. We also propose an algorithm based on the Backward and Forward algorithm that can be applied for monotone and non monotone models. We prove the existence of an upper bound for the expected running time of both algorithms.Nessa tese estudamos dois modelos probabilísticos definidos em grafos: o modelo estocástico por blocos e o modelo de grafos exponenciais. Dessa forma, essa tese está dividida em duas partes. Na primeira parte nós propomos um estimador penalizado baseado na mistura de Krichevsky-Trofimov para o número de comunidades do modelo estocástico por blocos e provamos sua convergência quase certa sem considerar um limitante conhecido para o número de comunidades. Na segunda parte dessa tese nós abordamos o problema de simulação perfeita para o modelo de grafos aleatórios Exponenciais. Nós propomos um algoritmo de simulação perfeita baseado no algoritmo Coupling From the Past usando a dinâmica de Glauber. Esse algoritmo é eficiente apenas no caso em que o modelo é monotóno e nós provamos que esse é o caso para um subconjunto do espaço paramétrico. Nós também propomos um algoritmo de simulação perfeita baseado no algoritmo Backward and Forward que pode ser aplicado à modelos monótonos e não monótonos. Nós provamos a existência de um limitante superior para o número esperado de passos de ambos os algoritmos.
39
Parikh, Nidhi Kiranbhai. "Generating Random Graphs with Tunable Clustering Coefficient." Thesis, Virginia Tech, 2011. http://hdl.handle.net/10919/31591.
Full textAbstract:
Most real-world networks exhibit a high clustering coefficientâ the probability that two neighbors
of a node are also neighbors of each other. We propose four algorithms CONF-1, CONF-2,
THROW-1, and THROW-2 which are based on the configuration model and that take triangle degree
sequence (representing the number of triangles/corners at a node) and single-edge degree sequence
(representing the number of single-edges/stubs at a node) as input and generate a random graph
with a tunable clustering coefficient. We analyze them theoretically and empirically for the case of
a regular graph. CONF-1 and CONF-2 generate a random graph with the degree sequence and the
clustering coefficient anticipated from the input triangle and single-edge degree sequences. At each
time step, CONF-1 chooses each node for creating triangles or single edges with the same probability,
while CONF-2 chooses a node for creating triangles or single edge with a probability proportional
to their number of unconnected corners or unconnected stubs, respectively. Experimental results
match quite well with the anticipated clustering coefficient except for highly dense graphs, in which
case the experimental clustering coefficient is higher than the anticipated value. THROW-2 chooses
three distinct nodes for creating triangles and two distinct nodes for creating single edges, while
they need not be distinct for THROW-1. For THROW-1 and THROW-2, the degree sequence and the
clustering coefficient of the generated graph varies from the input. However, the expected degree
distribution, and the clustering coefficient of the generated graph can also be predicted using analytical
results. Experiments show that, for THROW-1 and THROW-2, the results match quite well with
the analytical results. Typically, only information about degree sequence or degree distribution is
available. We also propose an algorithm DEG that takes degree sequence and clustering coefficient
as input and generates a graph with the same properties. Experiments show results for DEG that
are quite similar to those for CONF-1 and CONF-2.Master of Science
40
Anthapadmanabhan, Nagaraj Prasanth. "Random codes and graphs for secure communication." College Park, Md.: University of Maryland, 2009. http://hdl.handle.net/1903/9293.
Full textAbstract:
Thesis (Ph. D.) -- University of Maryland, College Park, 2009.Thesis research directed by: Dept. of Electrical and Computer Engineering. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.
41
Brody, Justin. "On the model theory of random graphs." College Park, Md. : University of Maryland, 2009. http://hdl.handle.net/1903/9291.
Full textAbstract:
Thesis (Ph.D.) -- University of Maryland, College Park, 2009.Thesis research directed by: Dept. of Mathematics. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.
42
Andersson, Evelina. "Random sampling of finite graphs with constraints." Thesis, Uppsala universitet, Algebra och geometri, 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-219764.
Full text
43
Hardy, Bradley. "Heuristic methods for colouring dynamic random graphs." Thesis, Cardiff University, 2018. http://orca.cf.ac.uk/109385/.
Full textAbstract:
Many real-world operational research problems can be reformulated into static graph colouring problems. However, such problems might be better represented as dynamic graphs if their size and/or constraints change over time. In this thesis, we explore heuristics approaches for colouring dynamic random graphs. We consider two di�erent types of dynamic graph: edge dynamic and vertex dynamic. We also consider two di�erent change scenarios for each of these dynamic graph types: without future change information (i. e. random change) and with probabilistic future change information. By considering a dynamic graph as a series of static graphs, we propose a �modi �cation approach� which modi�es a feasible colouring (or solution) for the static representation of a dynamic graph at one time-step into a colouring for the subsequent time-step. In almost all cases, this approach is bene�cial with regards to either improving quality or reducing computational e�ort when compared against using a static graph colouring approach for each time-step independently. In fact, for test instances with small amounts of change between time-steps, this approach can be bene�cial with regards to both quality and computational e�ort When probabilistic future change information is available, we propose a �twostage approach� which �rst attempts to identify a feasible colouring for the current time-step using our �modi�cation approach�, and then attempts to increase the robustness of the colouring with regards to potential future changes. For both the edge and vertex dynamic cases, this approach was shown to decrease the �problematic� change introduced between time-steps. A clear trade-o� can be observed between the quality of a colouring and its potential robustness, such that a colouring with more colours (i. e. reduced quality) can be made more robust.
44
Xu, Keyulu. "Graph structures, random walks, and all that : learning graphs with jumping knowledge networks." Thesis, Massachusetts Institute of Technology, 2019. https://hdl.handle.net/1721.1/121660.
Full textAbstract:
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2019
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 51-54).
Graph representation learning aims to extract high-level features from the graph structures and node features, in order to make predictions about the nodes and the graphs. Applications include predicting chemical properties of drugs, community detection in social networks, and modeling interactions in physical systems. Recent deep learning approaches for graph representation learning, namely Graph Neural Networks (GNNs), follow a neighborhood aggregation procedure, where the representation vector of a node is computed by recursively aggregating and transforming feature vectors of its neighboring nodes. We analyze some important properties of these models, and propose a strategy to overcome the limitations. In particular, the range of neighboring nodes that a node's representation draws from strongly depends on the graph structure, analogous to the spread of a random walk. To adapt to local neighborhood properties and tasks, we explore an architecture - jumping knowledge (JK) networks that flexibly leverages, for each node, different neighborhood ranges to enable better structure-aware representation. In a number of experiments on social, bioinformatics and citation networks, we demonstrate that our model achieves state-of-the-art performance. Furthermore, combining the JK framework with models like Graph Convolutional Networks, GraphSAGE and Graph Attention Networks consistently improves those models' performance.
by Keyulu Xu.
S.M.
S.M. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science
45
Dartois, Stephane. "Random Tensor models : Combinatorics, Geometry, Quantum Gravity and Integrability." Thesis, Sorbonne Paris Cité, 2015. http://www.theses.fr/2015USPCD104/document.
Full textAbstract:
Dans cette thèse nous explorons différentes facettes des modèles de tenseurs aléatoires. Les modèles de tenseurs aléatoires ont été introduits en physique dans le cadre de l'étude de la gravité quantique. En effet les modèles de matrices aléatoires, qui sont un cas particuliers de modèles de tenseurs, en sont une des origines. Ces modèles de matrices sont connus pour leur riche combinatoire et l'incroyable diversité de leurs propriétés qui les font toucher tous les domaines de l'analyse, la géométrie et des probabilités. De plus leur étude par les physiciens ont prouvé leur efficacité en ce qui concerne l'étude de la gravité quantique à deux dimensions. Les modèles de tenseurs aléatoires incarnent une généralisation possible des modèles de matrices. Comme leurs cousins, les modèles de matrices, ils posent questions dans les domaines de la combinatoire (comment traiter les cartes combinatoires d dimensionnelles ?), de la géométrie (comment contrôler la géométrie des triangulations générées ?) et de la physique (quel type d'espace-temps produisent-ils ? Quels sont leurs différentes phases ?). Cette thèse espère établir des pistes ainsi que des techniques d'études de ces modèles. Dans une première partie nous donnons une vue d'ensemble des modèles de matrices. Puis, nous discutons la combinatoire des triangulations en dimensions supérieures ou égales à trois en nous concentrant sur le cas tridimensionnelle (lequel est plus simple à visualiser). Nous définissons ces modèles et étudions certaines de leurs propriétés à l'aide de techniques combinatoires permettant de traiter les cartes d dimensionnelles. Enfin nous nous concentrons sur la généralisation de techniques issues des modèles de matrices dans le cas d'une famille particulières de modèles de tenseurs aléatoires. Ceci culmine avec le dernier chapitre de la thèse donnant des résultats partiels concernant la généralisation de la récurrence topologique de Eynard et Orantin à cette famille de modèles de tenseursIn this thesis manuscript we explore different facets of random tensor models. These models have been introduced to mimic the incredible successes of random matrix models in physics, mathematics and combinatorics. After giving a very short introduction to few aspects of random matrix models and recalling a physical motivation called Group Field Theory, we start exploring the world of random tensor models and its relation to geometry, quantum gravity and combinatorics. We first define these models in a natural way and discuss their geometry and combinatorics. After these first explorations we start generalizing random matrix methods to random tensors in order to describes the mathematical and physical properties of random tensor models, at least in some specific cases
46
Wang, Yang. "Use of finite random graphs to model packet radio networks." Ohio : Ohio University, 1990. http://www.ohiolink.edu/etd/view.cgi?ohiou1183474696.
Full text
47
Kartun-Giles, Alexander Paul. "Connectivity and centrality in dense random geometric graphs." Thesis, University of Bristol, 2017. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.720827.
Full text
48
Kohayakawa, Yoshiharu. "Extremal combinatorics and the evolution of random graphs." Thesis, University of Cambridge, 1990. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.335739.
Full text
49
Lim, Kim-Huat. "Modelling epidemics via empirical measures and random graphs." Thesis, University of Oxford, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.445786.
Full text
50
Atkin, Max R. "Applications of random graphs to 2D quantum gravity." Thesis, University of Oxford, 2011. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.598036.
Full textAbstract:
The central topic of this thesis is two dimensional Quantum Gravity and its properties. The term Quantum Gravity itself is ambiguous as there are many proposals for its correct formulation and none of them have been verified experimentally. In this thesis we consider a number of closely related approaches to two dimensional quantum gravity that share the property that they may be formulated in terms of random graphs. In one such approach known as Causal Dynamical Triangulations, numerical computations suggest an interesting phenomenon in which the effective spacetime dimension is reduced in t he UV. In this thesis we first address whether such a dynamical reduction in the number of dimensions may be understood in a simplified model. vVe introduce a continuum limit where t his simplified model exhibits a reduction in the effective dimension of spacetime in the UV, in addition to having rich cross-over behaviour. In the second part of this thesis we consider an approach closely related to causal dynamical triangu lation; namely dynamical triangulation. Although this theory is less well-behaved than causal dynamical triangulation) it is known how to couple it to matter) t herefore allowing for potentially multiple boundary states to appear in the theory. We address t he conjecture of Seiberg and Shih which states that all these boundary states are degenerate and may be constructed from a single principal boundary state. By use of the random graph formulation of the theory we compute the higher genus amplitudes with a single boundary and find that they violate the Seiberg-Shih conjecture. Finally we discuss whether this result prevents the replacement of boundary states by local operators as proposed by Seiberg.