二分图中俩集合中节点数与连边概率的关系

Question

1.考虑ER随机图G（N，p），其中给定N＝2000和p＝0.003。请计算度值k＞2倍的平均度的节点数量的期望值。
2.构造一个二分的随机图如下：假设集合X和Y中分别有Nx和Ny个节点，并且对于集合X中的任一节点，它和集合Y中任一节点之间有边相连的概率均为p。如果要使得集合Y中任一节点都以概率1与集合X中的至少一个节点有边相连，请给出参数Nx、Ny和p应满足的关系式。

Answer 1

首先，我们来解答这两个问题。

问题 1：ER随机图G(N, p)中特定度值节点的期望数量

在ER随机图（Erdős-Rényi图）G(N, p)中，每个节点都独立于其他节点，以概率p与其他节点相连。因此，对于一个特定的节点，其度值（连接的边的数量）遵循二项分布B(N-1, p)。图的平均度是p(N-1)。
对于问题1，我们需要找到度值大于2倍平均度的节点数量的期望值。首先，我们计算平均度，然后找到度值大于2倍平均度的概率，最后用这个概率乘以节点总数N得到期望值。

1. 计算平均度：平均度 = p(N-1)
2. 计算度值大于2倍平均度的概率：这可以通过计算度值小于或等于2倍平均度的概率，然后用1减去这个概率来得到。
3. 计算期望值：期望值 = N * 度值大于2倍平均度的概率
   现在，我们可以使用这些步骤来计算具体的数值。

   问题 2：二分随机图中集合间连边概率

   在二分随机图中，要使集合Y中的每个节点都以概率1至少与集合X中的一个节点相连，我们需要保证对于集合Y中的任意节点，至少有一条边与集合X中的某个节点相连。
   这可以通过以下方式计算：
4. 集合Y中任一节点至少有一条边与集合X相连的概率：这等于1减去集合Y中任一节点与集合X中所有节点都没有边相连的概率。后者是(1-p)^Nx。
5. 要使这个概率为1，我们需要(1-p)^Nx趋近于0，即p足够大，使得(1-p)^Nx = 0。
   现在，我们可以用Python来计算这些值。
   from scipy.stats import binom

   问题 1 的参数

   N = 2000 # 节点总数
   p = 0.003 # 连接概率

   计算平均度

   average_degree = p * (N - 1)

   计算度值小于或等于2倍平均度的概率

   prob_less_than_2_avg = binom.cdf(2 * average_degree, N - 1, p)

   计算度值大于2倍平均度的概率

   prob_more_than_2_avg = 1 - prob_less_than_2_avg

   计算期望值

   expected_number_of_nodes = N * prob_more_than_2_avg
   average_degree, prob_more_than_2_avg, expected_number_of_nodes
   (5.997, 0.019855898110872627, 39.71179622174525)
   对于问题1：

• 在ER随机图G(N, p)中，平均度为5.997。
• 度值大于2倍平均度的概率约为1.99%。
• 因此，期望的节点数量，其度值大于2倍平均度，约为39.71个。

  问题 2：二分随机图中集合间连边概率

  对于问题2，要使集合Y中的每个节点至少以概率1与集合X中的一个节点相连，我们需要满足以下条件：

1. 集合Y中任一节点至少有一条边与集合X相连的概率：这等于1减去该节点与集合X中所有节点都没有边相连的概率。这个概率是(1-p)^Nx。
2. 要使这个概率为1，我们需要(1-p)^Nx趋近于0。这意味着p需要足够大，以使(1-p)^Nx = 0。
   因此，参数Nx、Ny和p应满足的关系式为：
   $$
   (1-p)^{Nx} = 0
   $$
   由于任何数的0次幂都是1，而不是0，所以实际上我们不能有一个精确的p值使得(1-p)^Nx等于0。但是，为了使这个概率非常接近于0，p需要非常大，接近于1。换句话说，几乎所有的边都需要存在，以确保每个节点至少有一条边与另一个集合相连。