在 networkx 中生成具有固定度数的小世界网络

Question

我正在尝试在 networkx 中创建一个具有固定度数的 SW 网络，但找不到如何操作重新布线过程。在 igraph 中，像这样创建一个 SW，其中所有节点的度数都为 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()

networkx中有类似的东西吗？我只能看到如何创建格子，但我找不到重新布线的函数。

Answer 1

我想你正在寻找 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)

编辑：

这是对 nx.random_reference 来源的改编。此版本的函数允许切换指定部分的边。节点度数和边数是守恒的。函数的原始版本是here。我用 #< 评论指出了所做的更改。

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

在 networkx 中生成具有固定度数的小世界网络

Generate Small World network with fixed degree in networkx

igraph

networkx

编辑：