如何检查一个网络是否为无标度网络？

Question

给定一个无向的NetworkX图graph，我想要检查它是否是无标度的。为了做到这一点，我需要找到每个节点的度k以及整个网络中该度数P(k)的频率。由于度数和频率之间的关系，这应该表示一个幂律曲线。我的计算结果显示P(k)和k的图像呈现出预期的幂律曲线，但是当我对其进行双对数处理时，没有绘制出一条直线。以下图像是使用1000个节点获得的。

代码如下：

k = []
Pk = []

for node in list(graph.nodes()):
    degree = graph.degree(nbunch=node)
    try:
        pos = k.index(degree)
    except ValueError as e:
        k.append(degree)
        Pk.append(1)
    else:
        Pk[pos] += 1

# get a double log representation
for i in range(len(k)):
    logk.append(math.log10(k[i]))
    logPk.append(math.log10(Pk[i]))

order = np.argsort(logk)
logk_array = np.array(logk)[order]
logPk_array = np.array(logPk)[order]
plt.plot(logk_array, logPk_array, ".")
m, c = np.polyfit(logk_array, logPk_array, 1)
plt.plot(logk_array, m*logk_array + c, "-")

{{m}}代表缩放系数，如果其在2到3之间，则该网络应该是无标度的。

通过调用NetworkX的scale_free_graph方法获取图形，然后将其用作Graph构造函数的输入来获得这些图形。

更新 根据@Joel的请求，以下是10000个节点的绘图。此外，生成图形的确切代码如下： graph = networkx.Graph(networkx.scale_free_graph(num_of_nodes))

可见，很多值似乎形成一条直线，但是该网络在对数-对数形式中有一个奇怪的尾巴。

- Mox

---

尝试使用更大的网络，我认为那样会更明显。另外，你能提供用于创建图形的代码吗？ - Joel

@Joel 如问题底部所解释的那样，该图是通过以下方式获得的：graph = networkx.Graph(networkx.scale_free_graph(num_of_nodes)) - Mox

我遇到的确切问题是日志值不符合我的预期。 - Mox

@Joel，按照您的要求完成了。一条直线似乎确实形成了，但随着k值的增加，它变得更加模糊，这污染了我的图表，因此也影响了缩放系数的计算。 - Mox

尝试将它变得更大... - Joel

Answer 1

你尝试过在Python中使用powerlaw模块吗？它非常简单。

首先，从你的网络中创建一个度分布变量：

degree_sequence = sorted([d for n, d in G.degree()], reverse=True) # used for degree distribution and powerlaw test

然后将数据拟合到幂律和其他分布中：

import powerlaw # Power laws are probability distributions with the form:p(x)∝x−α
fit = powerlaw.Fit(degree_sequence) 

请注意，powerlaw会自动查找数据集中每个唯一值的起始点并创建一个幂律拟合，以此选择导致数据与拟合之间Kolmogorov-Smirnov距离D最小的alpha值作为xmin的最优值。 如果您想包含所有数据，可以将xmin值定义如下：

fit = powerlaw.Fit(degree_sequence, xmin=1)

然后您可以绘制图形：

fig2 = fit.plot_pdf(color='b', linewidth=2)
fit.power_law.plot_pdf(color='g', linestyle='--', ax=fig2)

这将产生如下输出： 幂律分布拟合 另一方面，它可能不是幂律分布，而是任何其他分布，如对数线性等，您还可以检查powerlaw.distribution_compare:

R, p = fit.distribution_compare('power_law', 'exponential', normalized_ratio=True)
print (R, p)

其中 R 是两个候选分布之间的可能性比率。如果数据更可能出现在第一个分布中，则该数字将为正，但您还应检查 p < 0.05。

最后，一旦您为分布选择了 xmin，您可以绘制社交网络的一些常见度分布进行比较：

plt.figure(figsize=(10, 6))
fit.distribution_compare('power_law', 'lognormal')
fig4 = fit.plot_ccdf(linewidth=3, color='black')
fit.power_law.plot_ccdf(ax=fig4, color='r', linestyle='--') #powerlaw
fit.lognormal.plot_ccdf(ax=fig4, color='g', linestyle='--') #lognormal
fit.stretched_exponential.plot_ccdf(ax=fig4, color='b', linestyle='--') #stretched_exponential

对数正态分布 vs 幂律分布 vs 拉伸指数分布

最后，需要注意的是，在网络中的幂律分布目前正在讨论中，强度为无标度的网络在实际中很少见。

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6399239/

- Leonardo Rocco

Answer 2

你的问题之一是在拟合线时没有包含缺失的度数。有一些大度节点，你将它们包含在你的线中，但你忽略了许多大度不存在的事实。你的最大度数在1000-2000范围内，但只有两个观察结果。因此，对于这么大的值，我期望一个随机节点具有如此大的度数的概率为2/(1000*N)（或者实际上可能更小）。但在你的拟合中，你把它们当作是这两个特定度数的概率是2/N，并忽略了其他度数。

简单的解决方法是只使用较小的度数进行拟合。

更稳健的方法是拟合互补的累积分布。不要绘制P(K=k)，而是绘制P(K>=k)，并尝试拟合它（注意，如果P(K=k)的概率是幂律，则P(K>=k)的概率也是，但指数不同-请检查）。

- Joel

Answer 3

尝试将这些点拟合成一条直线是错误的，因为这些点在 x 轴上不是线性分布的。直线的拟合函数会更加关注包含更多点的区域。

您应该使用函数 np.interp 重新分配观测值在 x 轴上的位置，就像这样。

logk_interp = np.linspace(np.min(logk_array),np.max(logk_array),1000)
logPk_interp = np.interp(logk_interp, logk_array, logPk_array)
plt.plot(logk_array, logPk_array,".")

m, c = np.polyfit(logk_interp, logPk_interp, 1)
plt.plot(logk_interp, m*logk_interp + c, "-")

- Tonca