Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHow likely is a random graph shift-enabled?
214
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The shift-enabled property of an underlying graph is essential in designing distributed filters. This article discusses when a random graph is shift-enabled. In particular, popular graph models ER, WS, BA random graph are used, weighted and unweighted, as well as signed graphs. Our results show that the considered unweighted connected random graphs are shift-enabled with high probability when the number of edges is moderately high. However, very dense graphs, as well as fully connected graphs, are not shift-enabled. Interestingly, this behaviour is not observed for weighted connected graphs, which are always shift-enabled unless the number of edges in the graph is very low.
rate research
Read More
We are given an integer $d$, a graph $G=(V,E)$, and a uniformly random embedding $f : V rightarrow {0,1}^d$ of the vertices. We are interested in the probability that $G$ can be realized by a scaled Euclidean norm on $mathbb{R}^d$, in the sense that there exists a non-negative scaling $w in mathbb{R}^d$ and a real threshold $theta > 0$ so that [ (u,v) in E qquad text{if and only if} qquad Vert f(u) - f(v) Vert_w^2 < theta,, ] where $| x |_w^2 = sum_i w_i x_i^2$. These constraints are similar to those found in the Euclidean minimum spanning tree (EMST) realization problem. A crucial difference is that the realization map is (partially) determined by the random variable $f$. In this paper, we consider embeddings $f : V rightarrow { x, y}^d$ for arbitrary $x, y in mathbb{R}$. We prove that arbitrary trees can be realized with high probability when $d = Omega(n log n)$. We prove an analogous result for graphs parametrized by the arboricity: specifically, we show that an arbitrary graph $G$ with arboricity $a$ can be realized with high probability when $d = Omega(n a^2 log n)$. Additionally, if $r$ is the minimum effective resistance of the edges, $G$ can be realized with high probability when $d=Omegaleft((n/r^2)log nright)$. Next, we show that it is necessary to have $d geq binom{n}{2}/6$ to realize random graphs, or $d geq n/2$ to realize random spanning trees of the complete graph. This is true even if we permit an arbitrary embedding $f : V rightarrow { x, y}^d$ for any $x, y in mathbb{R}$ or negative weights. Along the way, we prove a probabilistic analog of Radons theorem for convex sets in ${0,1}^d$. Our tree-realization result can complement existing results on statistical inference for gene expression data which involves realizing a tree, such as [GJP15].
Using three supercomputers, we broke a record set in 2011, in the enumeration of non-isomorphic regular graphs by expanding the sequence of A006820 in Online Encyclopedia of Integer Sequences (OEIS), to achieve the number for 4-regular graphs of order 23 as 429,668,180,677,439, while discovering serval optimal regular graphs with minimum average shortest path lengths (ASPL) that can be used as interconnection networks for parallel computers. The number of 4-regular graphs and the optimal graphs, extremely time-consuming to calculate, result from a method we adapt from GENREG, a classical regular graph generator, to fit for supercomputers strengths of using thousands of processor cores.
We analyze complex networks under random matrix theory framework. Particularly, we show that $Delta_3$ statistic, which gives information about the long range correlations among eigenvalues, provides a qualitative measure of randomness in networks. As networks deviate from the regular structure, $Delta_3$ follows random matrix prediction of linear behavior, in semi-logarithmic scale with the slope of $1/pi^2$, for the longer scale.
Exponential family Random Graph Models (ERGMs) can be viewed as expressing a probability distribution on graphs arising from the action of competing social forces that make ties more or less likely, depending on the state of the rest of the graph. Such forces often lead to a complex pattern of dependence among edges, with non-trivial large-scale structures emerging from relatively simple local mechanisms. While this provides a powerful tool for probing macro-micro connections, much remains to be understood about how local forces shape global outcomes. One simple question of this type is that of the conditions needed for social forces to stabilize a particular structure. We refer to this property as local stability and seek a general means of identifying the set of parameters under which a target graph is locally stable with respect to a set of alternatives. Here, we provide a complete characterization of the region of the parameter space inducing local stability, showing it to be the interior of a convex cone whose faces can be derived from the change-scores of the sufficient statistics vis-a-vis the alternative structures. As we show, local stability is a necessary but not sufficient condition for more general notions of stability, the latter of which can be explored more efficiently by using the ``stable cone within the parameter space as a starting point. In addition, we show how local stability can be used to determine whether a fitted model implies that an observed structure would be expected to arise primarily from the action of social forces, versus by merit of the model permitting a large number of high probability structures, of which the observed structure is one. We also use our approach to identify the dyads within a given structure that are the least stable, and hence predicted to have the highest probability of changing over time.
A simplified Doppler frequency shift measurement approach based on Serrodyne optical frequency translation is reported. A sawtooth wave with an appropriate amplitude is sent to one phase modulation arm of a Mach-Zehnder modulator in conjunction with the transmitted signal to implement the Serrodyne optical frequency transition, as well as the optical phase modulation of the transmitted signal on the frequency-shifted optical carrier. The echo signal is applied to the other phase modulation arm of the Mach-Zehnder modulator. The optical signals from the two arms are combined in the Mach-Zehnder modulator, whose lower optical sidebands are selected by an optical bandpass filter and then detected in a photodetector. By simply measuring the frequency of the output low-frequency signal, the value and direction of DFS can be determined simultaneously. An experiment is performed. DFS from -100 to 100 kHz is measured for microwave signals from 6 to 17 GHz with a measurement error of less than 0.03 Hz and a measurement stability of 0.015 Hz in 30 minutes when a 500-kHz sawtooth wave is used as the reference.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
