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*将有:math:`mu mathrm{deg}(u)`条边连接到其社区之外的节点，以及:math:`(1 - mu) mathrm{deg}(u)`条边连接到其社区内的节点。

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

  3. 每个节点将被随机分配到一个社区，条件是该社区足够大以容纳节点的社区内度数，如步骤2所述。如果一个社区变得太大，将随机选择一个节点重新分配到新社区，直到所有节点都被分配到一个社区。

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

Parameters:
nint

创建的图中节点的数量。

tau1float

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

tau2float

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

mufloat

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

average_degreefloat

创建的图中节点的期望平均度。该值必须在区间[0, n]内。必须指定其中一个，否则会引发:exc:NetworkXError 。

min_degreeint

创建的图中节点的最小度。该值必须在区间[0, n]内。必须指定其中一个，否则会引发:exc:NetworkXError 。

max_degreeint

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

min_communityint

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

max_communityint

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

tolfloat

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

max_itersint

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

seedinteger, random_state, 或 None (默认)

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

Returns:
GNetworkX图

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

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

Raises:
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 次迭代内无法创建有效的社区分配。

Notes

该算法与[1]中原始呈现的方式略有不同。

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

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

尽管作者描述该算法相当健壮，但在开发过程中的测试表明，可能需要更窄的参数集才能成功生成图。如果出现异常，提供了一些建议。

References

[1]

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

Examples

基本用法:

>>> 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}
On this page