生成具有幂律度分布的无标度网络。

Question

我正在努力建立一对无规模的网络，包括：

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

我需要建立至少60对这样的夫妇，并为每个人运行一个模拟。

为了做到这一点，我需要一种方法来生成具有上述属性的完全n个节点的网络。

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

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

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

我可以丢弃孤立的节点，但是我的最后一个网络的节点将比我预期的少，而且它可能不是单个网络。它可以是两个或更多独立的连接组件。

Answer 1

首先是一个问题--你不想要孤立的节点或多个连接的组件有什么原因吗？原则上，一个真正的“随机”幂律图会有这些。

所以有几点评论：

1)如果使用expected_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中的expected_degree_graph实现提出了算法(不是模型，而是实现它的算法)。如果你有空的话，把它读一遍。这很酷。

Answer 2

当我遇到与您类似的问题时，我走了一条路，简单地使用了BA生成器，为新的节点添加了不同数量的链接，例如，1，.，5，这保证了一个连接的组件，没有平行的边。

由于您需要固定幂律指数，我建议如下:通常，在级联故障中，研究两种不同类型的拓扑。如果是这样的话，请从最大的连接组件(LCC)生成一个“无标度”网络，如我的ipython笔记本所示。

import networkx as nx
from networkx.utils import (powerlaw_sequence, create_degree_sequence)
sequence = create_degree_sequence(num, powerlaw_sequence, exponent=exp)
graph = nx.configuration_model(sequence, seed=seed)
loops = graph.selfloop_edges()
# remove parallel edges and self-loops
graph = nx.Graph(graph)
graph.remove_edges_from(loops)
# get largest connected component
# unfortunately, the iterator over the components is not guaranteed to be sorted by size
components = sorted(nx.connected_components(graph), key=len, reverse=True)
lcc = graph.subgraph(components[0])

并将生成ER图的节点数作为连通拓扑，因为LCC中的节点数比一定的边缘概率要可靠得多。

正如您在链接度分布中所看到的，LCC的拓扑结构仍然是我所认为的“无标度”。当您考虑几千个节点的网络时，只要您的两个连接网络的数目相同，您的60个网络就不应该有完全相同的节点数。

如果你想连接两个“无标度”的网络，除了从两个LCC中删除随机节点之外，我看不出如何做到这一点，直到你到达相同的数字。

让我们知道你是怎么解决的。