graphscope.nx.generators.community.LFR_benchmark_graph

graphscope.nx.generators.community.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)[源代码]

返回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. 每个节点将被随机分配到一个社区，条件是社区足够大以满足节点的社区内度数(1 - mu) mathrm{deg}(u)（如步骤2所述）。如果某个社区变得过大，将随机选择一个节点重新分配到新社区，直到所有节点都被分配到一个社区。

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

Parameters:

  • n (int) – 创建的图中的节点数量。

  • tau1 (float) – 所创建图的度分布幂律指数。该值必须严格大于1。

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

  • mu (float) – 每个节点关联的跨社区边所占比例。该值必须在区间[0, 1]内。

  • average_degree (float) – 创建图中节点的期望平均度数。该值必须位于区间[0, n]内。此参数与min_degree必须且只能指定其中一个，否则会引发NetworkXError错误。

  • min_degree (int) – 创建图中节点的最小度数。该值必须在区间[0, n]内。必须且只能指定此参数或average_degree中的一个，否则会引发NetworkXError错误。

  • max_degree (int) – 创建图中节点的最大度数。如果未指定，则默认为n，即图中的节点总数。

  • min_community (int) – 图中社区的最小规模。如果未指定，将默认设置为min_degree。

  • max_community (int) – 图中社区的最大规模。如果未指定，则默认设置为n，即图中的节点总数。

  • tol (float) – 浮点数比较时的容差，特指在比较平均度值时的容差。

  • max_iters (int) – 尝试创建社区规模、度分布和社区归属的最大迭代次数。

  • seed (integer, random_state, or None (default)) - 随机数生成状态的指示器。 参见随机性。

Returns:

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

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

Return type:

NetworkX 图

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

示例

基本用法：

>>> 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}

备注

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

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

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

尽管作者将该算法描述为相当稳健，但开发期间的测试表明，参数范围稍窄一些更有可能成功生成图。若出现异常情况，文中也提供了一些建议。

参考文献