Randomised algorithms are an effective method of attacking computationally intractable problems. A simple and fast randomised algorithm may produce results to an accuracy sufficient for many purposes, especially in the average case. In this thesis we consider average case analyses of heuristics for certain NP-hard graph optimisation problems. In particular, we consider algorithms that find dominating sets of random regular directed graphs. As well as providing an average case analysis, our results also determine new upper bounds on domination numbers of random regular directed graphs. The algorithms for random regular directed graphs considered in this thesis are known as prioritised algorithms. Each prioritised algorithm determines a discrete random process. This discrete process may be continuously approximated using differential equations. Under certain conditions, the solutions to these differential equations describe the behaviour of the prioritised algorithm. Applying such an analysis to prioritised algorithms directly is difficult. However, we are able to use prioritised algorithms to define new algorithms, called deprioritised algorithms, that can be analysed in this fashion. Defining a deprioritised algorithm based on a given prioritised algorithm, and then analysing the deprioritised algorithm, is called the deprioritised approach. The initial theory describing the deprioritised approach was developed by Wormald and has been successfully applied in many cases. However not all algorithms are covered by Wormald??s theory: for example, algorithms for random regular directed graphs. The main contribution of this thesis is the extension of the deprioritised approach to a larger class of prioritised algorithms. We demonstrate the new theory by applying it to two algorithms which find dominating sets of random regular directed graphs.

Randomised algorithms are an effective method of attacking computationally intractable problems. A simple and fast randomised algorithm may produce results to an accuracy sufficient for many purposes, especially in the average case. In this thesis we consider average case analyses of heuristics for certain NP-hard graph optimisation problems. In particular, we consider algorithms that find dominating sets of random regular directed graphs. As well as providing an average case analysis, our results also determine new upper bounds on domination numbers of random regular directed graphs. The algorithms for random regular directed graphs considered in this thesis are known as prioritised algorithms. Each prioritised algorithm determines a discrete random process. This discrete process may be continuously approximated using differential equations. Under certain conditions, the solutions to these differential equations describe the behaviour of the prioritised algorithm. Applying such an analysis to prioritised algorithms directly is difficult. However, we are able to use prioritised algorithms to define new algorithms, called deprioritised algorithms, that can be analysed in this fashion. Defining a deprioritised algorithm based on a given prioritised algorithm, and then analysing the deprioritised algorithm, is called the deprioritised approach. The initial theory describing the deprioritised approach was developed by Wormald and has been successfully applied in many cases. However not all algorithms are covered by Wormald??s theory: for example, algorithms for random regular directed graphs. The main contribution of this thesis is the extension of the deprioritised approach to a larger class of prioritised algorithms. We demonstrate the new theory by applying it to two algorithms which find dominating sets of random regular directed graphs.

No description available.

In summary, the viewpoint of random graphs indeed provides us an opportunity of improving some existing machine learning algorithms. / In this thesis, we establish three machine learning models on random graphs: Heat Diffusion Models on Random Graphs, Predictive Random Graph Ranking, and Random Graph Dependency. The heat diffusion models on random graphs lead to Graph-based Heat Diffusion Classifiers (G-HDC) and a novel ranking algorithm on Web pages called DiffusionRank. For G-HDC, a random graph is constructed on data points. The generated random graph can be considered as the representation of the underlying geometry, and the heat diffusion model on them can be considered as the approximation to the way that heat flows on a geometric structure. Experiments show that G-HDC can achieve better performance in accuracy in some benchmark datasets. For DiffusionRank, theoretically we show that it is a generalization of PageRank when the heat diffusion coefficient tends to infinity, and empirically we show that it achieves the ability of anti-manipulation. / Predictive Random Graph Ranking (PRGR) incorporates DiffusionRank. PRGR aims to solve the problem that the incomplete information about the Web structure causes inaccurate results of various ranking algorithms. The Web structure is predicted as a random graph, on which ranking algorithms are expected to be improved in accuracy. Experimental results show that the PRGR framework can improve the accuracy of the ranking algorithms such as PageRank and Common Neighbor. / Three special forms of the novel Random Graph Dependency measure on two random graphs are investigated. The first special form can improve the speed of the C4.5 algorithm, and can achieve better results on attribute selection than gamma used in Rough Set Theory. The second special form of the general random graph dependency measure generalizes the conditional entropy because it becomes equivalent to the conditional entropy when the random graphs take their special form-equivalence relations. Experiments demonstrates that the second form is an informative measure, showing its success in decision trees on small sample size problems. The third special form can help to search two parameters in G-HDC faster than the cross-validation method. / Yang, haixuan. / "August 2007." / Advisers: Irwin King; Michael R. Lyu. / Source: Dissertation Abstracts International, Volume: 69-02, Section: B, page: 1125. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (p. 184-197). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract in English and Chinese. / School code: 1307.

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).

Thesis (Ph. D.)--University of Washington, 2007. / Vita. Includes bibliographical references (leaves 48-49).

Thesis (B.A.)--Haverford College, Dept. of Computer Science, 2005. / Includes bibliographical references.

Thesis (Ph. D.)--Rutgers University, 2007. / "Graduate Program in Mathematics." Includes bibliographical references (p. 64-65).

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

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.