解释ER模型聚类系数为C=P=<k>/N
时间: 2024-05-31 12:11:01 浏览: 11
ER模型是一种随机图模型,用于描述节点和边的随机生成过程。在ER模型中,节点和边的数量是随机的,并且它们之间的连边也是随机的。因此,ER模型的聚类系数是一个平均值,表示节点之间的紧密连接程度。
C表示聚类系数,P表示三角形的数量,k表示节点的度数,N表示节点的数量。
在ER模型中,每个节点的度数k是一个随机变量,它服从泊松分布。因此,节点i的度数ki的期望值为λ,即ki ~ Poisson(λ)。
考虑一个节点i,如果它有ki个邻居,则它最多能形成ki*(ki-1)/2个三角形。但是,由于ER模型是随机的,不是所有的三角形都会形成。假设任意两个节点之间连边的概率是p,则节点i形成三角形的概率是p^ki*(ki-1)/2。因此,节点i形成的三角形的期望数量为:
E(Pi) = p^ki*(ki-1)/2 * (N-1 choose ki) ≈ p^ki*(ki-1)/2 * (N-1)^ki / ki!
其中,(N-1 choose ki)表示从其它N-1个节点中选择ki个节点作为节点i的邻居的组合数。这个式子的近似是基于斯特林公式的,它可以用来计算组合数的近似值。
将Pi的期望值代入聚类系数的定义式中,得到:
C = (1/N) * sum(Pi/ki) ≈ (1/N) * sum(p^ki*(ki-1)/2 * (N-1)^ki / ki! / ki)
约束ki的期望值为λ,即sum(ki)/N = λ。这个约束是因为节点的度数是泊松分布的,其期望值为λ。
根据泊松分布的性质,有:
sum(ki*(ki-1)/2 * p^ki / ki!) = λ^2 * e^(-λ) * (1-p)
将这个式子代入C的式子中,得到:
C ≈ (1/N) * λ^2 * e^(-λ) * (1-p) * sum((N-1)^ki / ki!)
考虑对sum((N-1)^ki / ki!)做一个近似。由于ki服从泊松分布,因此可以用泊松分布的特征函数来近似:
E(e^(t*ki)) = exp(λ*(e^t-1))
将t=ln(N-1)代入,得到:
E((N-1)^ki) ≈ exp(λ*(N-1)*(e^ln(N-1)-1))
将这个近似代入C的式子中,得到:
C ≈ (1/N) * λ^2 * e^(-λ) * (1-p) * exp(λ*(N-1)*(e^ln(N-1)-1))
对λ求偏导数,得到:
dC/dλ ≈ (1/N) * (2λ*e^(-λ) - λ^2*e^(-λ)) * (1-p) * exp(λ*(N-1)*(e^ln(N-1)-1)) + (1/N) * λ^2 * e^(-λ) * (1-p) * (N-1)*(e^ln(N-1)-1) * exp(λ*(N-1)*(e^ln(N-1)-1))
令dC/dλ=0,解得:
λ = ln(N) - ln(ln(N)) - 1/2
将这个解代入C的式子中,得到:
C ≈ ln(N)/N
这就是ER模型聚类系数的近似值。它可以看作是节点数量的对数级别,与节点的度数和连边概率无关。