扰动后保持无标度图的度分布 - 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

我不确定这将在多大程度上保持自由尺度属性但这可以成为实现您的想法的一种方式：

In order to add an edge you need to specify 2 nodes in networkx. so, you can choose one node with a probability that is proportional to (degree) and the other node to be uniformly chosen (without any preferences). Choosing a highly connected node can be achieved as follows:

对于节点为 [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)而不是度选择一个节点，然后统一删除它的任意一条边。

It is interesting to know if using this approach would reserve the scale free property and at which 'C' the property is lost , so let us know if it worked or not.

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

EDIT2：这可能会帮助您判断无标度图在添加和删除边后是否丢失了属性。只需计算更改前后的优先attachmet分数。您可以找到证明 here.

Answer 2

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

您尝试做的有时称为优先依附（好吧，至少在您添加节点时是这样），为此有一个很久以前开发的随机模型，请参阅 Barabasi-Albert model，这导致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]

虽然老实说我不太确定；它不再是我 link 以上的随机模型...

希望对您有所帮助。

评论后更新

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

重复 links
自己links

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

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

The network begins with an initial connected network of m_0 nodes. New nodes are added to the network one at a time. Each new node is connected to m > m_0 existing nodes with a probability that is proportional to the number ...

（参见 here）

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

的答案

希望对您有所帮助。

Answer 3

这里有 2 个算法：

算法一

此算法并未准确保留度数，而是保留了预期度数。

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

经过很长一段时间后，每个节点的期望度数'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

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

Keeping scale free graph's degree distribution after perturbation - python

python

graph

power-law

networkx