python - 扰动后保持无标度图的度分布 - python

Question

给定一个无标度图 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 来表示该图，我发现的只是删除或添加特定边的过程。知道如何实现上述内容吗？

Answer 1

这里有 2 种算法:

算法 1

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

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

经过很长一段时间后，每个节点“u”的期望度数就是其初始度数(但可能会更高或更低)。

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

注意 - 这将使度分布发生变化。

算法1a

这是一个高效的networkx实现，跳过了度数删除和添加，直接得到最终结果(假设一个networkx图G):

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

这是documentation

算法2

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

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

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

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