Theta graphs are important geometric graphs that have many applications, including wireless networking, motion planning, real-time animation, and minimum-spanning tree construction. We give closed form expressions for the average degree of theta graphs of a homogeneous Poisson point process over the plane. We then show that essentially the same bounds---with vanishing error terms---hold for theta graphs of finite sets of points that are uniformly distributed in a square. Finally, we show that the number of edges in a theta graph of points uniformly distributed in a square is concentrated around its expected value.
In contrast, properties of other proximity graphs of random point sets have been studied extensively: Devroye @cite_15 presents a general theorem for obtaining exact leading constants for the expected degree of a number of proximity graphs over point sets drawn from a large class of distributions. This theorem can be applied to Gabriel graphs, relative neighbourhood graphs, and nearest-neighbour graphs. This work [Section 7] devroye:expected also mentions directional nearest-neighbour graphs,'' now commonly known as Yao graphs @cite_5 @cite_11 , and points out that the general theorem does not apply to these (nor does it apply to theta graphs---for the same reasons).
@cite_5 @cite_15 @cite_11
2023618719 2051522939 2031671531
Abstract We consider n independent points with a common but arbitrary density f in R d . Two points ( X i , X j ) are joined by an edge when a certain set S ( X i , X j ) does not contain any other data points. The expected number E ( N ) of edges in the graph depends upon n , f and the definition of S . Examples include rectangle, spheres and loons; these lead to the graph of all dominance pairs, the Gabriel graph and the relative neighborhood graph, respectively. Other graphs covered by our analysis include the nearest neighbor graph and the directional nearest neighbor graph. In all cases, we obtain asymptotic lower bounds that do not depend upon f (and are hence useful in all applications involving these graphs, since we usually do not know f ). For sparse graphs, exact asymptotic constants are obtained for E ( N ) that are valid for all densities. We study an evolving spatial network in which sequentially arriving vertices are joined to existing vertices at random according to a rule that combines preference according to degree with preference according to spatial proximity. We investigate phase transitions in graph structure as the relative weighting of these two components of the attachment rule is varied. Previous work of one of the authors showed that when the geometric component is weak, the limiting degree sequence of the resulting graph coincides with that of the standard Barab 'asi--Albert preferential attachment model. We show that at the other extreme, in the case of a sufficiently strong geometric component, the limiting degree sequence coincides with that of a purely geometric model, the on-line nearest-neighbour graph, which is of interest in its own right and for which we prove some extensions of known results. We also show the presence of an intermediate regime, in which the behaviour differs significantly from both the on-line nearest-neighbour graph and the Barab 'asi--Albert model; in this regime, we obtain a stretched exponential upper bound on the degree sequence. Our results lend some mathematical support to simulation studies of Manna and Sen, while proving that the power law to stretched exponential phase transition occurs at a different point from the one conjectured by those authors. Suppose we are given a bipartite graph with vertex set X, Y, |X| = n , |Y| = N , each point in X (Y) has degree D(d) fixed, respectively, moreover, each pair of points x, x' ∈ X has at most D (log n) 3 (common) neighbours. Let t (X, Y) denote the minimum number of vertices of Y needed to cover all vertices of X. We prove (Theorem 1.1) that t (X, Y) d n tends to 1 as n tends to infinity. This result has many applications: Theorem [5]. Suppose k > r > 1 are fixed, n → ∞. Then there exists a collection of (1 + o (1)) × ( n r ) ( k r ) k -subsets of an n -set so that each r -subset is contained in at least one member of the collection. Analogues and strengthenings of this result are deduced. E.g. for vector spaces, orthogonal or simplectic geometries, random collections of k -sets with constant probabilities, etc. Theorem 3.3. Suppose G is a graph on v vertices and e edges and ℛ is a random graph on n vertices and edge probability e ( v 2 ). Then there exists a collection of (1 + o (1))( n 2 ) ( v 2 ) induced subgraphs of ℛ on v vertices, isomorphic to G and such that each edge (non-edge) of ℛ is covered by an edge (non-edge) of a graph in the collection. Motivated by applications of Gabriel graphs and Yao graphs in wireless ad-hoc networks, we show that the maximum degree of a random Gabriel graph or Yao graph defined on n points drawn uniformly at random from a unit square grows as ?(log n log log n) in probability. This paper presents a relational framework for studying properties of labeled data points related to proximity and labeling information in order to improve the performance of the 1NN rule. Specifically, the class conditional nearest neighbor (ccnn) relation over pairs of points in a labeled training set is introduced. For a given class label c, this relation associates to each point a its nearest neighbor computed among only those points with class label c (excluded a). A characterization of ccnn in terms of two graphs is given. These graphs are used for defining a novel scoring function over instances by means of an information-theoretic divergence measure applied to the degree distributions of these graphs. The scoring function is employed to develop an effective large margin instance selection method, which is empirically demonstrated to improve storage and accuracy performance of the 1NN rule on artificial and real-life data sets. Previous experiments with low dimensional data sets have shown that Gabriel graph methods for instance-based learning are among the best machine learning algorithms for pattern classification applications. However, as the dimensionality of the data grows large, all data points in the training set tend to become Gabriel neighbors of each other, bringing the efficacy of this method into question. Indeed, it has been conjectured that for high-dimensional data, proximity graph methods that use sparser graphs, such as relative neighbor graphs (RNG) and minimum spanning trees (MST) would have to be employed in order to maintain their privileged status. Here the performance of proximity graph methods, in instance-based learning, that employ Gabriel graphs, relative neighborhood graphs, and minimum spanning trees, are compared experimentally on high-dimensional data sets. These methods are also compared empirically against the traditional k-NN rule and support vector machines (SVMs), the leading competitors of proximity graph methods. Let P be a Poisson process of intensity one in a square Sn of area n. For a fixed integer k, join every point of P to its k nearest neighbours, creating an undirected random geometric graph Gn,k. We prove that there exists a critical constant ccrit such that for c ccrit, Gn,⌊clog n⌋ is connected with probability tending to 1 as n → ∞. This answers a question posed by the authors in [1]. Let P be a Poisson process of intensity one in a square Sn of area n. For a fixed integer k, we join every point of P to its k nearest neighbours, creating an undirected random geometric graph GSn,k = Gn,k in which every vertex has degree at least k. The connectivity of these graphs was studied by the present authors in [1]. It is not hard to see that Gn,k becomes connected around k = �(log n), and we proved in [1] that if k(n) ≤ 0.3043log n then the probability that Gn,k(n) is connected tends to zero as n → ∞, while if k(n) ≥ 0.5139log n then the probability that Gn,k(n) is connected tends to one as n → ∞. However, we were unable to prove the natural conjecture that there exists a critical constant ccrit such that for c ccrit, P(Gn,⌊clog n⌋ is connected) → 1 as n → ∞. In this paper we prove this conjecture. Many graphs arising in various information networks exhibit the "power law" behavior — the number of vertices of degree k is proportional to k −β for some positive β. We show that if β > 2.5, the largest eigenvalue of a random power law graph is almost surely (1+ o(1)) √ m where m is the maximum degree. Moreover, the k largest eigenvalues of a random power law graph with exponent β have power law distribution with exponent 2β − 1 if the maximum degree is sufficiently large, where k is a function depending on β, m and d, the average degree. When 2< β < 2.5, the largest eigenvalue is heavily concentrated at cm 3−β for some constant c depending on β and the average degree. This result follows from a more general theorem which shows that the largest eigenvalue of a random graph with a given expected degree sequence is determined by m, the maximum degree, and ˜ d, the weighted average of the squares of the expected degrees. We show that the k-th largest eigenvalue is almost surely (1+ o(1)) √ m k where mk is the k-th largest expected degree provided mk is large enough. These results have implications on the usage of spectral techniques in many areas related to pattern detection and information retrieval. We consider sparse random intersection graphs with the property that the clustering coefficient does not vanish as the number of nodes tends to infinity. We find explicit asymptotic expressions for the correlation coefficient of degrees of adjacent nodes (called the assortativity coefficient), the expected number of common neighbours of adjacent nodes, and the expected degree of a neighbour of a node of a given degree k. These expressions are written in terms of the asymptotic degree distribution and, alternatively, in terms of the parameters defining the underlying random graph model. Distributed voting is a fundamental topic in distributed computing. In the standard model of pull voting, at each step every vertex chooses a neighbour uniformly at random and adopts its opinion. The voting is completed when all vertices hold the same opinion. In the simplest case, each vertex initially holds one of two different opinions. This partitions the vertices into arbitrary sets A and B. For many graphs, including regular graphs and irrespective of their expansion properties, if both A and B are sufficiently large sets, then pull voting requires @math expected steps, where n is the number of vertices of the graph. In this paper we consider a related class of voting processes based on sampling two opinions. In the simplest case, every vertex v chooses two random neighbours at each step. If both these neighbours have the same opinion, then v adopts this opinion. Otherwise, v keeps its own opinion. Let G be a connected graph with n vertices and m edges. Let P be the transition matrix of a simple random walk on G with second largest eigenvalue @math . We show that if the initial imbalance in degree between the two opinions satisfies @math , then with high probability voting completes in @math steps, and the opinion with the larger initial degree wins. The condition that @math , or only a bound on the conductance of the graph is known, the sampling process can be modified so that voting still provably completes in @math steps with high probability. The modification uses two sampling based on probing to a fixed depth @math from any vertex. In its most general form our voting process allows vertices to bias their sampling of opinions among their neighbours to achieve a desired outcome. This is done by allocating weights to edges. Suppose in a graph G vertices can be either red or blue. Let k be odd. At each time step, each vertex v in G polls k random neighbours and takes the majority colour. If it does not have k neighbours, it simply polls all of them, or all less one if the degree of v is even. We study this protocol on graphs of a given degree sequence, in the following setting: initially each vertex of G is red independently with probability α < 1 2 , and is otherwise blue. We show that if α is sufficiently biased, then with high probability consensus is reached on the initial global majority within O ( log k log k n ) steps if 5 ? k ? d , and O ( log d log d n ) steps if k d . Here, d ? 5 is the effective minimum degree, the smallest integer which occurs ? ( n ) times in the degree sequence. We further show that on such graphs, any local protocol in which a vertex does not change colour if all its neighbours have that same colour, takes time at least ? ( log d log d n ) , with high probability. Additionally, we demonstrate how the technique for the above sparse graphs can be applied in a straightforward manner to get bounds for the Erd?s-Renyi random graphs in the connected regime. A median of a family of vertices in a graph is any vertex whose distance-sum to that family is minimum. In the framework of metric spaces the problem of minimizing a distance-sum is often referred to as the Fermat problem. On the other hand, medians have been studied from a purely order-theoretic or combinatorial point of view (for instance, in statistics, or in Jordan’s work [12] on trees). The aim of this paper is to investigate the mutual relationship of the metric and the ordinal combinatorial approaches to the median problem in the class of median graphs. A connected graph is a median graph if any three vertices admit a unique median (see Avann [l]). Note that trees and the covering graphs of distributive lattices are median graphs. Very little is known about medians in arbitrary graphs (cf. Slater [20]); so far, only trees (Zelinka [22], and many others) and the covering graphs of distributive lattices (Barbut [4]) have been considered. In both cases we get that (i) the medians of any family form an interval (a path in a tree, an order-theoretic interval in a distributive lattice), and (ii) medians of odd numbered families are unique (see Slater [19] for trees, and Barbut [4] for distributive lattices). These results point to the fact that (i) and (ii) must be true for any median graph. After recalling some basic definitions and facts concerning median graphs and median semilattices (for further information, see Bandelt and Hedlikova [3]), we establish (i) and (ii) for arbitrary median graphs. Our results are based on theorems of Avann, Sholander, and Barbut. In trees medians have nice local properties (cf. [7]). Indeed, median sets are related to mass centers (Zelinka [22]) and security centers (Slater [18]). In Section 3 this is extended to median graphs. The study of medians applies to social choice theory (see Barbut 151, and Barthelemy and Monjardet [8]). The median procedure is strongly related to the simple majority rule: the median of a family (A,, . . . , Azk+ ,) of subsets of a set X may be written as U n Ai (Barbut’s formula). We consider monotone embeddings of a finite metric space into low-dimensional normed space. That is, embeddings that respect the order among the distances in the original space. Our main interest is in embeddings into Euclidean spaces. We observe that any metric on n points can be embedded into l2n, while (in a sense to be made precise later), for almost every n-point metric space, every monotone map must be into a space of dimension Ω(n) (Lemma 3).It becomes natural, then, to seek explicit constructions of metric spaces that cannot be monotonically embedded into spaces of sublinear dimension. To this end, we employ known results on sphericity of graphs, which suggest one example of such a metric space--that is defined by a complete bipartite graph. We prove that an δn-regular graph of order n, with bounded diameter has sphericity Ω(n (λ2+1)), where λ2 is the second largest eigenvalue of the adjacency matrix of the graph, and 0<δ≤½ is constant (Theorem 4). We also show that while random graphs have linear sphericity, there are quais-random graphs of logarithmic sphericity (Lemma 7).For the above bound to be linear, λ2 must be constant. We show that if the second eigenvalue of an n 2-regular graph is bounded by a constant, then the graph is close to being complete bipartite. Namely, its adjacency matrix differs from that of a complete bipartite graph in only o(n2) entries (Theorem 5). Furthermore, for any 0<δ<½, and λ2, there are only finitely many δn-regular graphs with second eigenvalue at most λ2 (Corollary 4). A Directional Nearest-Neighbor graph is defined on a finite set of points in the plane by drawing an arc from each point X to its nearest neighbor in each of r divisions of the plane relative to X. We prove that Directional Nearest-Neighbor graphs having @math are strongly connected. In this paper we propose and analyze a randomized algorithm to get rendezvous between neighbours in an anonymous graph. We examine in particular the probability to obtain at least one rendezvous and the expected number of rendezvous. We study the rendezvous number distribution in the cases of chain graphs, rings, and complete graphs. The last part is devoted to the efficiency of the proposed algorithm. The "nearest-neighbor" relation, or more generally the "k-nearest-neighbors" relation, defined for a set of points in a metric space, has found many uses in computational geometry and clustering analysis, yet surprisingly little is known about some of its basic properties. In this paper we consider some natural questions that are motivated by geometric embedding problems. We derive bounds on the relationship between size and depth for the components of a nearest-neighbor graph and prove some probabilistic properties of the k-nearest-neighbors graph for a random set of points. We consider the following randomized algorithm for finding a matching M in an arbitrary graph G = (V, E). Repeatedly, choose a random vertex u, then a random neighbour v of u. Add edge u, v to M and delete vertices u, v from G along with any vertices that become isolated. Our main result is that there exists a positive constant ϵ such that the expected ratio of the size of the matching produced to the size of largest matching in G is at least 0.5 + ϵ. We obtain stronger results for sparse graphs and trees and consider extensions to hypergraphs. © 1995 Wiley Periodicals, Inc. In network modeling of complex systems one is often required to sample random realizations of networks that obey a given set of constraints, usually in form of graph measures. A much studied class of problems targets uniform sampling of simple graphs with given degree sequence or also with given degree correlations expressed in the form of a joint degree matrix. One approach is to use Markov chains based on edge switches (swaps) that preserve the constraints, are irreducible (ergodic) and fast mixing. In 1999, Kannan, Tet ali and Vempala (KTV) proposed a simple swap Markov chain for sampling graphs with given degree sequence and conjectured that it mixes rapidly (in poly-time) for arbitrary degree sequences. While the conjecture is still open, it was proven for special degree sequences, in particular, for those of undirected and directed regular simple graphs, of half-regular bipartite graphs, and of graphs with certain bounded maximum degrees. Here we prove the fast mixing KTV conjecture for novel, exponentially large classes of irregular degree sequences. Our method is based on a canonical decomposition of degree sequences into split graph degree sequences, a structural theorem for the space of graph realizations and on a factorization theorem for Markov chains. After introducing bipartite splitted degree sequences, we also generalize the canonical split graph decomposition for bipartite and directed graphs. We present a parallel algorithm for k-nearest neighbor graph construction that uses Morton ordering. Experiments show that our approach has the following advantages over existing methods: 1) faster construction of k-nearest neighbor graphs in practice on multicore machines, 2) less space usage, 3) better cache efficiency, 4) ability to handle large data sets, and 5) ease of parallelization and implementation. If the point set has a bounded expansion constant, our algorithm requires one-comparison-based parallel sort of points, according to Morton order plus near-linear additional steps to output the k-nearest neighbor graph. Markovian evolving graphs are dynamic-graph models where the links among a fixed set of nodes change during time according to an arbitrary Markovian rule. They are extremely general and they can well describe important dynamic-network scenarios. We study the speed of information spreading in the "stationary phase" by analyzing the completion time of the "flooding mechanism". We prove a general theorem that establishes an upper bound on flooding time in any stationary Markovian evolving graph in terms of its node-expansion properties. We apply our theorem in two natural and relevant cases of such dynamic graphs. "Geometric Markovian evolving graphs" where the Markovian behaviour is yielded by "n" mobile radio stations, with fixed transmission radius, that perform independent random walks over a square region of the plane. "Edge-Markovian evolving graphs" where the probability of existence of any edge at time "t" depends on the existence (or not) of the same edge at time "t-1". In both cases, the obtained upper bounds hold "with high probability" and they are nearly tight. In fact, they turn out to be tight for a large range of the values of the input parameters. As for geometric Markovian evolving graphs, our result represents the first analytical upper bound for flooding time on a class of concrete mobile networks.