53、图算法：随机图采样、循环枚举与 motif 分析

图算法：随机图采样、循环枚举与 motif 分析

1. 随机图采样算法

在图论中，有时我们需要生成具有特定度 - 度相关性的随机图。下面介绍的算法基于隐藏变量模型，能够根据给定图 $G$ 生成具有相同度 - 度概率分布的图 $G’$。

1.1 算法步骤

以下是该算法的伪代码：

Algorithm 39 hidden_variable() Input: G Output: i, j 1: pkk[][] ← degree_corr_distr(G) 2: rho[] ← compute_rho(pkk[]) 3: fhh[][] ← compute_fhh(pkk[]) 4: h[] ← sample_node_variables(rho[]) 5: K ← 0 6: for n1 in 0 to N-1 do 7: h1 ← h[n1] 8: for n2 in i+1 to N-1 do 9: h2 ← h[n2] 10: v ← RAND(0,1) 11: if v < fhh[h1][h2] then 12: i[K] ← n1 13: j[K] ← n2 14: K ← K + 1 15: end if 16: end for 17: end for 18: return i, j

具体步骤解释如下：
1.计算度 - 度概率分布：使用degree_corr_distr(G) <