扰动后保持无标度图的度分布 - python
Keeping scale free graph's degree distribution after perturbation - python
给定无标度图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 来表示图形，我发现的只是删除或添加特定边的过程。知道如何实现上述内容吗？
我不确定这将在多大程度上保持自由尺度 属性 但这可以成为实现您的想法的一种方式：
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.
虽然您已经接受了@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
的答案
希望对您有所帮助。
这里有 2 个算法：
算法一
此算法并未准确保留度数，而是保留了预期度数。
保存每个节点的初始度。然后随机删除边。每当你创建边时，通过随机选择两个节点来实现，每个节点的概率与这些节点的初始度成正比。
经过很长一段时间后，每个节点的期望度数'u'就是它的初始度数（但可能会高一点或低一点）。
基本上，这将创建所谓的 Chung-Lu 随机图。 Networkx 有一个用于创建它们的内置算法。
注意 - 这将允许学位分布发生变化。
算法 1a
这是高效的 networkx 实现，跳过度数删除和添加并直接进入最终结果（假设 networkx 图 G）：
degree_list = G.degree().values()
H = nx.expected_degree_graph(degree_list)
算法2
该算法准确地保留了度数。
选择一组边并打断它们。创建一个列表，每个节点出现的次数等于它所在的断边数。打乱这个列表。在该列表中彼此相邻的节点之间创建新边。
检查以确保您永远不会将节点加入到自身或已经是邻居的节点中。如果发生这种情况，您将需要考虑一种自定义方法来避免它。一种选择是简单地重新排列列表。另一种方法是将这些节点放在一边，并将它们包含在您下次执行此操作时创建的列表中。
编辑
有一个内置的 networkx 命令 double_edge_swap 可以一次交换两条边。 documentation
给定无标度图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 来表示图形，我发现的只是删除或添加特定边的过程。知道如何实现上述内容吗？
我不确定这将在多大程度上保持自由尺度 属性 但这可以成为实现您的想法的一种方式：
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.
虽然您已经接受了@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
的答案希望对您有所帮助。
这里有 2 个算法：
算法一
此算法并未准确保留度数，而是保留了预期度数。
保存每个节点的初始度。然后随机删除边。每当你创建边时，通过随机选择两个节点来实现，每个节点的概率与这些节点的初始度成正比。
经过很长一段时间后，每个节点的期望度数'u'就是它的初始度数（但可能会高一点或低一点）。
基本上，这将创建所谓的 Chung-Lu 随机图。 Networkx 有一个用于创建它们的内置算法。
注意 - 这将允许学位分布发生变化。
算法 1a
这是高效的 networkx 实现，跳过度数删除和添加并直接进入最终结果（假设 networkx 图 G）：
degree_list = G.degree().values()
H = nx.expected_degree_graph(degree_list)
算法2
该算法准确地保留了度数。
选择一组边并打断它们。创建一个列表，每个节点出现的次数等于它所在的断边数。打乱这个列表。在该列表中彼此相邻的节点之间创建新边。
检查以确保您永远不会将节点加入到自身或已经是邻居的节点中。如果发生这种情况，您将需要考虑一种自定义方法来避免它。一种选择是简单地重新排列列表。另一种方法是将这些节点放在一边，并将它们包含在您下次执行此操作时创建的列表中。
编辑
有一个内置的 networkx 命令 double_edge_swap 可以一次交换两条边。 documentation