networkxのランダムエッジの追加と削除

Question

私はPythonでNetworkXを使用しています。無向グラフと非重みグラフがある場合、すべてのノードをループしたいと思う。各ノードでは、ランダムなエッジを追加したり、確率pでそのノードの既存のランダムエッジを削除したりします。これを行う簡単な方法はありますか？どうもありがとう！

Answer 1

与えられたノードi重複なしでエッジを追加するには、（1）iからどのエッジが既に存在しているかを知り、次に存在しない候補エッジの集合を計算する必要があります（i）。削除の場合、既にコメントにメソッドを定義しています。これは単に（1）に基づいています。

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

そして、あなたはこのように表示されます。ここでは はアクションでこの機能を確認するには、リストの内包表記

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  

に基づいて、ランダム化された追加および除去の1ラウンドを提供する関数です。

あなたはまた、隣接行列と似た何かができるノート、 A = nx.adjacency_matrix(G).todense()（A [I、：]のように操作して、それがnumpyの行列です。）（ゼロ以外が関連になります）。非常に大規模なネットワークを使用すると、これはより効率的になる可能性があります。

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 

使用exemple：

new_graph = random_edge(graph, del_orig=True) 

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

あなたが（例えばnumpy.random.choice()を使用）する必要がある場合我々はまだrandom.choiceにおけるエッジの確率分布を追加することができます。