Generate Small World network with fixed degree in networkx

Question

I am trying to create a SW network with fixed degree in networkx, but cannot find how to manipulate the rewiring process. In igraph, something like this creates a SW where all nodes have a degree of 8:

import igraph
g = igraph.Graph.Lattice([1,100], nei=4, directed=False, mutual=False, circular=True)
g.rewire(n=int(g.ecount()*0.05), mode="simple")
g.degree()

Is there anything similar in networkx? I can only see how to create a Lattice, but I failed at finding functions for the rewiring.

Answer 1

I suppose you are looking for nx.random_reference:

import networkx as nx


G = nx.grid_graph(dim=[3,10], periodic=True)


pos = nx.spring_layout(G)

plt.subplot(1,2,1)
nx.draw_networkx(G, pos=pos,with_labels=False)

plt.subplot(1,2,2)
H = nx.random_reference(G)
nx.draw_networkx(H, pos=pos, with_labels=False)

edit:

This is an adaptation of the source of nx.random_reference. This version of the function allows a specifiable fraction of the edges to be switched. Node degree and edge numbers are conserved. The original version of the function is here. I indicated changes made with #< comments.

def random_reference(G, niter=1, connectivity=True, seed=None, fraction=1.0): #< fraction kwarg was added
    """Compute a random graph by swapping edges of a given graph.

    Parameters
    ----------
    G : graph
        An undirected graph with 4 or more nodes.

    niter : integer (optional, default=1)
        An edge is rewired approximately `niter` times.

    connectivity : boolean (optional, default=True)
        When True, ensure connectivity for the randomized graph.

    seed : integer, random_state, or None (default)
        Indicator of random number generation state.
        See :ref:`Randomness<randomness>`.
    fraction: fraction of edges that undergo rewiring #<

    Returns
    -------
    G : graph
        The randomized graph.

    Notes
    -----
    The implementation is adapted from the algorithm by Maslov and Sneppen
    (2002) [1]_.

    References
    ----------
    .. [1] Maslov, Sergei, and Kim Sneppen.
           "Specificity and stability in topology of protein networks."
           Science 296.5569 (2002): 910-913.
    """
    if G.is_directed():
        msg = "random_reference() not defined for directed graphs."
        raise nx.NetworkXError(msg)
    if len(G) < 4:
        raise nx.NetworkXError("Graph has less than four nodes.")

    from networkx.utils import cumulative_distribution, discrete_sequence
    local_conn = nx.connectivity.local_edge_connectivity
    import random  #< needed to replace seed.choice below. 

    G = G.copy()
    keys, degrees = zip(*G.degree())  # keys, degree
    cdf = nx.utils.cumulative_distribution(degrees)  # cdf of degree
    nnodes = len(G)
    nedges = nx.number_of_edges(G)
    niter = niter*nedges
    # ntries = int(nnodes*nedges/(nnodes*(nnodes-1)/2)) #< original version
    ntries = int(fraction * nedges) #<
    if ntries % 2 !=0: #< ensure even numbers
        ntries += 1 #<

    swapcount = 0

    for i in range(niter):
        n = 0
        while n < ntries:
            # pick two random edges without creating edge list
            # choose source node indices from discrete distribution
            (ai, ci) = discrete_sequence(2, cdistribution=cdf, seed=seed)
            if ai == ci:
                continue  # same source, skip
            a = keys[ai]  # convert index to label
            c = keys[ci]
            # choose target uniformly from neighbors
            b = random.choice(list(G.neighbors(a)))  #< changed seed.choice to random.choice
            d = random.choice(list(G.neighbors(c)))  #< changed seed.choice to random.choice
            bi = keys.index(b)
            di = keys.index(d)
            if b in [a, c, d] or d in [a, b, c]:
                continue  # all vertices should be different

            # don't create parallel edges
            if (d not in G[a]) and (b not in G[c]):
                G.add_edge(a, d)
                G.add_edge(c, b)
                G.remove_edge(a, b)
                G.remove_edge(c, d)

                # Check if the graph is still connected
                if connectivity and local_conn(G, a, b) == 0:
                    # Not connected, revert the swap
                    G.remove_edge(a, d)
                    G.remove_edge(c, b)
                    G.add_edge(a, b)
                    G.add_edge(c, d)
                else:
                    swapcount += 1
                    break
            n += 1
    return G