LFR_benchmark_graph#

LFR_benchmark_graph(n, tau1, tau2, mu, average_degree=None, min_degree=None, max_degree=None, min_community=None, max_community=None, tol=1e-07, max_iters=500, seed=None)[source]#

返回 LFR 基准图。

此算法按如下步骤进行：

  1. 找到一个遵循幂律分布、最小度为 min_degree 且近似平均度为 average_degree 的度序列。这可以通过以下方式实现：

    1. 指定 min_degree 而不指定 average_degree，

    2. 指定 average_degree 而不指定 min_degree，在这种情况下，将找到合适的最小度。

    也可以指定 max_degree，否则它将被设置为 n。每个节点 u 将有 \(\mu \mathrm{deg}(u)\) 条边连接到其自身社区之外的节点，以及 \((1 - \mu) \mathrm{deg}(u)\) 条边连接到其自身社区内的节点。

  2. 根据指数为 tau2 的幂律分布生成社区大小。如果未指定 min_community 和 max_community，它们将分别被设置为 min_degree 和 max_degree。社区大小将一直生成，直到其总和等于 n。

  3. 每个节点将被随机分配到一个社区，条件是该社区足够大以容纳该节点的社区内度，即步骤 2 中描述的 \((1 - \mu) \mathrm{deg}(u)\)。如果一个社区变得太大，将随机选择一个节点重新分配到新的社区，直到所有节点都被分配了社区。

  4. 然后，每个节点 u 添加 \((1 - \mu) \mathrm{deg}(u)\) 条社区内边和 \(\mu \mathrm{deg}(u)\) 条社区间边。

参数：
nint

创建的图中的节点数。

tau1float

创建的图的度分布的幂律指数。该值必须严格大于 1。

tau2float

创建的图中的社区大小分布的幂律指数。该值必须严格大于 1。

mufloat

每个节点的社区间边的比例。该值必须在区间 [0, 1] 内。

average_degreefloat

创建的图中节点的期望平均度。该值必须在区间 [0, n] 内。必须且只能指定 average_degree 和 min_degree 中的一个，否则将引发 NetworkXError。

min_degreeint

创建的图中节点的最小度。该值必须在区间 [0, n] 内。必须且只能指定 min_degree 和 average_degree 中的一个，否则将引发 NetworkXError。

max_degreeint

创建的图中节点的最大度。如果未指定，则设置为 n，即图中的节点总数。

min_communityint

图中的社区最小大小。如果未指定，则设置为 min_degree。

max_communityint

图中的社区最大大小。如果未指定，则设置为 n，即图中的节点总数。

tolfloat

比较浮点数时的容差，特别是在比较平均度值时。

max_itersint

尝试创建社区大小、度分布和社区归属的最大迭代次数。

seedinteger, random_state, 或 None (默认)

随机数生成状态的指示器。参见 随机性。

返回值：
GNetworkX graph

根据指定参数生成的 LFR 基准图。

图中的每个节点都有一个节点属性 'community'，用于存储包含该节点的社区（即节点集合）。

引发：
NetworkXError

如果任何参数不符合其上限和下限

  • tau1 和 tau2 必须严格大于 1。

  • mu 必须在 [0, 1] 内。

  • max_degree 必须在 {1, …, n} 内。

  • min_community 和 max_community 必须在 {0, …, n} 内。

如果未精确指定 average_degree 和 min_degree 中的一个。

如果未指定 min_degree 且找不到合适的 min_degree。

ExceededMaxIterations

如果在 max_iters 次迭代内无法创建有效的度序列。

如果在 max_iters 次迭代内无法创建有效的社区大小集合。

如果在 10 * n * max_iters 次迭代内无法创建有效的社区分配。

说明

此算法与 [1] 中最初提出的方法略有不同。

  1. 我们不是通过配置模型连接图，然后重新布线以匹配社区内度和社区间度，而是在最后明确执行此布线，这应该是等效的。

  2. 作者网站 [2] 上发布的代码使用连续近似计算随机幂律分布变量及其平均值，而我们在此使用离散分布，因为度和社区大小都是离散的。

尽管作者称该算法相当鲁棒，但开发期间的测试表明，参数设置范围略窄一些更有可能成功生成图。在发生异常时提供了一些建议。

参考文献

[1]

“Benchmark graphs for testing community detection algorithms”, Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi, Phys. Rev. E 78, 046110 2008

示例

基本用法

>>> from networkx.generators.community import LFR_benchmark_graph
>>> n = 250
>>> tau1 = 3
>>> tau2 = 1.5
>>> mu = 0.1
>>> G = LFR_benchmark_graph(
...     n, tau1, tau2, mu, average_degree=5, min_community=20, seed=10
... )

继续上面的示例，您可以从图的节点属性中获取社区信息

>>> communities = {frozenset(G.nodes[v]["community"]) for v in G}
本页内容