论文标题
无界等级的随机图中的渗透
Percolation in Random Graphs of Unbounded Rank
论文作者
论文摘要
（随机）图中的引导性渗透是一组具有一定阈值级别的顶点之间的传染性动力学。该过程由一组最初感染的顶点开始，最初未感染的带有阈值$ K $的顶点在其受感染邻居的数量超过$ K $后立即被感染。该过程已在所谓的\ textit {rank One}模型中进行了广泛的研究。这些模型可以生成带有重尾度序列的随机图，但它们无法聚类。在本文中，我们处理一类无限等级的随机图，这些图允许大量聚类。我们的主要结果确定了被感染顶点的最终部分是在合适的功能空间上定义的非线性操作员的固定点。我们提出了一种促进神经网络以有效计算该固定点的算法。我们基于操作员的Fréchet导数进一步得出标准，该标准允许人们确定小型感染是通过整个图传播的还是保持本地的。
Bootstrap percolation in (random) graphs is a contagion dynamics among a set of vertices with certain threshold levels. The process is started by a set of initially infected vertices, and an initially uninfected vertex with threshold $k$ gets infected as soon as the number of its infected neighbors exceeds $k$. This process has been studied extensively in so called \textit{rank one} models. These models can generate random graphs with heavy-tailed degree sequences but they are not capable of clustering. In this paper, we treat a class of random graphs of unbounded rank which allow for extensive clustering. Our main result determines the final fraction of infected vertices as the fixed point of a non-linear operator defined on a suitable function space. We propose an algorithm that facilitates neural networks to calculate this fixed point efficiently. We further derive criteria based on the Fréchet derivative of the operator that allows one to determine whether small infections spread through the entire graph or rather stay local.
