论文标题
与幂律分布的小世界图中的键渗透
Bond Percolation in Small-World Graphs with Power-Law Distribution
论文作者
论文摘要
\ emph {带有参数$ p $的全键渗透}是一个过程，在该过程中，对于每个边缘，我们独立删除了概率$ 1-p $的边缘。键渗透是由数学物理问题中的问题进行的，并在平行计算和网络科学中进行了研究，以了解分布式系统对随机链路失败的弹性以及通过不可靠的链接在网络中信息传播的弹性。 全键渗透也等同于\ emph {reed-frost Process}，这是\ emph {sir}流行病的网络版本，其中该图代表人们之间的联系，$ p $对应于感染者和敏感的人之间接触的可能性，引起了感染的传播。 我们将\ emph {一维幂律小型图形}以参数$α$作为一个周期的结合，并具有额外的长距离随机边缘的结合：每对距离的节点$（u，v）$在距离$ l $ l $ l $ l $连接，由长距离的边缘$（u，v）$连接，并以$ 1/l l^al $ 1/l^al $ 1/l^al $ 1/l^al $ l^ach。我们的分析确定了小型世界图的渗透子图$ g_p $的三个阶段，具体取决于$α$的值。 1）如果$α<1 $，则有一个$ p <1 $，因此，有可能有$ω（n）$ nodes，可以在$ o（\ log n）$ hops中彼此之间的$ g_p $中触及$ g_p $; 2）如果$ 1 <α<2 $，则有一个$ p <1 $，这样，有了很高的概率，就有$ω（n）$节点可以在$ g_p $中从$ \ log \ log^{o（1）}（n）$ hops中互相达到$ g_p $; 3）如果$α> 2 $，对于每$ p <1 $，则具有较高概率的所有连接组件的$ g_p $具有尺寸$ o（\ log n）$。 在本文中研究的有限图中的全键渗透设置，这是与网络SIR SIR模型相对应的流行病扩散模型的设置。
\emph{Full-bond percolation} with parameter $p$ is the process in which, given a graph, for every edge independently, we delete the edge with probability $1-p$. Bond percolation is motivated by problems in mathematical physics and it is studied in parallel computing and network science to understand the resilience of distributed systems to random link failure and the spread of information in networks through unreliable links. Full-bond percolation is also equivalent to the \emph{Reed-Frost process}, a network version of \emph{SIR} epidemic spreading, in which the graph represents contacts among people and $p$ corresponds to the probability that a contact between an infected person and a susceptible one causes a transmission of the infection. We consider \emph{one-dimensional power-law small-world graphs} with parameter $α$ obtained as the union of a cycle with additional long-range random edges: each pair of nodes $(u,v)$ at distance $L$ on the cycle is connected by a long-range edge $(u,v)$, with probability proportional to $1/L^α$. Our analysis determines three phases for the percolation subgraph $G_p$ of the small-world graph, depending on the value of $α$. 1) If $α< 1$, there is a $p<1$ such that, with high probability, there are $Ω(n)$ nodes that are reachable in $G_p$ from one another in $O(\log n)$ hops; 2) If $1 < α< 2$, there is a $p<1$ such that, with high probability, there are $Ω(n)$ nodes that are reachable in $G_p$ from one another in $\log^{O(1)}(n)$ hops; 3) If $α> 2$, for every $p<1$, with high probability all connected components of $G_p$ have size $O(\log n)$. The setting of full-bond percolation in finite graphs studied in this paper, which is the one that corresponds to the network SIR model of epidemic spreading, had not been analyzed before.
