跳到内容

从给定的度序列确定性地创建图

来源: R/make.R
realize_degseq.Rd

通常需要创建具有给定顶点度的图。此函数以确定性的方式创建这样的图。

用法

realize_degseq(
  out.deg,
  in.deg = NULL,
  allowed.edge.types = c("simple", "loops", "multi", "all"),
  method = c("smallest", "largest", "index")
)

参数

out.deg

数值向量，度的序列（对于无向图）或出度（对于有向图）。 对于无向图，其总和应为偶数。 对于有向图，其总和应与in.deg的总和相同。

in.deg

对于有向图，入度序列。 默认值为NULL，并创建一个无向图。

allowed.edge.types

字符，指定允许的边的类型。 “simple”仅允许简单图（无环，无多重边）。 “multiple”允许多重边，但不允许环。 “loops”允许环边，但不允许多重边（目前未实现）。 “all”允许所有类型的边。 默认值为“simple”。

method

字符，用于生成图的方法； 见下文。

值

新的图对象。

详细信息

使用 Havel-Hakimi 算法（无向情况）或类似的 Kleitman-Wang 算法（有向情况）构造简单无向图。 这些算法的工作方式是选择一个任意顶点，并将其所有桩连接到其他顶点。 重复此步骤，直到所有度都已连接起来。

“method”参数控制在算法过程中选择顶点的顺序。

“smallest”方法选择剩余度最小的顶点。 结果通常是具有高负度组合性的图。 在无向情况下，无论是否允许多重边，只要存在连接的实现，此方法都保证生成连接的图。 有关详细信息，请参见 Horvát 和 Modes (2021)。 在有向情况下，它倾向于生成弱连接的图，但这不能保证。 这是默认方法。

“largest”方法选择剩余度最大的顶点。 结果通常是具有高正度组合性的图，并且通常是断开连接的。

“index”方法按索引顺序选择顶点。

参考文献

V. Havel, Poznámka o existenci konečných grafů (关于有限图的存在的评论), Časopis pro pěstování matematiky 80, 477-480 (1955). https://eudml.org/doc/19050

S. L. Hakimi, 关于整数集合作为线性图的顶点的度的可实现性, Journal of the SIAM 10, 3 (1962). doi:10.1137/0111010

D. J. Kleitman 和 D. L. Wang, 用于构造具有给定化合价和因子的图和有向图的算法, Discrete Mathematics 6, 1 (1973). doi:10.1016/0012-365X(73)90037-X

Sz. Horvát 和 C. D. Modes, 连接很重要：连接网络的构造和精确随机抽样 (2021). doi:10.1088/2632-072X/abced5

参见

sample_degseq() 用于从具有给定度序列的图中进行采样的随机变体。

realize_degree_sequence().

示例


g <- realize_degseq(rep(2, 100))
degree(g)
#>   [1] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
#>  [38] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
#>  [75] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
is_simple(g)
#> [1] TRUE

## Exponential degree distribution, with high positive assortativity.
## Loop and multiple edges are explicitly allowed.
## Note that we correct the degree sequence if its sum is odd.
degs <- sample(1:100, 100, replace = TRUE, prob = exp(-0.5 * (1:100)))
if (sum(degs) %% 2 != 0) {
  degs[1] <- degs[1] + 1
}
g4 <- realize_degseq(degs, method = "largest", allowed.edge.types = "all")
all(degree(g4) == degs)
#> [1] TRUE

## Power-law degree distribution, no loops allowed but multiple edges
## are okay.
## Note that we correct the degree sequence if its sum is odd.
degs <- sample(1:100, 100, replace = TRUE, prob = (1:100)^-2)
if (sum(degs) %% 2 != 0) {
  degs[1] <- degs[1] + 1
}
g5 <- realize_degseq(degs, allowed.edge.types = "multi")
all(degree(g5) == degs)
#> [1] TRUE