Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA curious gap in one-dimensional geometric random graphs between connectivity and the absence of isolated node
93
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
One-dimensional geometric random graphs are constructed by distributing $n$ nodes uniformly and independently on a unit interval and then assigning an undirected edge between any two nodes that have a distance at most $r_n$. These graphs have received much interest and been used in various applications including wireless networks. A threshold of $r_n$ for connectivity is known as $r_n^{*} = frac{ln n}{n}$ in the literature. In this paper, we prove that a threshold of $r_n$ for the absence of isolated node is $frac{ln n}{2 n}$ (i.e., a half of the threshold $r_n^{*}$). Our result shows there is a curious gap between thresholds of connectivity and the absence of isolated node in one-dimensional geometric random graphs; in particular, when $r_n$ equals $frac{cln n}{ n}$ for a constant $c in( frac{1}{2}, 1)$, a one-dimensional geometric random graph has no isolated node but is not connected. This curious gap in one-dimensional geometric random graphs is in sharp contrast to the prevalent phenomenon in many other random graphs such as two-dimensional geometric random graphs, ErdH{o}s-Renyi graphs, and random intersection graphs, all of which in the asymptotic sense become connected as soon as there is no isolated node.
rate research
Read More
Random $s$-intersection graphs have recently received considerable attention in a wide range of application areas. In such a graph, each vertex is equipped with a set of items in some random manner, and any two vertices establish an undirected edge in between if and only if they have at least $s$ common items. In particular, in a uniform random $s$-intersection graph, each vertex independently selects a fixed number of items uniformly at random from a common item pool, while in a binomial random $s$-intersection graph, each item in some item pool is independently attached to each vertex with the same probability. For binomial/uniform random $s$-intersection graphs, we establish threshold functions for perfect matching containment, Hamilton cycle containment, and $k$-robustness, where $k$-robustness is in the sense of Zhang and Sundaram [IEEE Conf. on Decision & Control 12]. We show that these threshold functions resemble those of classical ErdH{o}s-R{e}nyi graphs, where each pair of vertices has an undirected edge independently with the same probability.
How are people linked in a highly connected society? Since in many networks a power-law (scale-free) node-degree distribution can be observed, power-law might be seen as a universal characteristics of networks. But this study of communication in the Flickr social online network reveals that power-law node-degree distributions are restricted to only sparsely connected networks. More densely connected networks, by contrast, show an increasing divergence from power-law. This work shows that this observation is consistent with the classic idea from social sciences that similarity is the driving factor behind communication in social networks. The strong relation between communication strength and node similarity could be confirmed by analyzing the Flickr network. It also is shown that node similarity as a network formation model can reproduce the characteristics of different network densities and hence can be used as a model for describing the topological transition from weakly to strongly connected societies.
Connections between continuous and discrete worlds tend to be elusive. One example is curvature. Even though there exist numerous nonequivalent definitions of graph curvature, none is known to converge in any limit to any traditional definition of curvature of a Riemannian manifold. Here we show that Ollivier curvature of random geometric graphs in any Riemannian manifold converges in the continuum limit to Ricci curvature of the underlying manifold, but only if the definition of Ollivier graph curvature is properly generalized to apply to mesoscopic graph neighborhoods. This result establishes the first rigorous link between a definition of curvature applicable to networks and a traditional definition of curvature of smooth spaces.
Random geometric graphs consist of randomly distributed nodes (points), with pairs of nodes within a given mutual distance linked. In the usual model the distribution of nodes is uniform on a square, and in the limit of infinitely many nodes and shrinking linking range, the number of isolated nodes is Poisson distributed, and the probability of no isolated nodes is equal to the probability the whole graph is connected. Here we examine these properties for several self-similar node distributions, including smooth and fractal, uniform and nonuniform, and finitely ramified or otherwise. We show that nonuniformity can break the Poisson distribution property, but it strengthens the link between isolation and connectivity. It also stretches out the connectivity transition. Finite ramification is another mechanism for lack of connectivity. The same considerations apply to fractal distributions as smooth, with some technical differences in evaluation of the integrals and analytical arguments.
We propose a thermodynamic version of the Axelrod model of social influence. In one-dimensional (1D) lattices, the thermodynamic model becomes a coupled Potts model with a bonding interaction that increases with the site matching traits. We analytically calculate thermodynamic and critical properties for a 1D system and show that an order-disorder phase transition only occurs at T = 0 independent of the number of cultural traits q and features F. The 1D thermodynamic Axelrod model belongs to the same universality class of the Ising and Potts models, notwithstanding the increase of the internal dimension of the local degree of freedom and the state-dependent bonding interaction. We suggest a unifying proposal to compare exponents across different discrete 1D models. The comparison with our Hamiltonian description reveals that in the thermodynamic limit the original out-of-equilibrium 1D Axelrod model with noise behaves like an ordinary thermodynamic 1D interacting particle system.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
