Add and delete a random edge in networkx

Question

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!

Answer 1

Create a new random edge in networkx

Let's set up a test graph:

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

Now we can pick a random edge from a list of non-edge from the graph. It is not totally clear yet what is the probability you mentioned. Since you add a comment stating that you want to use random.choice I'll stick to that.

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

Usage exemple:

new_graph = random_edge(graph, del_orig=True)

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

We can still add a probability distribution over the edges in random.choiceif you need to (using numpy.random.choice() for instance).