马氏模型下移动自组网随选型路由协议特性分析

移动自组网络（简称MANET）因其移动性及无基础设施支持等特点已经成为无线通信网络中的热门问题．通过将一个MANET网络中每条链边的长度看作一个生灭过程,并且假设在泛洪过程中空间可以复用n次,建立了移动自组网络空间可复用的马氏模型,简记为n-SRBDM．在一个典型的随选型路由协议即动态源路由（DSR）协议的基础上,研究了网络的一些关键性能参数,给出了路由泛洪距离的概率分布和期望,限定泛洪步数时成功寻路的概率、发现τ-时有效路径及对称有效路径的概率,发现一条有效路径的平均时间等,对于路由维护过程,也引入并研究了一些网络性能参数,例如,路由恢复的平均频率,路由有效的平均时间．对于这些网络参数在空间可复用和空间不可复用两种情形下进行了比较．证明了空间可复用模型下的路由选择更为有效．     

On the probability of the occurrence of a copy of a fixed graph in a random distance graph

The threshold probability of the occurrence of a copy of a balanced graph in a random distance graph is obtained. The technique used by P. Erd?s and A. Rényi for determining the threshold probability for the classical random graph could not be applied in the model under consideration. In this connection, a new method for deriving estimates of the number of copies of a balanced graph in a complete distance graph is developed.     

An Interlacing Technique for Spectra of Random Walks and Its Application to Finite Percolation Clusters

A comparison technique for random walks on finite graphs is introduced, using the well-known interlacing method. It yields improved return probability bounds. A key feature is the incorporation of parts of the spectrum of the transition matrix other than just the principal eigenvalue. As an application, an upper bound of the expected return probability of a random walk with symmetric transition probabilities is found. In this case, the state space is a random partial graph of a regular graph of bounded geometry and transitive automorphism group. The law of the random edge-set is assumed to be invariant with respect to some transitive subgroup of the automorphism group (‘invariant percolation’). Given that this subgroup is unimodular, it is shown that this invariance strengthens the upper bound of the expected return probability, compared with standard bounds such as those derived from the Cheeger inequality. The improvement is monotone in the degree of the underlying transitive graph.     

Continuous-Time Independent Edge-Markovian Random Graph Process

In this paper, the continuous-time independent edge-Markovian random graph process model is constructed. The authors also define the interval isolated nodes of the random graph process, study the distribution sequence of the number of isolated nodes and the probability of having no isolated nodes when the initial distribution of the random graph process is stationary distribution, derive the lower limit of the probability in which two arbitrary nodes are connected and the random graph is also connected, and prove that the random graph is almost everywhere connected when the number of nodes is sufficiently large.     

Some large deviation results for sparse random graphs

Summary. We obtain a large deviation principle (LDP) for the relative size of the largest connected component in a random graph with small edge probability. The rate function, which is not convex in general, is determined explicitly using a new technique. The proof yields an asymptotic formula for the probability that the random graph is connected. We also present an LDP and related result for the number of isolated vertices. Here we make use of a simple but apparently unknown characterisation, which is obtained by embedding the random graph in a random directed graph. The results demonstrate that, at this scaling, the properties `connected' and `contains no isolated vertices' are not asymptotically equivalent. (At the threshold probability they are asymptotically equivalent.) Received: 14 November 1996 / In revised form: 15 August 1997     

Expansion in eigenfunctions of the Sturm-Liouville problem on a bundle graph

In this paper we consider the applicability of the Fourier method for partial differential equations on spatial grids (we choose a bundle graph as a model). This leads to an important problem, namely, to the expansion of a given function in eigenfunctions of the corresponding Sturm-Liouville problem on a grid. We study a model problem which describes a symmetric case, when one considers physically identical one-dimensional continuums on the bundle graph. Such problems arise, for example, in the modeling of oscillating processes of an elastic mast with supporting elastic ties.     

The random planar graph process

We consider the following variant of the classical random graph process introduced by Erd?s and Rényi. Starting with an empty graph on n vertices, choose the next edge uniformly at random among all edges not yet considered, but only insert it if the graph remains planar. We show that for all ε > 0, with high probability, θ(n²) edges have to be tested before the number of edges in the graph reaches (1 + ε)n. At this point, the graph is connected with high probability and contains a linear number of induced copies of any fixed connected planar graph, the first property being in contrast and the second one in accordance with the uniform random planar graph model. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Random generation of tournaments and asymmetric graphs with given out-degrees

In this paper, we first present a polynomial algorithm which computes a random tournament with given out-degrees; any tournament having these out-degrees has a nonzero probability to be computed. Then we give a necessary and sufficient condition for a sequence of numbers to be the out-degrees (or similarly the in-degrees) of an asymmetric graph. Lastly, using the above algorithm and this characterization, we design a second polynomial algorithm to compute a random asymmetric graph with given out-degrees, and any asymmetric graph with these out-degrees has a nonzero probability to be found.     

Random graphs with given vertex degrees and switchings

Random graphs with a given degree sequence are often constructed using the configuration model, which yields a random multigraph. We may adjust this multigraph by a sequence of switchings, eventually yielding a simple graph. We show that, assuming essentially a bounded second moment of the degree distribution, this construction with the simplest types of switchings yields a simple random graph with an almost uniform distribution, in the sense that the total variation distance is o(1). This construction can be used to transfer results on distributional convergence from the configuration model multigraph to the uniform random simple graph with the given vertex degrees. As examples, we give a few applications to asymptotic normality. We show also a weaker result yielding contiguity when the maximum degree is too large for the main theorem to hold.     

Multi-colony Wright–Fisher with seed-bank

We consider a multi-colony version of the Wright–Fisher model with seed-bank that was recently introduced by Blath et al. Individuals live in colonies and change type via resampling and mutation. Each colony contains a seed-bank that acts as a genetic reservoir. Individuals can enter the seed-bank and become dormant or can exit the seed-bank and become active. In each colony at each generation a fixed fraction of individuals swap state, drawn randomly from the active and the dormant population. While dormant, individuals suspend their resampling. While active, individuals resample from their own colony, but also from different colonies according to a random walk transition kernel representing migration. Both active and dormant individuals mutate.We are interested in the probability that two individuals drawn randomly from two given colonies are identical by descent, i.e., share a common ancestor. This probability, which depends on the locations of the two colonies, is a measure for the inbreeding coefficient of the population. We derive a formula for this probability that is valid when the colonies form a discrete torus. We consider the special case of a symmetric slow seed-bank, for which in each colony half of the individuals are in the seed-bank and at each generation the fraction of individuals that swap state is small. This leads to a simpler formula, from which we are able to deduce how the probability to be identical by descent depends on the distance between the two colonies and various relevant parameters. Through an analysis of random walk Green functions, we are able to derive explicit scaling expressions when mutation is slower than migration. We also compute the spatial second moment of the probability to be identical by descent for all parameters when the torus becomes large. For the special case of a symmetric slow seed-bank, we again obtain explicit scaling expressions.     

Large scale localization of a spatial version of Neveu’s branching process

Recently a spatial version of Neveu’s (1992) continuous-state branching process was constructed by Fleischmann and Sturm (2004). This superprocess with infinite mean branching behaves quite differently from usual supercritical spatial branching processes. In fact, at macroscopic scales, the mass renormalized to a (random) probability measure is concentrated in a single space point which randomly fluctuates according to the underlying symmetric stable motion process.     

A family of kurtosis orderings for multivariate distributions

In this paper, a family of kurtosis orderings for multivariate distributions is proposed and studied. Each ordering characterizes in an affine invariant sense the movement of probability mass from the “shoulders” of a distribution to either the center or the tails or both. All even moments of the Mahalanobis distance of a random vector from its mean (if exists) preserve a subfamily of the orderings. For elliptically symmetric distributions, each ordering determines the distributions up to affine equivalence. As applications, the orderings are used to study elliptically symmetric distributions. Ordering results are established for three important families of elliptically symmetric distributions: Kotz type distributions, Pearson Type VII distributions, and Pearson Type II distributions.     

The chromatic number of random Borsuk graphs

We study a model of random graph where vertices are n i.i.d. uniform random points on the unit sphere S^d in , and a pair of vertices is connected if the Euclidean distance between them is at least 2??. We are interested in the chromatic number of this graph as n tends to infinity. It is not too hard to see that if ?>0 is small and fixed, then the chromatic number is d+2 with high probability. We show that this holds even if ?→0 slowly enough. We quantify the rate at which ? can tend to zero and still have the same chromatic number. The proof depends on combining topological methods (namely the Lyusternik–Schnirelman–Borsuk theorem) with geometric probability arguments. The rate we obtain is best possible, up to a constant factor—if ?→0 faster than this, we show that the graph is (d+1)‐colorable with high probability.25     

Limits of discrete distributions and Gibbs measures on random graphs

Building upon the theory of graph limits and the Aldous–Hoover representation and inspired by Panchenko’s work on asymptotic Gibbs measures [Annals of Probability 2013], we construct continuous embeddings of discrete probability distributions. We show that the theory of graph limits induces a meaningful notion of convergence and derive a corresponding version of the Szemerédi regularity lemma. Moreover, complementing recent work Bapst et al. (2015), we apply these results to Gibbs measures induced by sparse random factor graphs and verify the “replica symmetric solution” predicted in the physics literature under the assumption of non-reconstruction.     

Local probabilities and total variation distance for random permutations

We are concerned with permutations taken uniformly at random from the symmetric group. Firstly, we study the probability of a permutation missing short cycles. Secondly, the result is employed to establish a formula for total variation distance between the process of multiplicities of cycle lengths in a random permutation and a process of independent Poisson random variables. We apply an analytic approach originated in number theory (K. Gyory et al. (Eds.) in Number Theory in Progress, 1999).     

An algorithm for finding hamilton paths and cycles in random graphs

This paper describes a polynomial time algorithm HAM that searches for Hamilton cycles in undirected graphs. On a random graph its asymptotic probability of success is that of the existence of such a cycle. If all graphs withn vertices are considered equally likely, then using dynamic programming on failure leads to an algorithm with polynomial expected time. The algorithm HAM is also used to solve the symmetric bottleneck travelling salesman problem with probability tending to 1, asn tends to ∞. Various modifications of HAM are shown to solve several Hamilton path problems. Supported by NSF Grant MCS 810 4854.     

Variable orderings and the size of OBDDs for random partially symmetric Boolean functions

The size of ordered binary decision diagrams (OBDDs) strongly depends on the chosen variable ordering. It is an obvious heuristic to use symmetric variable orderings, i.e., variable orderings where symmetric variables are arranged adjacently. In order to evaluate this heuristic, methods for estimating the OBDD size for random partially symmetric functions are presented. Characterizations of cases where, with high probability, only symmetric variable orderings and, with high probability, only nonsymmetric variable orderings lead to minimum OBDD size are obtained. For this analysis estimates for the number of different blocks of random Boolean matrices are used. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13, 49–70, 1998     

Asymmetry and structural information in preferential attachment graphs

Graph symmetries intervene in diverse applications, from enumeration, to graph structure compression, to the discovery of graph dynamics (e.g., node arrival order inference). Whereas Erd?s‐Rényi graphs are typically asymmetric, real networks are highly symmetric. So a natural question is whether preferential attachment graphs, where in each step a new node with m edges is added, exhibit any symmetry. In recent work it was proved that preferential attachment graphs are symmetric for m = 1, and there is some nonnegligible probability of symmetry for m = 2. It was conjectured that these graphs are asymmetric when m ≥ 3. We settle this conjecture in the affirmative, then use it to estimate the structural entropy of the model. To do this, we also give bounds on the number of ways that the given graph structure could have arisen by preferential attachment. These results have further implications for information theoretic problems of interest on preferential attachment graphs.     

The Median of the Number of Simple Paths on Three Vertices in the Random Graph

We study the asymptotic behavior of the random variable equal to the number of simple paths on three vertices in the binomial random graph in which the edge probability equals the threshold probability of the appearance of such paths. We prove that, for any fixed nonnegative integer b and a sufficiently large number n of vertices of the graph, the probability that the number of simple paths on three vertices in the given random graph is b decreases with n. As a consequence of this result, we obtain the median of the number of simple paths on three vertices for sufficiently large n.

     

Asymptotic normality in random graphs with given vertex degrees

We consider random graphs with a given degree sequence and show, under weak technical conditions, asymptotic normality of the number of components isomorphic to a given tree, first for the random multigraph given by the configuration model and then, by a conditioning argument, for the simple uniform random graph with the given degree sequence. Such conditioning is standard for convergence in probability, but much less straightforward for convergence in distribution as here. The proof uses the method of moments, and is based on a new estimate of mixed cumulants in a case of weakly dependent variables. The result on small components is applied to give a new proof of a recent result by Barbour and Röllin on asymptotic normality of the size of the giant component in the random multigraph; moreover, we extend this to the random simple graph.