expected_degree_graph

expected_degree_graph(w, seed=None, selfloops=True)

返回具有给定期望度的随机图。

给定一个长度为 \(n\) 的期望度序列 \(W=(w_0,w_1,\ldots,w_{n-1})\)，此算法以如下概率在节点 \(u\) 和节点 \(v\) 之间分配一条边

\[p_{uv} = \frac{w_u w_v}{\sum_k w_k} .\]

参数：

w列表

期望度列表。

selfloops: 布尔值 (默认为 True)

设置为 False 可移除自环边的可能性。

seed整数, 随机状态, 或 None (默认)

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

返回值：

图

备注

节点具有与期望度输入序列索引相对应的整数标签。

此算法的复杂度为 \( \mathcal{O}(n+m) \)，其中 \( n \) 是节点数，\( m \) 是期望的边数。

[1] 中的模型包含自环边的可能性。设置 selfloops=False 可生成不含自环的图。

对于有限图，此模型无法精确生成给定的期望度序列。相反，期望度如下所示。

对于没有自环的情况 (selfloops=False)，

\[E[deg(u)] = \sum_{v \ne u} p_{uv} = w_u \left( 1 - \frac{w_u}{\sum_k w_k} \right) .\]

NetworkX 使用标准约定，自环边在节点的度中计为 2，因此存在自环时 (selfloops=True)，

\[E[deg(u)] = \sum_{v \ne u} p_{uv} + 2 p_{uu} = w_u \left( 1 + \frac{w_u}{\sum_k w_k} \right) .\]

参考文献

[1]

Fan Chung and L. Lu, Connected components in random graphs with given expected degree sequences, Ann. Combinatorics, 6, pp. 125-145, 2002.

[2]

Joel Miller and Aric Hagberg, Efficient generation of networks with given expected degrees, in Algorithms and Models for the Web-Graph (WAW 2011), Alan Frieze, Paul Horn, and Paweł Prałat (Eds), LNCS 6732, pp. 115-126, 2011.

示例

>>> z = [10 for i in range(100)]
>>> G = nx.expected_degree_graph(z)