在networkx中添加和删除随机边缘
I'm using NetworkX in python. Given any undirected and unweighted graph, I want to loop through all the nodes. With each node, I want to add a random edge and/or delete an existing random edge for that node with probability p. Is there a simple way to do this? Thanks a lot!
我在python中使用NetworkX。给定任何无向和未加权的图形,我想循环遍历所有节点。对于每个节点,我想添加随机边缘和/或以概率p删除该节点的现有随机边缘。有一个简单的方法吗?非常感谢!
2 个解决方案
#1
1
Given a node i
, To add edges without duplication you need to know (1) what edges from i
already exist and then compute (2) the set of candidate edges that don't exist from i
. For removals, you already defined a method in the comment - which is based simply on (1). Here is a function that will provide one round of randomised addition and removal, based on list comprehensions
给定节点i,要添加没有重复的边缘,您需要知道(1)来自i的边缘已经存在,然后计算(2)i中不存在的候选边缘集合。对于删除,您已在注释中定义了一个方法 - 该方法仅基于(1)。这是一个基于列表推导提供一轮随机添加和删除的功能
def add_and_remove_edges(G, p_new_connection, p_remove_connection):
'''
for each node,
add a new connection to random other node, with prob p_new_connection,
remove a connection, with prob p_remove_connection
operates on G in-place
'''
new_edges = []
rem_edges = []
for node in G.nodes():
# find the other nodes this one is connected to
connected = [to for (fr, to) in G.edges(node)]
# and find the remainder of nodes, which are candidates for new edges
unconnected = [n for n in G.nodes() if not n in connected]
# probabilistically add a random edge
if len(unconnected): # only try if new edge is possible
if random.random() < p_new_connection:
new = random.choice(unconnected)
G.add_edge(node, new)
print "\tnew edge:\t {} -- {}".format(node, new)
new_edges.append( (node, new) )
# book-keeping, in case both add and remove done in same cycle
unconnected.remove(new)
connected.append(new)
# probabilistically remove a random edge
if len(connected): # only try if an edge exists to remove
if random.random() < p_remove_connection:
remove = random.choice(connected)
G.remove_edge(node, remove)
print "\tedge removed:\t {} -- {}".format(node, remove)
rem_edges.append( (node, remove) )
# book-keeping, in case lists are important later?
connected.remove(remove)
unconnected.append(remove)
return rem_edges, new_edges
To see this function in action:
要查看此功能的实际效果:
import networkx as nx
import random
import matplotlib.pyplot as plt
p_new_connection = 0.1
p_remove_connection = 0.1
G = nx.karate_club_graph() # sample graph (undirected, unweighted)
# show original
plt.figure(1); plt.clf()
fig, ax = plt.subplots(2,1, num=1, sharex=True, sharey=True)
pos = nx.spring_layout(G)
nx.draw_networkx(G, pos=pos, ax=ax[0])
# now apply one round of changes
rem_edges, new_edges = add_and_remove_edges(G, p_new_connection, p_remove_connection)
# and draw new version and highlight changes
nx.draw_networkx(G, pos=pos, ax=ax[1])
nx.draw_networkx_edges(G, pos=pos, ax=ax[1], edgelist=new_edges,
edge_color='b', width=4)
# note: to highlight edges that were removed, add them back in;
# This is obviously just for display!
G.add_edges_from(rem_edges)
nx.draw_networkx_edges(G, pos=pos, ax=ax[1], edgelist=rem_edges,
edge_color='r', style='dashed', width=4)
G.remove_edges_from(rem_edges)
plt.show()
And you should see something like this.
你应该看到这样的事情。
Note that you could also do something similar with the adjacency matrix, A = nx.adjacency_matrix(G).todense()
(it's a numpy matrix so operations like A[i,:].nonzero() would be relevant). This might be more efficient if you have extremely large networks.
请注意,您也可以使用邻接矩阵A = nx.adjacency_matrix(G).todense()执行类似的操作(它是一个numpy矩阵,因此像A [i,:]。nonzero()这样的操作是相关的)。如果您拥有极大的网络,这可能会更有效。
更多相关文章
- 在NumPy中更改数组边缘的值
- 迭代地在python中编写XML节点
- django npm和节点包体系结构
- 2D Numpy Array的边缘值
- Linux利用i节点删除乱码文件
- MySQL Cluster在线添加数据节点
- android 百度地图路线规划去掉节点图标
- android init进程分析 ueventd — 设备节点的创建、固件更新过