生成一个具有幂律度数分布的无标度网络

Question

生成一个具有幂律度数分布的无标度网络

pythongraphgraph-algorithmnetworkx

6

我正在尝试生成一些规模自由网络，满足以下条件：

度分布遵循相同指数的幂律分布
包含完全相同数量的节点

我需要至少生成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()

然而，这会生成许多孤立节点的图形，通常不止一个连通分量。

我可以舍弃孤立节点，但最终网络将比我预期的节点数少，并且可能不是单个网络。它可能是两个或更多独立的联通分量。

- Agostino

2个回答

1

当我遇到类似于你的问题时，我采用了简单的方法，使用BA生成器添加新节点并变化链接数量，例如1、2、3、4、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中删除随机节点直到达到相同数量之外还有什么其他方法。让我们知道你是如何解决它的。

- Midnighter

感谢您的发布。我的IDE警告我create_degree_sequence()已经过时。 - Agostino

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Joel · Accepted Answer

首先问一个问题——您不想要孤立节点或多个连接组件的原因是什么？从原理上讲，真正的“随机”幂律图形将具有这些特征。

所以有几点需要注意：

1）如果使用expected_degree_graph，则很难消除孤立节点。这是因为许多节点的预期度数约为1（但实际度数来自泊松分布）。这意味着它们很可能会有小于1的度数。要验证这一点，请打印s。

2）另一种选择是使用配置模型图创建网络。对于此操作，我们从powerlaw序列中取出数字并取整数部分。丢弃值为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实现算法（不是模型，而是实现它的算法）做出了贡献。如果你有空，可以仔细阅读一下。这很棒。