To see the other types of publications on this topic, follow the link: Random Graph.
Dissertations / Theses on the topic 'Random Graph'
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 Graph.'
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
Makai, Tamas. "Random graph processes." Thesis, Royal Holloway, University of London, 2012. http://repository.royalholloway.ac.uk/items/b24b89af-3fc1-4d2f-a673-64483a3bc2f2/8/.
Full textAbstract:
This thesis deals with random graph processes. More precisely it deals with two random graph processes which create H -free graphs. The first of these processes is the random H-elimination process which starts from the complete graph and in every step removes an edge uniformly at random from the set of edges which are found in a copy of H. The second is the H-free random graph process which starts from the empty graph and in every step an edge chosen uniformly at random from the set of edges which when added to the graph would not create a copy of H is inserted. We consider these graph processes for several classes of graphs H, for example strictly two balanced graphs. The class of strictly two balanced graphs includes among others cycles and complete graphs. We analysed the H-elimination process, when H is strictly 2-balanced. For this class we show the typical number of edges found at the end of the process. We also consider the sub graphs created by the process and its independence number. We also managed to show the expected number of edges in the H -elimination pro- cess when H = Ki, the graph created from the complete graph on 4 vertices by removing an edge and when H = K34 where K34 is created from the complete bi- partite graph with 3 vertices in one partition and'4 vertices in the second partition, by removing an edge. In case of the H -free process we considered the case when H is the triangle and showed that the triangle-free random graph process only creates sparse subgraphs. Finally we have improved the lower bound on the length of the K34-free random graph process. '
4
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
5
Roberts, Ekaterina Sergeevna. "Tailored random graph ensembles." Thesis, King's College London (University of London), 2014. https://kclpure.kcl.ac.uk/portal/en/theses/tailored-random-graph-ensembles(daefc925-24a3-4f7f-8c79-21b9136c636b).html.
Full textAbstract:
Tailored graph ensembles are a developing bridge between statistical mechanics and biological networks. In this thesis, this concept is used to generate a suite of rigorous mathematical tools to quantify and compare the topology of cellular signalling networks. Earlier published results to quantify the entropy of constrained random graph ensembles are extended by looking at constraints relating to directed graphs, bipartite graphs, neighbourhood compositions and generalised degrees. To incorporate constraints relating to the average number of short loops, a number of innovative techniques are reviewed and extended, moving the analysis beyond the usual tree-like assumption. The generation of unbiased sample networks under some of these new constraints is studied. A series of illustrations of how these concepts may be applied to systems biology are developed. Topological observables are obtained from real biological networks and the entropy of the associated random graph ensemble is calculated. Certain studies on over-represented motifs are replicated and the influence of the choice of null model is considered. The correlation between the topological role of each protein and its lethality is studied in yeast. Throughout, this document aims to promote looking at a network as a realisation satisfying certain constraints rather than just as a list of nodes and edges. This may initially seem to be an abstract approach, but it is in fact a more natural viewpoint within which to consider many fundamental questions regarding the origin, function and design of observed real networks.
6
Warnke, Lutz. "Random graph processes with dependencies." Thesis, University of Oxford, 2012. http://ora.ox.ac.uk/objects/uuid:71b48e5f-a192-4684-a864-ea9059a25d74.
Full textAbstract:
Random graph processes are basic mathematical models for large-scale networks evolving over time. Their systematic study was pioneered by Erdös and Rényi around 1960, and one key feature of many 'classical' models is that the edges appear independently. While this makes them amenable to a rigorous analysis, it is desirable, both mathematically and in terms of applications, to understand more complicated situations. In this thesis the main goal is to improve our rigorous understanding of evolving random graphs with significant dependencies. The first model we consider is known as an Achlioptas process: in each step two random edges are chosen, and using a given rule only one of them is selected and added to the evolving graph. Since 2000 a large class of 'complex' rules has eluded a rigorous analysis, and it was widely believed that these could give rise to a striking and unusual phenomenon. Making this explicit, Achlioptas, D'Souza and Spencer conjectured in Science that one such rule yields a very abrupt (discontinuous) percolation phase transition. We disprove this, showing that the transition is in fact continuous for all Achlioptas process. In addition, we give the first rigorous analysis of the more 'complex' rules, proving that certain key statistics are tightly concentrated (i) in the subcritical evolution, and (ii) also later on if an associated system of differential equations has a unique solution. The second model we study is the H-free process, where random edges are added subject to the constraint that they do not complete a copy of some fixed graph H. The most important open question for such 'constrained' processes is due to Erdös, Suen and Winkler: in 1995 they asked what the typical final number of edges is. While Osthus and Taraz answered this in 2000 up to logarithmic factors for a large class of graphs H, more precise bounds are only known for a few special graphs. We close this gap for the cases where a cycle of fixed length is forbidden, determining the final number of edges up to constants. Our result not only establishes several conjectures, it is also the first which answers the more than 15-year old question of Erdös et. al. for a class of forbidden graphs H.
7
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
8
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
9
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
10
Cooper, Jeffrey R. "Product Dimension of a Random Graph." Miami University / OhioLINK, 2010. http://rave.ohiolink.edu/etdc/view?acc_num=miami1272038833.
Full text
11
Horn, Paul Kenneth. "Random subgraphs of a given graph." Diss., [La Jolla] : University of California, San Diego, 2009. http://wwwlib.umi.com/cr/ucsd/fullcit?p3355765.
Full textAbstract:
Thesis (Ph. D.)--University of California, San Diego, 2009.Title from first page of PDF file (viewed June 25, 2009). Available via ProQuest Digital Dissertations. Vita. Includes bibliographical references (p. 91-94).
12
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.
13
Song, Linlin. "Random graph models for wireless communication networks." Thesis, Queen Mary, University of London, 2010. http://qmro.qmul.ac.uk/xmlui/handle/123456789/426.
Full textAbstract:
This thesis concerns mathematical models of wireless communication networks, in particular ad-hoc networks and 802:11 WLANs. In ad-hoc mode each of these devices may function as a sender, a relay or a receiver. Each device may only communicate with other devices within its transmission range. We use graph models for the relationship between any two devices: a node stands for a device, and an edge for a communication link, or sometimes an interference relationship. The number of edges incident on a node is the degree of this node. When considering geometric graphs, the coordinates of a node give the geographical position of a node. One of the important properties of a communication graph is its connectedness | whether all nodes can reach all other nodes. We use the term connectivity, the probability of graphs being connected given the number of nodes and the transmission range to measure the connectedness of a wireless network. Connectedness is an important prerequisite for all communication networks which communication between nodes. This is especially true for wireless ad-hoc networks, where communication relies on the contact among nodes and their neighbours. Another important property of an interference graph is its chromatic number | the minimum number of colours needed so that no adjacent nodes are assigned the same colour. Here adjacent nodes share an edge; adjacent edges share at least one node; and colours are used to identify di erent frequencies. This gives the minimum number of frequencies a network needs in order to attain zero interference. This problem can be solved as an optimization problem deterministically, but is algorithmically NP-hard. Hence, nding good asymptotic approximations for this value becomes important. Random geometric graphs describe an ensemble of graphs which share common features. In this thesis, node positions follow a Poisson point process or a binomial point process. We use probability theory to study the connectedness of random graphs and random geometric graphs, which is the fraction of connected graphs among many graph samples. This probability is closely related to the property of minimum node degree being at least unity. The chromatic number is closely related to the maximum degree as n ! 1; the chromatic number converges to maximum degree when graph is sparse. We test existing theorems and improve the existing ones when possible. These motivated me to study the degree of random (geometric) graph models. We study using deterministic methods some degree-related problems for Erda}os-R enyi random graphs G(n; p) and random geometric graphs G(n; r). I provide both theoretical analysis and accurate simulation results. The results lead to a study of dependence or non-dependence in the joint distribution of the degrees of neighbouring nodes. We study the probability of no node being isolated in G(n; p), that is, minimum node degree being at least unity. By making the assumption of non-dependence of node degree, we derive two asymptotics for this probability. The probability of no node being isolated is an approximation to the probability of the graph being connected. By making an analogy to G(n; p), we study this problem for G(n; r), which is a more realistic model for wireless networks. Experiment shows that this asymptotic result also works well for small graphs. We wish to nd the relationship between these basic features the above two important problems of wireless networks: the probability of a network being connected and the minimum number of channels a network needs in order to minimize interference. Inspired by the problem of maximum degree in random graphs, we study the problem of the maximum of a set of Poisson random variables and binomial random variables, which leads to two accurate formulae for the mode of the maximum for general random geometric graphs and for sparse random graphs. To our knowledge, these are the best results for sparse random geometric graphs in the literature so far. By approximating the node degrees as independent Poisson or binomial variables, we apply the result to the problem of maximum degree in general and sparse G(n; r), and derived much more accurate results than in the existing literature. Combining the limit theorem from Penrose and our work, we provide good approximations for the mode of the clique number and chromatic number in sparse G(n; r). Again these results are much more accurate than existing ones. This has implications for the interference minimization of WLANs. Finally, we apply our asymptotic result based on Poisson distribution for the chromatic number of random geometric graph to the interference minimization problem in IEEE 802:11b/g WLAN. Experiments based on the real planned position of the APs in WLANs show that our asymptotic results estimate the minimum number of channels needed accurately. This also means that sparse random geometric graphs are good models for interference minimization problem of WLANs. We discuss the interference minimization problem in single radio and multi-radio wireless networking scenarios. We study branchand- bound algorithms for these scenarios by selecting di erent constraint functions and objective functions.
14
Yeo, Dominic. "Self-organised criticality in random graph processes." Thesis, University of Oxford, 2016. https://ora.ox.ac.uk/objects/uuid:23af1abc-2128-4315-9b25-55ed8f290875.
Full textAbstract:
In the first half of this thesis, we study the random forest obtained by conditioning the Erdös-Rényi random graph G(N,p) to include no cycles. We focus on the critical window, in which | p(N) = | 1+λN-1/3 |
| N |
15
Duxbury, Scott W. "Diagnosing Multicollinearity in Exponential Random Graph Models." The Ohio State University, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=osu1491393848069144.
Full text
16
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
17
Achlioptas, Demetrios. "Threshold phenomena in random graph colouring and satisfiability." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape7/PQDD_0002/NQ41090.pdf.
Full text
18
Biswas, Amartya Shankha. "Local-access generators for basic random graph models." Thesis, Massachusetts Institute of Technology, 2018. http://hdl.handle.net/1721.1/119600.
Full textAbstract:
Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018.Cataloged from PDF version of thesis.
Includes bibliographical references (pages 61-64).
Consider a computation on a massive random graph: Does one need to generate the whole random graph up front, prior to performing the computation? Or, is it possible to provide an oracle to answer queries to the random graph "on-the-fly" in a much more efficient manner overall? That is, to provide a local access generator which incrementally constructs the random graph locally, at the queried portions, in a manner consistent with the random graph model and all previous choices. Local access generators can be useful when studying the local behavior of specific random graph models. Our goal is to design local access generators whose required resource overhead for answering each query is significantly more efficient than generating the whole random graph. Our results focus on undirected graphs with independent edge probabilities, that is, each edge is chosen as an independent Bernoulli random variable. We provide a general implementation for generators in this model. Then, we use this construction to obtain the first efficient local implementations for the Erdös-Rényi G(n, p) model, and the Stochastic Block model. As in previous local-access implementations for random graphs, we support VERTEX-PAIR, NEXT-NEIGHBOR queries, and ALL-NEIGHBORS queries. In addition, we introduce a new RANDOM-NEIGHBOR query. We also give the first local-access generation procedure for ALL-NEIGHBORS queries in the (sparse and directed) Kleinberg's Small-World model. Note that, in the sparse case, an ALL-NEIGHBORS query can be used to simulate the other types of queries efficiently. All of our generators require no pre-processing time, and answer each query using O(poly(log n)) time, random bits, and additional space.
by Amartya Shankha Biswas.
M. Eng.
19
Abdullah, Mohammed. "The cover time of random walks on graph." Thesis, King's College London (University of London), 2012. https://kclpure.kcl.ac.uk/portal/en/theses/the-cover-time-of-random-walks-on-graph(c23c303f-a6a2-4489-a059-4ade7c118106).html.
Full textAbstract:
A simple random walk on a graph is a sequence of movements from one vertex to another where at each step an edge is chosen uniformly at random from the set of edges incident on the current vertex, and then transitioned to next vertex. Central to this thesis is the cover time of the walk, that is, the expectation of the number of steps required to visit every vertex, maximised over all starting vertices. In our rst contribution, we establish a relation between the cover times of a pair of graphs, and the cover time of their Cartesian product. This extends previous work on special cases of the Cartesian product, in particular, the square of a graph. We show that when one of the factors is in some sense larger than the other, its cover time dominates, and can become within a logarithmic factor of the cover time of the product as a whole. Our main theorem eectively gives conditions for when this holds. The techniques and lemmas we introduce may be of independent interest. In our second contribution, we determine the precise asymptotic value of the cover time of a random graph with given degree sequence. This is a graph picked uniformly at random from all simple graphs with that degree sequence. We also show that with high probability, a structural property of the graph called conductance, is bounded below by a constant. This is of independent interest. Finally, we explore random walks with weighted random edge choices. We present a weighting scheme that has a smaller worst case cover time than a simple random walk. We give an upper bound for a random graph of given degree sequence weighted according to our scheme. We demonstrate that the speed-up (that is, the ratio of cover times) over a simple random walk can be unbounded.
20
Kruzick, Stephen M. "Optimal Graph Filter Design for Large-Scale Random Networks." Research Showcase @ CMU, 2018. http://repository.cmu.edu/dissertations/1165.
Full textAbstract:
Graph signal processing analyzes signals supported on the nodes of a network with respect to a shift operator matrix that conforms to the graph structure. For shift-invariant graph filters, which are polynomial functions of the shift matrix, the filter response is defined by the value of the filter polynomial at the shift matrix eigenvalues. Thus, information regarding the spectral decomposition of the shift matrix plays an important role in filter design. However, under stochastic conditions leading to uncertain network structure, the eigenvalues of the shift matrix become random, complicating the filter design task. In such case, empirical distribution functions built from the random matrix eigenvalues may exhibit deterministic limiting behavior that can be exploited for problems on large-scale random networks. Acceleration filters for distributed average consensus dynamics on random networks provide the application covered in this thesis work. The thesis discusses methods from random matrix theory appropriate for analyzing adjacency matrix spectral asymptotics for both directed and undirected random networks, introducing relevant theorems. Network distribution properties that allow computational simplification of these methods are developed, and the methods are applied to important classes of random network distributions. Subsequently, the thesis presents the main contributions, which consist of optimization problems for consensus acceleration filters based on the obtained asymptotic spectral density information. The presented methods cover several cases for the random network distribution, including both undirected and directed networks as well as both constant and switching random networks. These methods also cover two related optimization objectives, asymptotic convergence rate and graph total variation.
21
Malen, Greg. "The Topology of Random Flag and Graph Homomorphism Complexes." The Ohio State University, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=osu1461279333.
Full text
22
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.
23
Broutin, Nicolas. "Shedding new light on random trees." Thesis, McGill University, 2007. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=102963.
Full textAbstract:
We introduce a weighted model of random trees and analyze the asymptotic properties of their heights. Our framework encompasses most trees of logarithmic height that were introduced in the context of the analysis of algorithms or combinatorics. This allows us to state a sort of "master theorem" for the height of random trees, that covers binary search trees (Devroye, 1986), random recursive trees (Devroye, 1987; Pittel, 1994), digital search trees (Pittel, 1985), scale-free trees (Pittel, 1994; Barabasi and Albert, 1999), and all polynomial families of increasing trees (Bergeron et al., 1992; Broutin et al., 2006) among others. Other applications include the shape of skinny cells in geometric structures like k-d and relaxed k-d trees.This new approach sheds new light on the tight relationship between data structures like trees and tries that used to be studied separately. In particular, we show that digital search trees and the tries built from sequences generated by the same memoryless source share the same stable core. This link between digital search trees and tries is at the heart of our analysis of heights of tries. It permits us to derive the height of several species of tries such as the trees introduced by de la Briandais (1959) and the ternary search trees of Bentley and Sedgewick (1997).
The proofs are based on the theory of large deviations. The first order terms of the asymptotic expansions of the heights are geometrically characterized using the Crame'r functions appearing in estimates of the tail probabilities for sums of independent random variables.
24
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
25
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.
26
Eslava, Fernández Laura. "The rank of symmetric random matrices via a graph process." Thesis, McGill University, 2013. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=114602.
Full textAbstract:
Random matrix theory comprises a broad range of topics and avenues of research, one of them being to understand the probability of singularity for discrete random matrices. This is a fundamental, basic question about discrete matrices. Although is been proven that for random symmetric Bernoulli matrices the probability of singularity decays at least polynomially in the size of the matrix, it is conjectured that the right order of decay is exponential. We are interested in the adjacency matrix Q of the Erdos-Réyni random graph and we study the statistics of the rank of Q as a means of understanding the probability of singularity of Q. We take a stochastic process perspective, looking at the family of matrices Q (parametrized by p) as an increasing family of random matrices. We then investigate the structure of Q at the moment that it becomes non-singular and prove that, similar to some monotone properties of random graphs, the property of being non-singular obeys a so-called 'hitting time theorem'. Broadly speaking, this means that all-zero rows, which are a 'local' property of the matrix, are the only obstruction for non-singularity. This fact, which is the main novel contribution to the thesis, extends previous work by Costello and Vu.La théorie des matrices aléatoires a un large éventail de sujets et de pistes de recherche, l'un d'entre eux étant de comprendre la probabilité de la singularité des matrices aléatoires discrètes. Ca a été prouvé que pour des matrices aléatoires de Bernoulli symétriques la probabilité de singularité a des bornes polynomiales, mais la conjecture est que le bon ordre de décroissance est exponentiel. Nous sommes intéressés par la matrice d'adjacence Q du graphe aléatoire d'Erdos et Réyni et nous étudions les statistiques du rang de Q comme un moyen de comprende la probabilité de singularité de Q. Nous proposons maintenant une perspective de processus stochastique. Dans ce mémoire, nous considérons la famille Q comme une famille croissante de matrices aléatoires et nous étudions la structure de Q au moment oú il devient non singulière et nous prouvons de la même facon pour certaines propriétés monotones des graphes aléatoires, la propriété d'être non singulière obéit à soi-disant 'théorème de temps d'arrêt'. D'une manière globale, cela signifie que les lignes remplies de zéros, qui sont une propriété locale de la matrice, sont la seule obstruction pour la non-singularité. Ce fait, qui est la nouvelle contribution principale de ce mémoire, élargie les résultats antérieurs de Costello et Vu.
27
Bejan, Andrei Iu. "Inference and experimental design for percolation and random graph models." Thesis, Heriot-Watt University, 2010. http://hdl.handle.net/10399/2341.
Full textAbstract:
The problem of optimal arrangement of nodes of a random weighted graph is studied in this thesis. The nodes of graphs under study are fixed, but their edges are random and established according to the so called edge-probability function. This function is assumed to depend on the weights attributed to the pairs of graph nodes (or distances between them) and a statistical parameter. It is the purpose of experimentation to make inference on the statistical parameter and thus to extract as much information about it as possible. We also distinguish between two different experimentation scenarios: progressive and instructive designs. We adopt a utility-based Bayesian framework to tackle the optimal design problem for random graphs of this kind. Simulation based optimisation methods, mainly Monte Carlo and Markov Chain Monte Carlo, are used to obtain the solution. We study optimal design problem for the inference based on partial observations of random graphs by employing data augmentation technique. We prove that the infinitely growing or diminishing node configurations asymptotically represent the worst node arrangements. We also obtain the exact solution to the optimal design problem for proximity graphs (geometric graphs) and numerical solution for graphs with threshold edge-probability functions. We consider inference and optimal design problems for finite clusters from bond percolation on the integer lattice Zd and derive a range of both numerical and analytical results for these graphs. We introduce inner-outer plots by deleting some of the lattice nodes and show that the ‘mostly populated’ designs are not necessarily optimal in the case of incomplete observations under both progressive and instructive design scenarios. Finally, we formulate a problem of approximating finite point sets with lattice nodes and describe a solution to this problem.
28
Ye, Jiacheng. "Computing Exact Bottleneck Distance on Random Point Sets." Thesis, Virginia Tech, 2020. http://hdl.handle.net/10919/98669.
Full textAbstract:
Given a complete bipartite graph on two sets of points containing n points each, in a bottleneck matching problem, we want to find an one-to-one correspondence, also called a matching, that minimizes the length of its largest edge; the length of an edge is simply the Euclidean distance between its end-points. As an application, consider matching taxis to requests while minimizing the largest distance between any request to its matched taxi. The length of the largest edge (also called the bottleneck distance) has numerous applications in machine learning as well as topological data analysis. One can use the classical Hopcroft-Karp (HK-) Algorithm to find the bottleneck matching. In this thesis, we consider the case where A and B are points that are generated uniformly at random from a unit square. Instead of the classical HK-Algorithm, we implement and empirically analyze a new algorithm by Lahn and Raghvendra (Symposium on Computational Geometry, 2019). Our experiments show that our approach outperforms the HK-Algorithm based approach for computing bottleneck matching.Master of Science
Consider the problem of matching taxis to an equal number of requests. While matching them, one objective is to minimize the largest distance between a request and its match. Finding such a matching is called the bottleneck matching problem. In addition, this optimization problem arises in topological data analysis as well as machine learning. In this thesis, I conduct an empirical analysis of a new algorithm, which is called the FAST-MATCH algorithm, to find the bottleneck matching. I find that, when a large input data is randomly generated from a unit square, the FAST-MATCH algorithm performs substantially faster than the classical methods
29
Kong, Nayeong. "Convergence Rates of Spectral Distribution of Random Inner Product Kernel Matrices." Diss., Temple University Libraries, 2018. http://cdm16002.contentdm.oclc.org/cdm/ref/collection/p245801coll10/id/498132.
Full textAbstract:
MathematicsPh.D.
This dissertation has two parts. In the first part, we focus on random inner product kernel matrices. Under various assumptions, many authors have proved that the limiting empirical spectral distribution (ESD) of such matrices A converges to the Marchenko- Pastur distribution. Here, we establish the corresponding rate of convergence. The strategy is as follows. First, we show that for z = u + iv ∈ C, v > 0, the distance between the Stieltjes transform m_A (z) of ESD of matrix A and Machenko-Pastur distribution m(z) is of order O (log n \ nv). Next, we prove the Kolmogorov distance between ESD of matrix A and Marchenko-Pastur distribution is of order O(3\log n\n). It is the less sharp rate for much more general class of matrices. This uses a Berry-Esseen type bound that has been employed for similar purposes for other families of random matrices. In the second part, random geometric graphs on the unit sphere are considered. Observing that adjacency matrices of these graphs can be thought of as random inner product matrices, we are able to use an idea of Cheng-Singer to establish the limiting for the ESD of these adjacency matrices.
Temple University--Theses
30
Giasemidis, Georgios. "Spectral dimension in graph models of causal quantum gravity." Thesis, University of Oxford, 2013. http://ora.ox.ac.uk/objects/uuid:d0aaa6f2-dd0b-4ea9-81c1-7c9e81a7229e.
Full textAbstract:
The phenomenon of scale dependent spectral dimension has attracted special interest in the quantum gravity community over the last eight years. It was first observed in computer simulations of the causal dynamical triangulation (CDT) approach to quantum gravity and refers to the reduction of the spectral dimension from 4 at classical scales to 2 at short distances. Thereafter several authors confirmed a similar result from different approaches to quantum gravity. Despite the contribution from different approaches, no analytical model was proposed to explain the numerical results as the continuum limit of CDT. In this thesis we introduce graph ensembles as toy models of CDT and show that both the continuum limit and a scale dependent spectral dimension can be defined rigorously. First we focus on a simple graph ensemble, the random comb. It does not have any dynamics from the gravity point of view, but serves as an instructive toy model to introduce the characteristic scale of the graph, study the continuum limit and define the scale dependent spectral dimension. Having defined the continuum limit, we study the reduction of the spectral dimension on more realistic toy models, the multigraph ensembles, which serve as a radial approximation of CDT. We focus on the (recurrent) multigraph approximation of the two-dimensional CDT whose ensemble measure is analytically controlled. The latter comes from the critical Galton-Watson process conditioned on non-extinction. Next we turn our attention to transient multigraph ensembles, corresponding to higher-dimensional CDT. Firstly we study their fractal properties and secondly calculate the scale dependent spectral dimension and compare it to computer simulations. We comment further on the relation between Horava-Lifshitz gravity, asymptotic safety, multifractional spacetimes and CDT-like models.
31
Reiter, Richard M. "Prediction of recurrence in thin melanoma using trees and random forests /." Electronic version (PDF), 2005. http://dl.uncw.edu/etd/2005/reiterr/richardreiter.html.
Full text
32
Jones, Brian Douglas. "Tree components in random graph processes with non-uniform edge probabilities /." The Ohio State University, 1995. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487867541733461.
Full text
33
Baaqeel, Hanan. "Central limit theorems and statistical inference for some random graph models." Thesis, University of Nottingham, 2015. http://eprints.nottingham.ac.uk/29294/.
Full textAbstract:
Random graphs and networks are of great importance in any fields including mathematics, computer science, statistics, biology and sociology. This research aims to develop statistical theory and methods of statistical inference for random graphs in novel directions. A major strand of the research is the development of conditional goodness-of-fit tests for random graph models and for random block graph models. On the theoretical side, this entails proving a new conditional central limit theorem for a certain graph statistics, which are closely related to the number of two-stars and the number of triangles, and where the conditioning is on the number of edges in the graph. A second strand of the research is to develop composite likelihood methods for estimation of the parameters in exponential random graph models. Composite likelihood methods based on edge data have previously been widely used. A novel contribution of the thesis is the development of composite likelihood methods based on more complicated data structures. The goals of this PhD thesis also include testing the numerical performance of the novel methods in extensive simulation studies and through applications to real graphical data sets.
34
Lukov, Lior Y. "Unravelling the architecture of membrane proteins with conditional random fields." Thesis, The University of Sydney, 2005. http://hdl.handle.net/2123/9335.
Full textAbstract:
In this thesis we use Conditional Random Fields (CRFs) as a sequential classifier to predict the location of transmembrane helical regions in membrane proteins. CRFs allow for a seamless and principled integration of biological domain knowledge into the model and are known to have several advantages over other approaches. We have used this flexibility in order to incorporate several biologically inspired features into the model. We compared our approach with twenty eight other methods and received the highest score in the percentage of residues predicted correctly. We have also carried out experiments comparing CRFs against Maximum Entropy Models (MEMMs). Our results confirm that CRFs overcome the label bias problem, which are known to afflict MEMMs. Furthermore, we have used CRFs to analyze the architecture of the protein complex, Cytochrome c oxidase, and have recreated the results obtained from physical experiments.
35
Mirza, Batul J. "Jumping Connections: A Graph-Theoretic Model for Recommender Systems." Thesis, Virginia Tech, 2001. http://hdl.handle.net/10919/31370.
Full textAbstract:
Recommender systems have become paramount to customize
information access and reduce information overload. They serve multiple
uses, ranging from suggesting products and artifacts (to consumers), to
bringing people together by the connections induced by (similar) reactions
to products and services. This thesis presents a graph-theoretic model that
casts recommendation as a process of 'jumping connections' in a graph. In
addition to emphasizing the social network aspect, this viewpoint provides a
novel evaluation criterion for recommender systems. Algorithms for
recommender systems are distinguished not in terms of predicted ratings of
services/artifacts, but in terms of the combinations of people and artifacts
that they bring together. We present an algorithmic framework drawn from
random graph theory and outline an analysis for one particular form of jump
called a 'hammock.' Experimental results on two datasets collected over the
Internet demonstrate the validity of this approach.Master of Science
36
Coja-Oghlan, Amin, Andreas Goerdt, and André Lanka. "Spectral Partitioning of Random Graphs with Given Expected Degrees - Detailed Version." Universitätsbibliothek Chemnitz, 2009. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-200900426.
Full textAbstract:
It is a well established fact, that – in the case of classical random graphs like variants of Gn,p or random regular graphs – spectral methods yield efficient algorithms for clustering (e. g. colouring or bisec- tion) problems. The theory of large networks emerging recently provides convincing evidence that such networks, albeit looking random in some sense, cannot sensibly be described by classical random graphs. A vari- ety of new types of random graphs have been introduced. One of these types is characterized by the fact that we have a fixed expected degree sequence, that is for each vertex its expected degree is given. Recent theoretical work confirms that spectral methods can be success- fully applied to clustering problems for such random graphs, too – pro- vided that the expected degrees are not too small, in fact ≥ log6 n. In this case however the degree of each vertex is concentrated about its expectation. We show how to remove this restriction and apply spectral methods when the expected degrees are bounded below just by a suitable constant. Our results rely on the observation that techniques developed for the classical sparse Gn,p random graph (that is p = c/n) can be transferred to the present situation, provided we consider a suitably normalized ad- jacency matrix: We divide each entry of the adjacency matrix by the product of the expected degrees of the incident vertices. Given the host of spectral techniques developed for Gn,p this observation should be of independent interest.
37
Sivanathan, Gowrishankar. "Sink free orientations in a graph." Diss., Online access via UMI:, 2009.
Find full text
38
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.
39
Gajewar, Amita Surendra. "Approximate edge 3-coloring of cubic graphs." Thesis, Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/29735.
Full textAbstract:
Thesis (M. S.)--Computing, Georgia Institute of Technology, 2009.Committee Chair: Prof. Richard Lipton; Committee Member: Prof. Dana Randall; Committee Member: Prof. H. Venkateswaran. Part of the SMARTech Electronic Thesis and Dissertation Collection.
40
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.
41
Osthus, Deryk Simeon. "On the evolution of random discrete structures." Doctoral thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, 2000. http://dx.doi.org/10.18452/14561.
Full textAbstract:
Inhalt der Dissertation ist die Untersuchung der Evolutionsprozesse zufälliger diskreter Strukturen. Solche Evolutionsprozesse lassen sich üblicherweise wie folgt beschreiben. Anfangs beginnt man mit einer sehr einfachen Struktur (z.B. dem Graphen auf n Ecken, der keine Kanten hat) und einer Menge von ``Bausteinen'' (z.B. der Kantenmenge des vollständigen Graphen auf n Ecken). Mit zunehmender Zeit werden zufällig mehr und mehr Bausteine eingefügt. Die grundlegende Frage, mit der sich diese Dissertation beschäftigt, ist die folgende: Wie sieht zu einem gegebenen Zeitpunkt die durch den Prozess erzeugte Struktur mit hoher Wahrscheinlichkeit aus? Obwohl das Hauptthema der Dissertation die Evolution zufälliger diskreter Strukturen ist, lassen sich die erzielten Ergebnisse auch unter den folgenden Gesichtspunkten zusammenfassen: Zufällige Greedy-Algorithmen: Es wird ein zufälliger Greedy-Algorithmus untersucht, der für einen gegebenen Graphen H einen zufälligen H-freien Graphen erzeugt. Extremale Ergebnisse: Es wird die Existenz von Graphen mit hoher Taillenweite und hoher chromatischer Zahl bewiesen, wobei bestehende Schranken verbessert werden. Asymptotische Enumeration: Es werden präzise asymptotische Schranken für die Anzahl dreiecksfreier Graphen mit n Ecken und m Kanten bewiesen. ``Probabilistische'' Versionen klassischer S"atze: Es wird eine probabilistische Version des Satzes von Sperner bewiesen.In this thesis, we study the evolution of random discrete structures. Such evolution processes usually fit into the following general framework. Initially (say at time 0), we start with a very simple structure (e.g. a graph on n vertices with no edges) and a set of ``building blocks'' (e.g. the set of edges of the complete graph on n vertices). As time increases, we randomly add more and more elements from our set of building blocks. The basic question which we shall investigate is the following: what are the likely properties of the random structure produced by the process at any given time? Although this thesis is concerned with the evolution of random discrete structures, the results obtained can also be summarized according to the following keywords: Random greedy algorithms: we study the output of a random greedy algorithm which, for a given graph H, produces a random H-free graph. Extremal results: improving on previous bounds, we prove the existence of graphs with high girth and high chromatic number. Asymptotic enumeration: we prove sharp asymptotic bounds on the number of triangle-free graphs with n vertices and m edges for a large range of m. Probabilistic versions of ``classical'' theorems: we prove a probabilistic version of Sperner's theorem on finite sets.
42
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
43
Raymond, Jack R. "Typical case behaviour of spin systems in random graph and composite ensembles." Thesis, Aston University, 2008. http://publications.aston.ac.uk/15374/.
Full textAbstract:
This thesis includes analysis of disordered spin ensembles corresponding to Exact Cover, a multi-access channel problem, and composite models combining sparse and dense interactions. The satisfiability problem in Exact Cover is addressed using a statistical analysis of a simple branch and bound algorithm. The algorithm can be formulated in the large system limit as a branching process, for which critical properties can be analysed. Far from the critical point a set of differential equations may be used to model the process, and these are solved by numerical integration and exact bounding methods. The multi-access channel problem is formulated as an equilibrium statistical physics problem for the case of bit transmission on a channel with power control and synchronisation. A sparse code division multiple access method is considered and the optimal detection properties are examined in typical case by use of the replica method, and compared to detection performance achieved by interactive decoding methods. These codes are found to have phenomena closely resembling the well-understood dense codes. The composite model is introduced as an abstraction of canonical sparse and dense disordered spin models. The model includes couplings due to both dense and sparse topologies simultaneously. The new type of codes are shown to outperform sparse and dense codes in some regimes both in optimal performance, and in performance achieved by iterative detection methods in finite systems.
44
Glover, Cory. "The Non-Backtracking Spectrum of a Graph and Non-Bactracking PageRank." BYU ScholarsArchive, 2021. https://scholarsarchive.byu.edu/etd/9194.
Full textAbstract:
This thesis studies two problems centered around non-backtracking walks on graphs. First, we analyze the spectrum of the non-backtracking matrix of a graph. We show how to obtain the eigenvectors of the non-backtracking matrix using a smaller matrix and in doing so, create a block diagonal decomposition which more clearly expresses the non-backtracking matrix eigenvalues. Additionally, we develop upper and lower bounds on the matrix spectrum and use the spectrum to investigate properties of the graph. Second, we investigate the difference between PageRank and non-backtracking PageRank. We show some instances where there is no difference and develop an algorithm to compare PageRank and non-backtracking PageRank under certain conditions using $\mu$-PageRank.
45
Samavat, Reza. "Mean Eigenvalue Counting Function Bound for Laplacians on Random Networks." Doctoral thesis, Universitätsbibliothek Chemnitz, 2015. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-159578.
Full textAbstract:
Spectral graph theory widely increases the interests in not only discovering new properties of well known graphs but also proving the well known properties for the new type of graphs. In fact all spectral properties of proverbial graphs are not acknowledged to us and in other hand due to the structure of nature, new classes of graphs are required to explain the phenomena around us and the spectral properties of these graphs can tell us more about the structure of them. These both themes are the body of our work here. We introduce here three models of random graphs and show that the eigenvalue counting function of Laplacians on these graphs has exponential decay bound. Since our methods heavily depend on the first nonzero eigenvalue of Laplacian, we study also this eigenvalue for the graph in both random and nonrandom cases.
46
Pettarin, Alberto. "Graph Models of Information Spreading in Wireless Networks." Doctoral thesis, Università degli studi di Padova, 2012. http://hdl.handle.net/11577/3422448.
Full textAbstract:
This thesis investigates the structural properties of graph models of wireless networks, where autonomous agents communicate using radios in order to accomplish a predefined task. Ad hoc, sensor, and vehicle networks are perhaps the most familiar examples. The goal of this thesis is the analytical characterization of information spreading in graph models of wireless networks, since this fundamental process is a primitive needed to accomplish more complex tasks.
The well-established graph-based approaches adopted when analyzing
the behavior of “classical” distributed systems (e.g., P2P networks, computing clusters, etc.) fail to generalize to wireless networks, due to several causes, including the stricter physical constraints governing the operation of these systems (e.g., interference on the physical channel or scarce energy/computational resources) and the fact that the topology of the network might be unknown at design time or it might evolve over time.
This thesis shows how to tackle these problems by suitably defining
and rigorously analyzing graph models and graph processes capturing
the structure, evolution and operation of these networks. We present two
reference scenarios.
In the first one we study a family of random graphs known as Bluetooth Topology, which closely model the connectivity of a network built by
the device discovery phase of Bluetooth-like protocols, largely employed
in wireless networks. Formally, the Bluetooth Topology generalizes the
well-known Random Geometric Graph model, introducing a distributed
pruning of the edge set. We investigate the expansion and the diameter of
these graphs, as they quantify the bandwidth and the latency of a wireless
network. We give tight bounds on the expansion and, leveraging on these,
we prove nearly-tight bounds on the diameter. Our results show that the
Bluetooth Topology features the same global level of connectivity of the Random Geometric Graph but requires maintaining much fewer communication links.
Motivated by the recent and rapidly growing interest in mobile systems,
in the second part of the thesis we turn our attention to the dynamics of
information dissemination between agents performing random walks on
a planar grid and communicating over short distances. This setting can
also be employed to study phenomena like the spreading of a disease,
where infections are the result of local interactions between agents. We
prove that, for a sufficiently sparse system, the broadcast time of a message
is independent from the transmission radius; indeed, we show that the
broadcast time is dominated by the time needed for many agents to meet.
Our findings nicely complements previous results that dealt with dense
systems, where there is dependency from the transmission radius. Moreover,
our analysis techniques extend to similar mobility-communication models,
suggesting some interesting further research directions.Questa tesi studia le proprieta' strutturali di alcuni modelli a grafo di reti di agenti autonomi che comunicano via radio per completare un prefissato compito. Reti ad hoc, di sensori e veicolari sono forse gli esempi piu' immediati. Lo scopo di questa tesi e caratterizzare la diffusione dell’infor- mazione in questi modelli a grafo di reti wireless, considerata l’importanza di questo processo come primitiva fondamentale per realizzare protocolli piu' complessi. Gli approcci basati su tecniche combinatorie adottati per l’analisi di sistemi distribuiti “classici”, come le reti P2P o i cluster di calcolo, non possono essere estesi alle reti wireless, per varie ragioni: ad esempio a causa dei vincoli fisici che governano il funzionamento di questi sistemi (interferenza sul canale radio, scarse risorse energetiche/computazionali, ecc.) e per il fatto che la topologia della rete puo' essere ignota in fase di progettazione o puo' evolvere nel tempo. Questa tesi suggerisce come sia possibile affrontare tali problemi tramite l’opportuna definizione e l’analisi rigorosa di modelli a grafo (o processi su grafi) che catturino l’evoluzione e il funzionamento delle reti wireless. Mostriamo come sia possibile applicare quest’approccio a due scenari di riferimento. Innanzitutto studiamo una famiglia di grafi random nota come Bluetooth Topology, che ben rappresenta la connettivita' della rete creata dalla fase di device discovery in protocolli simili al Bluetooth, largamente utilizzati nelle reti wireless. Dal punto di vista formale, la Bluetooth Topology generalizza il ben noto modello Random Geometric Graph, introducendovi una selezione distribuita degli archi. Studiamo l’espansione e il diametro di questi grafi, poiche' quantificano la banda e la latenza della rete. Dimostriamo limiti stretti all’espansione e, sfruttando questa caratterizzazione, diamo dei limiti quasi stretti al diametro. I nostri risultati provano che la Bluetooth Topology presenta lo stesso livello globale di connettivita' del Random Geometric Graph, pur richiedendo molti meno link di comunicazione. Graph, pur richiedendo molti meno link di comunicazione. Motivati dal recente crescente interesse verso i sistemi mobili, nella seconda parte della tesi concentriamo la nostra attenzione sulle dinamiche di disseminazione dell’informazione tra agenti che effettuano random walk su una griglia planare e che comunicano su brevi distanze. Questo scenario puo' essere utilizzato per studiare fenomeni come la diffusione di malattie, dove le infezioni sono il risultato di interazioni locali tra gli agenti. Proviamo che, per un sistema sufficientemente sparso, il tempo di broadcast di un messaggio e indipendente dal raggio di trasmissione, dimostrando che esso e' dominato dal tempo necessario affinche' molti agenti si incontrino. I nostri risultati completano l’analisi, apparsa in lavori precedenti, di sistemi densi, dove viceversa vi e' dipendenza del tempo di broadcast dal raggio di trasmissione. Inoltre le nostre tecniche di analisi possono essere estese a modelli di mobilita'-comunicazione simili, suggerendo alcune interessanti linee di ulteriore ricerca.
47
Nanongkai, Danupon. "Graph and geometric algorithms on distributed networks and databases." Diss., Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/41056.
Full textAbstract:
In this thesis, we study the power and limit of algorithms on various models, aiming at applications in distributed networks and databases.
In distributed networks, graph algorithms are fundamental to many applications. We focus on computing random walks which are an important
primitive employed in a wide range of applications but has always been computed naively. We show that a faster solution exists and subsequently
develop faster algorithms by exploiting random walk properties leading to two immediate applications. We also show that this algorithm is optimal.
Our technique in proving a lower bound show the first non-trivial connection between communication complexity and lower bounds of distributed
graph algorithms. We show that this technique has a wide range of applications by proving new lower bounds of many problems. Some of these lower
bounds show that the existing algorithms are tight.
In database searching, we think of the database as a large set of multi-dimensional points stored in a disk and want to help the users to quickly find the most desired point. In this thesis, we develop an algorithm that is significantly faster than previous algorithms both theoretically and experimentally.
The insight is to solve the problem on the streaming model which helps emphasize the benefits of sequential access over random disk access. We also
introduced the randomization technique to the area. The results were complemented with a lower bound. We also initiat a new direction as an attempt to get a better query. We are the first to quantify the output quality using "user satisfaction" which is made possible by borrowing the idea of modeling users by utility functions from game theory and justify our approach through a geometric analysis.
48
Shafie, Termeh. "Random Multigraphs : Complexity Measures, Probability Models and Statistical Inference." Doctoral thesis, Stockholms universitet, Statistiska institutionen, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:su:diva-82697.
Full textAbstract:
This thesis is concerned with multigraphs and their complexity which is defined and quantified by the distribution of edge multiplicities. Two random multigraph models are considered. The first model is random stub matching (RSM) where the edges are formed by randomly coupling pairs of stubs according to a fixed stub multiplicity sequence. The second model is obtained by independent edge assignments (IEA) according to a common probability distribution over the edge sites. Two different methods for obtaining an approximate IEA model from an RSM model are also presented. In Paper I, multigraphs are analyzed with respect to structure and complexity by using entropy and joint information. The main results include formulae for numbers of graphs of different kinds and their complexity. The local and global structure of multigraphs under RSM are analyzed in Paper II. The distribution of multigraphs under RSM is shown to depend on a single complexity statistic. The distributions under RSM and IEA are used for calculations of moments and entropies, and for comparisons by information divergence. The main results include new formulae for local edge probabilities and probability approximation for simplicity of an RSM multigraph. In Paper III, statistical tests of a simple or composite IEA hypothesis are performed using goodness-of-fit measures. The results indicate that even for very small number of edges, the null distributions of the test statistics under IEA have distributions that are well approximated by their asymptotic χ2-distributions. Paper IV contains the multigraph algorithms that are used for numerical calculations in Papers I-III.
49
Huang, Zan. "GRAPH-BASED ANALYSIS FOR E-COMMERCE RECOMMENDATION." Diss., Tucson, Arizona : University of Arizona, 2005. http://etd.library.arizona.edu/etd/GetFileServlet?file=file:///data1/pdf/etd/azu%5Fetd%5F1167%5F1%5Fm.pdf&type=application/pdf.
Full text
50
Casselgren, Carl Johan. "On some graph coloring problems." Doctoral thesis, Umeå universitet, Institutionen för matematik och matematisk statistik, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-43389.
Full text