8

给定一个无向 NetworkX Graph graph，我想检查它是否是无标度的。

为此，据我了解，我需要找到k每个节点的度数，以及该度数P(k)在整个网络中的频率。由于度数的频率与度数本身之间的关系，这应该表示幂律曲线。

绘制我对 P(k) 和 k 的计算会按预期显示功率曲线，但是当我对其进行双重记录时，不会绘制直线。

以下图是使用 1000 个节点获得的。

P(k) - k 图

P(k) - k 的双对数图

代码如下：

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

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

来自 10000 个节点的 P(k) 图 来自 10000 个节点的双对数 P(k) 图

4

3 回答 3

4

您是否在 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)

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

lognornal vs powerlaw vs 拉伸指数

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

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

于 2020-08-17T03:02:41.733 回答
1

您的部分问题是您在拟合线时没有包括缺失的度数。有少量大度节点，您将其包括在您的行中，但您忽略了许多大度不存在的事实。您的最大度数在 1000-2000 范围内，但只有 2 个观测值。所以真的，对于如此大的值，我期望随机节点具有如此大的度数 2/(1000*N) 的概率（或者实际上，它可能甚至更小）。但是根据您的情况，您将它们视为这两个特定度数的概率是 2/N，而您忽略了其他度数。

简单的解决方法是仅使用适合您的较小度数。

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

于 2018-04-19T05:31:06.730 回答
0

试图将一条线拟合到这些点是错误的，因为这些点不是线性分布在 x 轴上的。线的拟合函数将更加重视包含更多点的域部分。

您应该使用 function 在 x 轴上重新分配观察结果np.interp，如下所示。

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, "-")
于 2019-11-06T10:02:22.733 回答