Phase transitions for detecting latent geometry in random graphs
Phase transitions for detecting latent geometry in random graphs
复制标题
用于检测随机图中潜在几何形状的相变
DOI：
10.1007/s00440-020-00998-3
复制
发表时间：
2020
影响因子：
2
通讯作者：
Nagaraj, Dheeraj
中科院分区：
文献类型：
--
作者：
Brennan, Matthew;Bresler, Guy;Nagaraj, Dheeraj
具有潜在几何结构的随机图是社交和生物网络的流行模型，其应用范围从网络用户分析到电路设计。这些图表在计算机科学、概率和统计学领域也具有纯粹的理论意义。关于这些模型的一个基本的初始问题是：这些随机图何时受到其潜在几何形状的影响，何时它们与没有潜在结构的简单模型（例如 Erdős-Rényi 图）无法区分？我们针对两个研究最深入的具有潜在几何的随机图模型（随机交集和随机几何图）来解决这个问题。我们的结果如下：（a）随机交集图是通过对n个随机集进行采样来定义的，通过以概率独立地包括大小集合中的每个元素，并包括edgeif。我们证明，对于密集边缘密度 p 和稀疏边缘密度 p，随机交集图在全变分中收敛于 Erdős-Rényi 图，如果，并且不会。这解决了 Fill 等人中的一个悬而未决的问题。 （随机结构算法 16(2):156–176, 2000），Rybarczyk（随机结构算法 38(1–2):205–234, 2011）和 Kim 等人。 （随机结构算法 52(4):662–679, 2018）。 Bubeck 等人同时独立地获得了相同的结果。 （当随机相交图失去几何形状时。手稿，2019）。 (b) 我们强化了前面的论点，以表明随机交集大小的矩阵在全变分中收敛到具有独立泊松项的对称矩阵。这产生了随机相交图的第一个全变分收敛结果，其中包括边缘。更准确地说，我们的结果意味着，如果 p 远离 1，则边缘密度 p 的随机交集图收敛到 if。 (c) 随机几何图on是通过从边if（包括边if）均匀随机采样来定义的。 Bubeck 等人的结果。 （Random Struct Algorithms 49:503–532, 2016）表明，该模型收敛于总变分，其中 p 的选择使得模型具有匹配的边缘密度，只要。这是 Bubeck 等人的推测。 (2016) 认为这个阈值对于 psmall 来说急剧下降。我们通过展示收敛性 if ，在这个猜想上取得了第一个进展。我们的证明是组合论证、直接耦合和信息不等式应用的混合体。先前具有潜在几何的随机图之间总变异距离的上限通常不是组合论和信息论的，而这种相互作用对于我们边界的清晰度至关重要。
Random graphs with latent geometric structure are popular models of social and biological networks, with applications ranging from network user profiling to circuit design. These graphs are also of purely theoretical interest within computer science, probability and statistics. A fundamental initial question regarding these models is: when are these random graphs affected by their latent geometry and when are they indistinguishable from simpler models without latent structure, such as the Erdős–Rényi graph? We address this question for two of the most well-studied models of random graphs with latent geometry—the random intersection and random geometric graph. Our results are as follows: (a) The random intersection graph is defined by samplingnrandom setsby including each element of a set of sizedin eachindependently with probability, and including the edgeif. We prove that the random intersection graph converges in total variation to an Erdős–Rényi graph if, and does not if, for both dense and sparse edge densitiesp. This resolves an open problem in Fill et al. (Random Struct Algorithms 16(2):156–176, 2000), Rybarczyk (Random Struct Algorithms 38(1–2):205–234, 2011) and Kim et al. (Random Struct Algorithms 52(4):662–679, 2018). The same result was obtained simultaneously and independently by Bubeck et al. (When random intersection graphs lose geometry. Manuscript, 2019). (b) We strengthen the preceding argument to show that the matrix of random intersection sizesconverges in total variation to a symmetric matrix with independent Poisson entries. This yields the first total variation convergence result for-random intersection graphs, where the edgeis included if. More precisely, our results imply that, ifpis bounded away from 1, then the-random intersection graph with edge densitypconverges toif. (c) The random geometric graph onis defined by samplinguniformly at random fromand including the edgeif. A result of Bubeck et al. (Random Struct Algorithms 49:503–532, 2016) showed that this model converges toin total variation, wherepis chosen so that the models have matching edge densities, as long as. It was conjectured in Bubeck et al. (2016) that this threshold decreases drastically forpsmall. We make the first progress towards this conjecture by showing convergence if. Our proofs are a hybrid of combinatorial arguments, direct couplings and applications of information inequalities. Previous upper bounds on the total variation distance between random graphs with latent geometry andhave typically not been both combinatorial and information-theoretic, while this interplay is essential to the sharpness of our bounds.
登录
查看更多内容
DOI：
--
发表时间：
2020-05
期刊：
--
影响因子：
--
作者：
Matthew Brennan;Guy Bresler
通讯作者：
Matthew Brennan;Guy Bresler
全可见下随机密钥预分配方案导出的随机图
DOI：
--
发表时间：
2008
期刊：
2008 IEEE International Symposium on Information Theory
影响因子：
--
作者：
Osman Yağan;A. Makowski
通讯作者：
A. Makowski
影响因子：
--
作者：
Ronen Eldan;Dan Mikulincer
通讯作者：
Dan Mikulincer
DOI：
--
发表时间：
2015
期刊：
影响因子：
--
作者：
Will Perkins
通讯作者：
Will Perkins
随机交集图与 G(n,p) 的等价
DOI：
--
发表时间：
2009
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
K. Rybarczyk
通讯作者：
K. Rybarczyk