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} .\]

Parameters:

wlist

期望度的列表。

selfloops: bool (默认=True)

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

seedinteger, random_state, 或 None (默认)

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

Returns:

Graph

Notes

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

该算法的复杂度为 \(\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) .\]

References

[1]

Fan Chung 和 L. Lu，具有给定期望度序列的随机图中的连通分量，Ann. Combinatorics, 6, pp. 125-145, 2002.

[2]

Joel Miller 和 Aric Hagberg， 高效生成具有给定期望度的网络， 在 Algorithms and Models for the Web-Graph (WAW 2011) 中， Alan Frieze, Paul Horn, 和 Paweł Prałat (Eds), LNCS 6732, pp. 115-126, 2011.

Examples

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