Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSampling perspectives on sparse exchangeable graphs
103
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Recent work has introduced sparse exchangeable graphs and the associated graphex framework, as a generalization of dense exchangeable graphs and the associated graphon framework. The development of this subject involves the interplay between the statistical modeling of network data, the theory of large graph limits, exchangeability, and network sampling. The purpose of the present paper is to clarify the relationships between these subjects by explaining each in terms of a certain natural sampling scheme associated with the graphex model. The first main technical contribution is the introduction of sampling convergence, a new notion of graph limit that generalizes left convergence so that it becomes meaningful for the sparse graph regime. The second main technical contribution is the demonstration that the (somewhat cryptic) notion of exchangeability underpinning the graphex framework is equivalent to a more natural probabilistic invariance expressed in terms of the sampling scheme.
rate research
Read More
We study the spectrum of a random multigraph with a degree sequence ${bf D}_n=(D_i)_{i=1}^n$ and average degree $1 ll omega_n ll n$, generated by the configuration model, and also the spectrum of the analogous random simple graph. We show that, when the empirical spectral distribution (ESD) of $omega_n^{-1} {bf D}_n $ converges weakly to a limit $ u$, under mild moment assumptions (e.g., $D_i/omega_n$ are i.i.d. with a finite second moment), the ESD of the normalized adjacency matrix converges in probability to $ uboxtimes sigma_{rm sc}$, the free multiplicative convolution of $ u$ with the semicircle law. Relating this limit with a variant of the Marchenko--Pastur law yields the continuity of its density (away from zero), and an effective procedure for determining its support. Our proof of convergence is based on a coupling between the random simple graph and multigraph with the same degrees, which might be of independent interest. We further construct and rely on a coupling of the multigraph to an inhomogeneous ErdH{o}s-Renyi graph with the target ESD, using three intermediate random graphs, with a negligible fraction of edges modified in each step.
We consider sampling and enumeration problems for Markov equivalence classes. We create and analyze a Markov chain for uniform random sampling on the DAGs inside a Markov equivalence class. Though the worst case is exponentially slow mixing, we find a condition on the Markov equivalence class for polynomial time mixing. We also investigate the ratio of Markov equivalence classes to DAGs and a Markov chain of He, Jia, and Yu for random sampling of sparse Markov equivalence classes.
A coupling of random walkers on the same finite graph, who take turns sequentially, is said to be an avoidance coupling if the walkers never collide. Previous studies of these processes have focused almost exclusively on complete graphs, in particular how many walkers an avoidance coupling can include. For other graphs, apart from special cases, it has been unsettled whether even two non-colliding simple random walkers can be coupled. In this article, we construct such a coupling on (i) any $d$-regular graph avoiding a fixed subgraph depending on $d$; and (ii) any square-free graph with minimum degree at least three. A corollary of the first result is that a uniformly random regular graph on $n$ vertices admits an avoidance coupling with high probability.
We consider the spectral gap of a uniformly chosen random $(d_1,d_2)$-biregular bipartite graph $G$ with $|V_1|=n, |V_2|=m$, where $d_1,d_2$ could possibly grow with $n$ and $m$. Let $A$ be the adjacency matrix of $G$. Under the assumption that $d_1geq d_2$ and $d_2=O(n^{2/3}),$ we show that $lambda_2(A)=O(sqrt{d_1})$ with high probability. As a corollary, combining the results from Tikhomirov and Youssef (2019), we confirm a conjecture in Cook (2017) that the second singular value of a uniform random $d$-regular digraph is $O(sqrt{d})$ for $1leq dleq n/2$ with high probability. This also implies that the second eigenvalue of a uniform random $d$-regular digraph is $O(sqrt{d})$ for $1leq dleq n/2$ with high probability. Assuming $d_2=O(1)$ and $d_1=O(n^2)$, we further prove that for a random $(d_1,d_2)$-biregular bipartite graph, $|lambda_i^2(A)-d_1|=O(sqrt{d_1(d_2-1)})$ for all $2leq ileq n+m-1$ with high probability. The proofs of the two results are based on the size biased coupling method introduced in Cook, Goldstein, and Johnson (2018) for random $d$-regular graphs and several new switching operations we defined for random bipartite biregular graphs.
We introduce two new bootstraps for exchangeable random graphs. One, the empirical graphon, is based purely on resampling, while the other, the histogram stochastic block model, is a model-based sieve bootstrap. We show that both of them accurately approximate the sampling distributions of motif densities, i.e., of the normalized counts of the number of times fixed subgraphs appear in the network. These densities characterize the distribution of (infinite) exchangeable networks. Our bootstraps therefore give, for the first time, a valid quantification of uncertainty in inferences about fundamental network statistics, and so of parameters identifiable from them.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
