跳到内容

具有给定预期度的随机图

来源: R/games.R
sample_chung_lu.Rd

[Experimental]

Chung-Lu 模型可用于生成具有固定预期度的随机图。此函数实现了 Chung 和 Lu 的原始模型，以及一些具有有用属性的其他变体。

用法

sample_chung_lu(
  out.weights,
  in.weights = NULL,
  ...,
  loops = TRUE,
  variant = c("original", "maxent", "nr")
)

chung_lu(
  out.weights,
  in.weights = NULL,
  ...,
  loops = TRUE,
  variant = c("original", "maxent", "nr")
)

参数

out.weights

非负顶点权重（或出权重）向量。在稀疏图中，这些权重将近似等于预期（出）度。

in.weights

非负入权重向量，近似等于稀疏图中的预期入度。可以设置为 NULL，在这种情况下，将生成无向图。

...

这些点用于未来的扩展，并且必须为空。

loops

逻辑值，指示是否允许创建自环。由于顶点对是独立连接的，因此将此设置为 FALSE 等效于简单地从现有的带环 Chung-Lu 图中丢弃自环。

variant

要从中采样的模型变体，具有顶点 \(i\) 和 \(j\) 之间连接概率的不同定义。给定 \(q_{ij} = \frac{w_i w_j}{S}\)，以下公式可用

“original”

原始 Chung-Lu 模型，\(p_{ij} = \min(q_{ij}, 1)\)。

“maxent”

具有固定预期度的最大熵模型，\(p_{ij} = \frac{q_{ij}}{1 + q_{ij}}\)。

“nr”

Norros 和 Reittu 的模型，\(p_{ij} = 1 - \exp(-q_{ij})\)。

值

一个 igraph 图。

详细信息

在原始 Chung-Lu 模型中，每对顶点 \(i\) 和 \(j\) 以独立概率连接 $$p_{ij} = \frac{w_i w_j}{S},$$ 其中 \(w_i\) 是与顶点 \(i\) 关联的权重，$$S = \sum_k w_k$$ 是权重的总和。在有向变体中，顶点既有出权重 \(w^\text{out}\) 也有入权重 \(w^\text{in}\)，总和相等，$$S = \sum_k w^\text{out}_k = \sum_k w^\text{in}_k.$$ 顶点 \(i\) 和 \(j\) 之间的连接概率是 $$p_{ij} = \frac{w^\text{out}_i w^\text{in}_j.}{S}$$

此模型通常用于创建具有固定预期度序列的随机图。顶点 \(i\) 的预期度大约等于权重 \(w_i\)。具体来说，如果图是有向的且允许自环，则预期的出度和入度精确地为 \(w^\text{out}\) 和 \(w^\text{in}\)。如果禁用自环，则预期的出度和入度分别为 \(\frac{w^\text{out} (S - w^\text{in})}{S}\) 和 \(\frac{w^\text{in} (S - w^\text{out})}{S}\)。如果图是无向的，则有自环和没有自环的预期度分别为 \(\frac{w (S + w)}{S}\) 和 \(\frac{w (S - w)}{S}\)。

原始 Chung-Lu 模型的一个限制是，当某些权重很大时，\(p_{ij}\) 的公式会产生大于 1 的值。Chung 和 Lu 的原始论文排除了使用此类权重。当 \(p_{ij} > 1\) 时，此函数仅发出警告并在 \(i\) 和 \(j\) 之间创建连接。但是，在这种情况下，预期度将不再以上述方式与权重相关。因此，原始 Chung-Lu 模型无法产生某些（大的）预期度。

为了克服此限制，此函数实现了模型的其他变体，并修改了顶点 \(i\) 和 \(j\) 之间的连接概率 \(p_{ij}\) 的表达式。设 \(q_{ij} = \frac{w_i w_j}{S}\)，或有向情况下的 \(q_{ij} = \frac{w^\text{out}_i w^\text{in}_j}{S}\)。在 \(q_{ij}\) 接近零的稀疏图的限制下，所有模型变体都变得等效。在原始 Chung-Lu 模型中，可以通过将 variant 设置为“original”来选择，\(p_{ij} = \min(q_{ij}, 1)\)。“maxent”变体，有时被称为广义随机图，使用 \(p_{ij} = \frac{q_{ij}}{1 + q_{ij}}\)，并且等效于具有预期度约束的最大熵模型（即，指数随机图模型）；参见 Park 和 Newman (2004)，第 B 节，设置 \(\exp(-\Theta_{ij}) = \frac{w_i w_j}{S}\)。Britton、Deijfen 和 Martin-Löf (2006) 也讨论了此模型。通过作为度约束最大熵模型，它以相同的概率生成具有相同度序列的图。可以使用“nr”请求第三个变体，它使用 \(p_{ij} = 1 - \exp(-q_{ij})\)。这是 Norros 和 Reittu (2006) 引入的多重图模型的底层简单图。有关这三个模型变体的讨论，请参见 Bollobás、Janson、Riordan (2007) 的第 16.4 节，以及 Van Der Hofstad (2013)。

参考文献

Chung, F., and Lu, L. (2002). Connected components in a random graph with given degree sequences. Annals of Combinatorics, 6, 125-145. doi:10.1007/PL00012580

Miller, J. C., and Hagberg, A. (2011). Efficient Generation of Networks with Given Expected Degrees. doi:10.1007/978-3-642-21286-4_10

Park, J., and Newman, M. E. J. (2004). Statistical mechanics of networks. Physical Review E, 70, 066117. doi:10.1103/PhysRevE.70.066117

Britton, T., Deijfen, M., and Martin-Löf, A. (2006). Generating Simple Random Graphs with Prescribed Degree Distribution. Journal of Statistical Physics, 124, 1377-1397. doi:10.1007/s10955-006-9168-x

Norros, I., and Reittu, H. (2006). On a conditionally Poissonian graph process. Advances in Applied Probability, 38, 59-75. doi:10.1239/aap/1143936140

Bollobás, B., Janson, S., and Riordan, O. (2007). The phase transition in inhomogeneous random graphs. Random Structures & Algorithms, 31, 3-122. doi:10.1002/rsa.20168

Van Der Hofstad, R. (2013). Critical behavior in inhomogeneous random graphs. Random Structures & Algorithms, 42, 480-508. doi:10.1002/rsa.20450

参见

sample_fitness() 实现了具有对边数严格约束的类似模型。sample_degseq() 采样具有明确指定度的随机图。sample_gnp() 创建在所有顶点对之间具有固定连接概率 \(p\) 的随机图。

随机图模型（游戏） bipartite_gnm()、erdos.renyi.game()、sample_()、sample_bipartite()、sample_correlated_gnp()、sample_correlated_gnp_pair()、sample_degseq()、sample_dot_product()、sample_fitness()、sample_fitness_pl()、sample_forestfire()、sample_gnm()、sample_gnp()、sample_grg()、sample_growing()、sample_hierarchical_sbm()、sample_islands()、sample_k_regular()、sample_last_cit()、sample_pa()、sample_pa_age()、sample_pref()、sample_sbm()、sample_smallworld()、sample_traits_callaway()、sample_tree()

chung_lu_game().

示例


g <- sample_chung_lu(c(3, 3, 2, 2, 2, 1, 1))

rowMeans(replicate(
  100,
  degree(sample_chung_lu(c(1, 3, 2, 1), c(2, 1, 2, 2)), mode = "out")
))
#> [1] 0.88 3.04 1.96 1.03

rowMeans(replicate(
  100,
  degree(sample_chung_lu(c(1, 3, 2, 1), c(2, 1, 2, 2), variant = "maxent"), mode = "out")
))
#> [1] 0.77 1.71 1.37 0.66