2

给定一个无标度图 G（一个度分布为幂律的图），以及以下过程：

for i in range(C):
    coint = randint(0,1)
    if (coint == 0):
        delete_random_edges(G)
    else:
        add_random_edge(G)

（C 是一个常数）
因此，当 C 很大时，过程后的度数分布将更像 G(n,p)。我有兴趣保留幂律分布，即 - 我希望图形在此过程之后是无标度的，即使对于大型 C。

我的想法是编写程序“delete_random_edges”和“add_random_edge”，以提供边缘连接到度数大的节点被删除的概率小（添加新边时，更有可能将其添加到度数大的节点）。

我使用 Networkx 来表示图形，我发现的只是删除或添加特定边的过程。知道如何实现上述功能吗？

4

3 回答 3

1

尽管您已经接受了@abdallah-sobehy 的答案，这意味着它有效，但我建议采用更简单的方法，以防它对您或周围的任何人有所帮助。

您尝试做的有时称为优先连接（好吧，至少在您添加节点时），并且很久以前开发了一个随机模型，请参阅Barabasi-Albert 模型，它导致等式的幂律gamma分布-3。

基本上，您必须添加概率等于节点度数除以所有节点度数之和的边。您可以scipy.stats使用这样的代码定义概率分布，

import scipy.stats as stats
x = Gx.nodes()
sum_degrees = sum(list(Gx.degree(Gx).values()))
p = [Gx.degree(x)/sum_degrees for x in Gx]
custm = stats.rv_discrete(name='custm', values=(x, p))

然后，您只需按照该分布选择 2 个节点，这就是您添加边的 2 个节点，

custm.rvs(size=2)

至于删除节点，我自己没试过。但我想你可以使用这样的东西，

sum_inv_degrees = sum([1/ x for x in list(Gx.degree(Gx).values())])
p = [1 / (Gx.degree(x) * sum_inv_degrees) for x in Gx]

虽然老实说我不完全确定；它不再是我上面链接到的随机模型......

无论如何，希望它有所帮助。

评论后更新

实际上，通过使用这种方法向现有图表添加节点，您可能会得到 2 个不希望的结果：

  • 重复的链接
  • 自链接

您可以删除这些，尽管它会使结果偏离预期的分布。

无论如何，您应该考虑到您已经偏离了优先连接模型，因为 Barabasi-Albert 研究的算法可以向现有图添加新节点和链接，

该网络以 m_0 个节点的初始连接网络开始。一次将一个新节点添加到网络中。每个新节点连接到 m > m_0 个现有节点的概率与数量成正比...

（见这里）

如果您想获得精确的分布（而不是扩大现有网络并保持其属性），您可能最好使用@joel 的答案

希望能帮助到你。

于 2015-10-11T16:07:05.120 回答
1

这里有2个算法：

算法 1

该算法并没有准确地保留度数，而是保留了预期的度数。

保存每个节点的初始度数。然后随机删除边。每当您创建一条边时，请通过随机选择两个节点来实现，每个节点的概率与这些节点的初始度成正比。

经过很长一段时间后，每个节点 'u' 的预期度数是它的初始度数（但它可能会更高或更低）。

基本上，这将创建所谓的 Chung-Lu 随机图。Networkx 有一个用于创建它们的内置算法。

注意 - 这将允许学位分布发生变化。

算法 1a

这是跳过度数删除和添加并直接进入最终结果的高效 networkx 实现（假设 networkx graph G）：

degree_list = G.degree().values()
H = nx.expected_degree_graph(degree_list)

这是文档

算法 2

该算法准确地保留了度数。

选择一组边并将它们折断。创建一个列表，每个节点的出现等于它所在的断边数。随机播放此列表。在此列表中彼此相邻的节点之间创建新边。

检查以确保您永远不会将节点加入到自身或已经是邻居的节点。如果发生这种情况，您将需要考虑一种自定义方法来避免它。一种选择是简单地重新排列列表。另一种方法是将这些节点放在一边，并在下次执行此操作时将它们包含在您创建的列表中。

编辑 有一个内置的 networkx 命令double_edge_swap可以一次交换两条边。文件

于 2015-10-14T01:30:25.073 回答
0

我不确定这将在多大程度上保留无标度属性，但这可能是实现您的想法的一种方式：

为了添加一条边，您需要在 networkx 中指定 2 个节点。因此，您可以选择一个概率与（度）成正比的节点，而另一个节点则被统一选择（没有任何偏好）。选择一个高度连接的节点可以实现如下：

对于节点为 [0,1,2,...,n] 的图 G

1) 创建一个介于 0 和 1 之间的浮点数（限制）列表，为每个节点指定根据其度 ^2 选择的概率。例如：limits[1] - limits[0] 是选择节点 0 的概率，limits[2] - limits[1] 是选择节点 2 的概率等。

# limits is a list that stores floats between 0 and 1 which defines
# the probabaility of choosing a certain node depending on its degree
limits = [0.0]
# store total number of edges of the graph; the summation of all degrees is 2*num_edges
num_edges = G.number_of_edges()
# store the degree of all nodes in a list
degrees = G.degree()
# iterate nodes to calculate limits depending on degree
for i in G:
    limits.append(G.degree(i)/(2*num_edges) + limits[i])

2) 随机生成一个介于 0 和 1 之间的数字，然后将其与限制进行比较，并相应地选择要添加边的节点：

rnd = np.random.random()
# compare the random number to the limits and choose node accordingly
for j in range(len(limits) - 1):
    if rnd >= limits[j] and rnd < limits[j+1]:
         chosen_node = G.node[j]

3) 通过生成[0,n]之间的随机整数，统一选择另一个节点

4) 在两个选定节点之间添加一条边。

5）同样删除边，可以根据（1/degree）而不是degree选择一个节点，然后统一删除它的任何边。

有趣的是，使用这种方法是否会保留无标度属性以及该属性在哪个“C”处丢失，因此请告诉我们它是否有效。

编辑：正如@joel 所建议的那样，选择要添加边的节点应该与度数而不是度数^ 2 成正比。我已经相应地编辑了第 1 步。

EDIT2：这可能有助于您判断无标度图在添加和删除边后是否失去了属性。只需计算更改前后的优惠附加分数。你可以在这里找到文档。

于 2015-10-11T13:45:48.007 回答