论文标题
双边协议家族的连通性随机图
Connectivity of a Family of Bilateral Agreement Random Graphs
论文作者
论文摘要
LA和KABKAB在2015年引入和分析了基于双边协议的随机无向图。该模型中使用$ n $顶点的图形构造使用了其他$ N-1 $顶点上的（随机）偏好顺序，每个顶点仅优先使用其自身的优先顺序，首先优先$ K $其他顶点；通常，$ k $可以是$ n $的函数。当且仅当潜在边缘的两个顶点彼此都偏爱时，随后的图中构建边缘。此随机图是对随机$ k^{th} $的概括 - 库珀和frize的最接近的邻居图，仅考虑了顶点的单方面偏好。 Moharrami \ emph {et al。}研究了巨大组件的出现及其在这个新的随机图系列中的大小，限制为$ n $，当$ k $是有限的。该随机图家族的连通性特性尚未正式分析。在其原始论文中，La和Kabkab猜想，对于$ k（t）= t \ log n $，具有高概率连接性的情况发生在$ t> 1 $，并且该图以$ t <1 $而断开。我们提供了这种猜想的证明。我们还将针对该图的平均程度引入渐近学。
Bilateral agreement based random undirected graphs were introduced and analyzed by La and Kabkab in 2015. The construction of the graph with $n$ vertices in this model uses a (random) preference order on other $n-1$ vertices and each vertex only prefers the top $k$ other vertices using its own preference order; in general, $k$ can be a function of $n$. An edge is constructed in the ensuing graph if and only if both vertices of a potential edge prefer each other. This random graph is a generalization of the random $k^{th}$-nearest neighbor graphs of Cooper and Frieze that only consider unilateral preferences of the vertices. Moharrami \emph{et al.} studied the emergence of a giant component and its size in this new random graph family in the limit of $n$ going to infinity when $k$ is finite. Connectivity properties of this random graph family have not yet been formally analyzed. In their original paper, La and Kabkab conjectured that for $k(t)=t \log n$, with high probability connectivity happens at $t>1$ and the graph is disconnected for $t<1$. We provide a proof for this conjecture. We will also introduce an asymptotic for the average degree of this graph.
