ترغب بنشر مسار تعليمي؟ اضغط هنا

On a general class of inhomogeneous random digraphs

110   0   0.0 ( 0 )
 نشر من قبل Mariana Olvera-Cravioto
 تاريخ النشر 2017
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

We study a family of directed random graphs whose arcs are sampled independently of each other, and are present in the graph with a probability that depends on the attributes of the vertices involved. In particular, this family of models includes as special cases the direct



قيم البحث

اقرأ أيضاً

We study the typical behavior of a generalized version of Googles PageRank algorithm on a large family of inhomogeneous random digraphs. This family includes as special cases direct
We study random digraphs on sequences of expanders with bounded average degree and weak local limit. The threshold for the existence of a giant strongly connected component, as well as the asymptotic fraction of nodes with giant fan-in or giant fan-o ut are local, in the sense that they are the same for two sequences with the same weak local limit. The digraph has a bow-tie structure, with all but a vanishing fraction of nodes lying either in the unique strongly connected giant and its fan-in and fan-out, or in sets with small fan-in and small fan-out. All local quantities are expressed in terms of percolation on the limiting rooted graph, without any structural assumptions on the limit, allowing, in particular, for non tree-like limits. In the course of proving these results, we prove that for unoriented percolation, there is a unique giant above criticality, whose size and critical threshold are again local. An application of our methods shows that the critical threshold for bond percolation and random digraphs on preferential attachment graphs is $p_c=0$, with an infinite order phase transition at $p_c$.
The voter model is a classical interacting particle system modelling how consensus is formed across a network. We analyse the time to consensus for the voter model when the underlying graph is a subcritical scale-free random graph. Moreover, we gener alise the model to include a `temperature parameter. The interplay between the temperature and the structure of the random graph leads to a very rich phase diagram, where in the different phases different parts of the underlying geometry dominate the time to consensus. Finally, we also consider a discursive voter model, where voters discuss their opinions with their neighbours. Our proofs rely on the well-known duality to coalescing random walks and a detailed understanding of the structure of the random graphs.
We prove the universality for the eigenvalue gap statistics in the bulk of the spectrum for band matrices, in the regime where the band width is comparable with the dimension of the matrix, $Wsim N$. All previous results concerning universality of no n-Gaussian random matrices are for mean-field models. By relying on a new mean-field reduction technique, we deduce universality from quantum unique ergodicity for band matrices.
Consider a set of $n$ vertices, where each vertex has a location in $mathbb{R}^d$ that is sampled uniformly from the unit cube in $mathbb{R}^d$, and a weight associated to it. Construct a random graph by placing edges independently for each vertex pa ir with a probability that is a function of the distance between the locations, and the vertex weights. Under appropriate integrability assumptions on the edge probabilities that imply sparseness of the model, after appropriately blowing up the locations, we prove that the local limit of this random graph sequence is the (countably) infinite random graph on $mathbb{R}^d$ with vertex locations given by a homogeneous Poisson point process, having weights which are i.i.d. copies of limiting vertex weights. Our setup covers many sparse geometric random graph models from the literature, including Geometric Inhomogeneous Random Graphs (GIRGs), Hyperbolic Random Graphs, Continuum Scale-Free Percolation and Weight-dependent Random Connection Models. We prove that the limiting degree distribution is mixed Poisson, and the typical degree sequence is uniformly integrable, and obtain convergence results on various measures of clustering in our graphs as a consequence of local convergence. Finally, as a by-product of our argument, we prove a doubly logarithmic lower bound on typical distances in this general setting.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا