生成具有幂律度分布的无标度网络 [英] Generate a scale-free network with a power-law degree distributions

问题描述

我正在尝试生成具有以下条件的几个无标度网络：

• 度分布服从相同指数的幂律
• 完全相同的节点数。

我需要构建至少60对这样的对，并为每个对运行模拟。

为此，我需要一种方法来生成正好由n个节点组成的具有上述属性的网络。

现在，我可以使用NetworkX Python库，用下面的代码生成遵循给定指数的幂律的度分布图

import networkx as nx
import matplotlib.pyplot as plt

#create a graph with degrees following a power law distribution
s = nx.utils.powerlaw_sequence(100, 2.5) #100 nodes, power-law exponent 2.5
G = nx.expected_degree_graph(s, selfloops=False)

print(G.nodes())
print(G.edges())

#draw and show graph
pos = nx.spring_layout(G)
nx.draw_networkx(G, pos)
plt.show()

但是，这会生成具有许多隔离节点的图形，并且通常不止一个连接的组件。

我可以丢弃隔离的节点，但是这样我的最终网络就会比我预期的少，而且它可能不是一个单一的网络。它可以是2个或更多独立的连接组件。

推荐答案

第一个问题-您不想要隔离节点或多个连接组件有什么原因吗？原则上，一个真正的"随机"幂律图会有这些。

以下是几点评论：

1)如果您使用EXPENDED_DEGREE_GRAPH图，您将很难删除孤立的节点。这是因为有许多节点的预期度约为1(但实际度数来自泊松分布)。这意味着他们的学位很有可能低于1。要显示这一点，请打印s。

2)另一种选择是改为使用配置模型图来创建网络。为此，我们从幂律序列中取数字并取整数部分。去掉那些为0的。然后使用nx.configuration_model创建图形。然后可以删除自环和重复边。但是，您应该小心-高度节点可能有许多自环或重复边。所以你需要小心，不要把强势法则的尾巴砍得太快。这不会解决拥有多个组件的问题。您通常会有一个非常大的组件和几个非常小的独立组件。除非你有很好的理由扔掉这些东西，否则扔掉这样的箱子会使你的样本产生偏差。

import networkx as nx
import matplotlib.pyplot as plt

#create a graph with degrees following a power law distribution

#I believe we can eliminate this loop to find s by using the call   
#nx.utils.create_degree_sequence(100,powerlaw_sequence) with 
#appropriate modification
while True:  
    s=[]
    while len(s)<100:
        nextval = int(nx.utils.powerlaw_sequence(1, 2.5)[0]) #100 nodes, power-law exponent 2.5
        if nextval!=0:
            s.append(nextval)
    if sum(s)%2 == 0:
        break
G = nx.configuration_model(s)
G=nx.Graph(G) # remove parallel edges
G.remove_edges_from(G.selfloop_edges())

#draw and show graph
pos = nx.spring_layout(G)
nx.draw_networkx(G, pos)
plt.savefig('test.pdf')

PS：我提出了networkx中Expect_Degree_Graphs实现的算法(不是模型，而是实现它的算法)。如果你有空闲时间，就把它读一遍。很凉爽。

这篇关于生成具有幂律度分布的无标度网络的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！