Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDirected Random Geometric Graphs
72
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Many real-world networks are intrinsically directed. Such networks include activation of genes, hyperlinks on the internet, and the network of followers on Twitter among many others. The challenge, however, is to create a network model that has many of the properties of real-world networks such as powerlaw degree distributions and the small-world property. To meet these challenges, we introduce the textit{Directed} Random Geometric Graph (DRGG) model, which is an extension of the random geometric graph model. We prove that it is scale-free with respect to the indegree distribution, has binomial outdegree distribution, has a high clustering coefficient, has few edges and is likely small-world. These are some of the main features of aforementioned real world networks. We empirically observe that word association networks have many of the theoretical properties of the DRGG model.
rate research
Read More
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.
Using the replica method, we develop an analytical approach to compute the characteristic function for the probability $mathcal{P}_N(K,lambda)$ that a large $N times N$ adjacency matrix of sparse random graphs has $K$ eigenvalues below a threshold $lambda$. The method allows to determine, in principle, all moments of $mathcal{P}_N(K,lambda)$, from which the typical sample to sample fluctuations can be fully characterized. For random graph models with localized eigenvectors, we show that the index variance scales linearly with $N gg 1$ for $|lambda| > 0$, with a model-dependent prefactor that can be exactly calculated. Explicit results are discussed for Erdos-Renyi and regular random graphs, both exhibiting a prefactor with a non-monotonic behavior as a function of $lambda$. These results contrast with rotationally invariant random matrices, where the index variance scales only as $ln N$, with an universal prefactor that is independent of $lambda$. Numerical diagonalization results confirm the exactness of our approach and, in addition, strongly support the Gaussian nature of the index fluctuations.
We study sums of directed paths on a hierarchical lattice where each bond has either a positive or negative sign with a probability $p$. Such path sums $J$ have been used to model interference effects by hopping electrons in the strongly localized regime. The advantage of hierarchical lattices is that they include path crossings, ignored by mean field approaches, while still permitting analytical treatment. Here, we perform a scaling analysis of the controversial ``sign transition using Monte Carlo sampling, and conclude that the transition exists and is second order. Furthermore, we make use of exact moment recursion relations to find that the moments $<J^n>$ always determine, uniquely, the probability distribution $P(J)$. We also derive, exactly, the moment behavior as a function of $p$ in the thermodynamic limit. Extrapolations ($nto 0$) to obtain $<ln J>$ for odd and even moments yield a new signal for the transition that coincides with Monte Carlo simulations. Analysis of high moments yield interesting ``solitonic structures that propagate as a function of $p$. Finally, we derive the exact probability distribution for path sums $J$ up to length L=64 for all sign probabilities.
For a directed graph $G(V_n, E_n)$ on the vertices $V_n = {1,2, dots, n}$, we study the distribution of a Markov chain ${ {bf R}^{(k)}: k geq 0}$ on $mathbb{R}^n$ such that the $i$th component of ${bf R}^{(k)}$, denoted $R_i^{(k)}$, corresponds to the value of the process on vertex $i$ at time $k$. We focus on processes ${ {bf R}^{(k)}: k geq 0}$ where the value of $R_i^{(k+1)}$ depends only on the values ${ R_j^{(k)}: j to i}$ of its inbound neighbors, and possibly on vertex attributes. We then show that, provided $G(V_n, E_n)$ converges in the local weak sense to a marked Galton-Watson process, the dynamics of the process for a uniformly chosen vertex in $V_n$ can be coupled, for any fixed $k$, to a process ${ mathcal{R}_emptyset^{(r)}: 0 leq r leq k}$ constructed on the limiting marked Galton-Watson tree. Moreover, we derive sufficient conditions under which $mathcal{R}^{(k)}_emptyset$ converges, as $k to infty$, to a random variable $mathcal{R}^*$ that can be characterized in terms of the attracting endogenous solution to a branching distributional fixed-point equation. Our framework can also be applied to processes ${ {bf R}^{(k)}: k geq 0}$ whose only source of randomness comes from the realization of the graph $G(V_n, E_n)$.
We show that, in almost every $n$-vertex random directed graph process, a copy of every possible $n$-vertex oriented cycle will appear strictly before a directed Hamilton cycle does, except of course for the directed cycle itself. Furthermore, given an arbitrary $n$-vertex oriented cycle, we determine the sharp threshold for its appearance in the binomial random directed graph. These results confirm, in a strong form, a conjecture of Ferber and Long.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
