在網絡中添加和刪除一個隨機邊緣

Question

我在Python中使用NetworkX。給定任何無向和無權圖，我想遍歷所有節點。對於每個節點，我想以概率p添加一個隨機邊和/或刪除該節點的現有隨機邊。有沒有簡單的方法來做到這一點？非常感謝！

Answer 1

給定一個節點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  

在行動中看到這樣的功能：

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() 

，你應該看到這樣的事情。

注意，你也可以做鄰接矩陣類似的東西， A = nx.adjacency_matrix(G).todense()（這是一個numpy的矩陣等等之類的操作A [我，：]。非零（）將是相關的）。如果你有非常大的網絡，這可能會更有效率。

Answer 2

創建networkx

一個新的隨機邊緣讓我們建立一個測試圖：

import networkx as nx 
import random 
import matplotlib.pyplot as plt 

graph = nx.Graph() 
graph.add_edges_from([(1,3), (3,5), (2,4)]) 
nx.draw(graph, with_labels=True) 
plt.show() 

現在我們可以從非邊緣的列表中選擇一個隨機邊緣圖形。現在還不完全清楚，你提到的可能性是多少。既然你添加了一條評論，說明你想使用random.choice我會堅持。

def random_edge(graph, del_orig=True): 
    ''' 
    Create a new random edge and delete one of its current edge if del_orig is True. 
    :param graph: networkx graph 
    :param del_orig: bool 
    :return: networkx graph 
    ''' 
    edges = list(graph.edges) 
    nonedges = list(nx.non_edges(graph)) 

    # random edge choice 
    chosen_edge = random.choice(edges) 
    chosen_nonedge = random.choice([x for x in nonedges if chosen_edge[0] == x[0]]) 

    if del_orig: 
     # delete chosen edge 
     graph.remove_edge(chosen_edge[0], chosen_edge[1]) 
    # add new edge 
    graph.add_edge(chosen_nonedge[0], chosen_nonedge[1]) 

    return graph 

用法爲例：

new_graph = random_edge(graph, del_orig=True) 

nx.draw(new_graph, with_labels=True) 
plt.show() 

我們仍然可以添加在邊緣的概率分佈在random.choice如果您需要（使用numpy.random.choice()例如）。