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=
(G, niter=1, connectivity=True, seed=None)
| 26 | @py_random_state(3) |
| 27 | @nx._dispatchable(returns_graph=True) |
| 28 | def random_reference(G, niter=1, connectivity=True, seed=None): |
| 29 | """Compute a random graph by swapping edges of a given graph. |
| 30 | |
| 31 | Parameters |
| 32 | ---------- |
| 33 | G : graph |
| 34 | An undirected graph with 4 or more nodes. |
| 35 | |
| 36 | niter : integer (optional, default=1) |
| 37 | An edge is rewired approximately `niter` times. |
| 38 | |
| 39 | connectivity : boolean (optional, default=True) |
| 40 | When True, ensure connectivity for the randomized graph. |
| 41 | |
| 42 | seed : integer, random_state, or None (default) |
| 43 | Indicator of random number generation state. |
| 44 | See :ref:`Randomness<randomness>`. |
| 45 | |
| 46 | Returns |
| 47 | ------- |
| 48 | G : graph |
| 49 | The randomized graph. |
| 50 | |
| 51 | Raises |
| 52 | ------ |
| 53 | NetworkXError |
| 54 | If there are fewer than 4 nodes or 2 edges in `G` |
| 55 | |
| 56 | Notes |
| 57 | ----- |
| 58 | The implementation is adapted from the algorithm by Maslov and Sneppen |
| 59 | (2002) [1]_. |
| 60 | |
| 61 | References |
| 62 | ---------- |
| 63 | .. [1] Maslov, Sergei, and Kim Sneppen. |
| 64 | "Specificity and stability in topology of protein networks." |
| 65 | Science 296.5569 (2002): 910-913. |
| 66 | """ |
| 67 | if len(G) < 4: |
| 68 | raise nx.NetworkXError("Graph has fewer than four nodes.") |
| 69 | if len(G.edges) < 2: |
| 70 | raise nx.NetworkXError("Graph has fewer that 2 edges") |
| 71 | |
| 72 | from networkx.utils import cumulative_distribution, discrete_sequence |
| 73 | |
| 74 | local_conn = nx.connectivity.local_edge_connectivity |
| 75 | |
| 76 | G = G.copy() |
| 77 | keys, degrees = zip(*G.degree()) # keys, degree |
| 78 | cdf = cumulative_distribution(degrees) # cdf of degree |
| 79 | nnodes = len(G) |
| 80 | nedges = nx.number_of_edges(G) |
| 81 | niter = niter * nedges |
| 82 | ntries = int(nnodes * nedges / (nnodes * (nnodes - 1) / 2)) |
| 83 | swapcount = 0 |
| 84 | |
| 85 | for i in range(niter): |
searching dependent graphs…