python - 如何检查网络是否无标度？

Question

给定一个无向 NetworkX Graph 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 方法获得的，然后将其用作图形构造函数的输入。

更新

根据@Joel 的要求，下面是 10000 个节点的图。
此外，生成图表的具体代码如下:
graph = networkx.Graph(networkx.scale_free_graph(num_of_nodes))

正如我们所见，大量的值似乎确实形成了一条直线，但网络在其双对数形式中似乎有一条奇怪的尾部。

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) 

考虑到幂律会自动找到 xmin 的最佳 alpha 值，方法是从数据集中的每个唯一值开始创建幂律拟合，然后选择导致数据之间的最小 Kolmogorov-Smirnov 距离 D 的那个和合身。如果要包含所有数据，可以按如下方式定义 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 fit

另一方面，它可能不是幂律分布，而是任何其他分布，如对数线性等，您还可以检查 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

lognornal vs powerlaw vs stretched exponential

最后，考虑到现在正在讨论网络中的幂律分布，强无标度网络在经验上似乎很少见

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