使用优先连接生成随机图 - sample_pa • igraph 网络分析库

优先连接是一系列用于构建图的简单随机算法。变体包括 Barabási-Abert 模型和 Price 模型。

用法

sample_pa(
  n,
  power = 1,
  m = NULL,
  out.dist = NULL,
  out.seq = NULL,
  out.pref = FALSE,
  zero.appeal = 1,
  directed = TRUE,
  algorithm = c("psumtree", "psumtree-multiple", "bag"),
  start.graph = NULL
)

pa(...)

参数

n: 顶点数。
power: 优先连接的幂，默认值为 1，即线性优先连接。
m: 数值常数，每个时间步添加的边数。仅当同时省略或 NULL out.dist 和 out.seq 时才使用此参数。
out.dist: 数值向量，每个时间步添加的边数的分布。仅当省略或 NULL out.seq 参数时才使用此参数。
out.seq: 数值向量，给出每个时间步添加的边数。它的第一个元素被忽略，因为第一个时间步不添加边。
out.pref: 逻辑值，如果为 true，则总度数用于计算引用概率，否则使用入度。
zero.appeal: 没有相邻边的顶点的“吸引力”。请参阅下面的详细信息。
directed: 是否创建有向图。
algorithm: 用于生成图的算法。 psumtree 使用部分前缀和树来生成图，此算法可以处理任何 power 和 zero.appeal 值，并且永远不会生成多重边。 psumtree-multiple 也使用部分前缀和树，但允许生成多重边。在 0.6 版本之前，如果 power 不为 1 或 zero.appeal 不为 1，则 igraph 使用此算法。 bag 是先前（0.6 版本之前）在 power 为 1 且 zero.appeal 也为 1 时使用的算法。它通过将顶点的 ID 放入一个包（实际上是多重集）中来工作，次数与它们的（入）度数相同，再加上一次。然后，从包中抽取所需数量的被引用顶点，并进行替换。此方法可能会生成多重边。它仅在 power 和 zero.appeal 等于 1 时才有效。
start.graph: NULL 或 igraph 图。如果是图，则提供的图用作优先连接算法的起始图。该图应至少有一个顶点。如果在此处提供了一个图，并且 out.seq 参数不是 NULL，则它应仅包含新顶点的出度，而不包含 start.graph 中的顶点的出度。
...: 传递给 sample_pa()。

值

一个图对象。

详细信息

这是一个生成图的简单随机算法。它是一个离散时间步模型，并且在每个时间步添加一个顶点。

我们在第一个时间步从单个顶点和没有边开始。然后我们在每个时间步添加一个顶点，并且新顶点发起一些边到旧顶点。旧顶点被选择的概率由 $$P[i] \sim k_i^\alpha+a$$ 给出，其中 $k_i$ 是当前时间步中顶点 $i$ 的入度（更准确地说是顶点 $i$ 的未由 $i$ 自身发起的相邻边数），$\alpha$ 和 $a$ 是由 power 和 zero.appeal 参数给出的参数。

在时间步中发起的边数由 m、out.dist 和 out.seq 参数给出。如果给出了 out.seq 并且不为 NULL，则它在向量中给出要添加的边数，第一个元素被忽略，第二个是在第二个时间步中要添加的边数，依此类推。如果未给出 out.seq 或为 null，并且给出了 out.dist 并且不为 NULL，则它用作离散分布以生成每个时间步中的边数。它的第一个元素是没有添加边的概率，第二个是添加一条边的概率，等等。（out.dist 不需要加起来为 1，它会自动标准化。） out.dist 应包含非负数，并且至少一个元素应为正数。

如果省略或 NULL out.seq 和 out.dist，则将使用 m，它应该是一个正整数常数，并且在每个时间步添加 m 条边。

默认情况下，sample_pa() 生成一个有向图，将 directed 设置为 FALSE 以生成无向图。请注意，即使生成无向图，$k_i$ 也表示不由顶点自身发起的相邻边数，而不是顶点的总（入 + 出）度数，除非 out.pref 参数设置为 TRUE。

参考文献

Barabási, A.-L. and Albert R. 1999. Emergence of scaling in random networks Science, 286 509–512.

de Solla Price, D. J. 1965. Networks of Scientific Papers Science, 149 510–515.

参见

随机图模型（游戏） bipartite_gnm(), erdos.renyi.game(), sample_(), sample_bipartite(), sample_chung_lu(), 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_age(), sample_pref(), sample_sbm(), sample_smallworld(), sample_traits_callaway(), sample_tree()

作者

Gabor Csardi csardi.gabor@gmail.com

示例


g <- sample_pa(10000)
degree_distribution(g)
#>   [1] 0.0000 0.6622 0.1695 0.0672 0.0322 0.0203 0.0119 0.0086 0.0061 0.0051
#>  [11] 0.0026 0.0025 0.0018 0.0008 0.0013 0.0008 0.0010 0.0006 0.0003 0.0002
#>  [21] 0.0005 0.0006 0.0004 0.0001 0.0002 0.0001 0.0002 0.0001 0.0001 0.0002
#>  [31] 0.0001 0.0001 0.0001 0.0001 0.0001 0.0000 0.0001 0.0000 0.0000 0.0000
#>  [41] 0.0001 0.0000 0.0001 0.0002 0.0000 0.0000 0.0000 0.0000 0.0002 0.0001
#>  [51] 0.0000 0.0002 0.0000 0.0000 0.0001 0.0000 0.0001 0.0000 0.0000 0.0000
#>  [61] 0.0001 0.0000 0.0000 0.0001 0.0000 0.0000 0.0001 0.0000 0.0000 0.0000
#>  [71] 0.0001 0.0000 0.0001 0.0000 0.0000 0.0000 0.0001 0.0000 0.0000 0.0000
#>  [81] 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
#>  [91] 0.0001 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
#> [101] 0.0001