| """Generate graphs with given degree and triangle sequence.""" |
|
|
| import networkx as nx |
| from networkx.utils import py_random_state |
|
|
| __all__ = ["random_clustered_graph"] |
|
|
|
|
| @py_random_state(2) |
| @nx._dispatchable(graphs=None, returns_graph=True) |
| def random_clustered_graph(joint_degree_sequence, create_using=None, seed=None): |
| r"""Generate a random graph with the given joint independent edge degree and |
| triangle degree sequence. |
| |
| This uses a configuration model-like approach to generate a random graph |
| (with parallel edges and self-loops) by randomly assigning edges to match |
| the given joint degree sequence. |
| |
| The joint degree sequence is a list of pairs of integers of the form |
| $[(d_{1,i}, d_{1,t}), \dotsc, (d_{n,i}, d_{n,t})]$. According to this list, |
| vertex $u$ is a member of $d_{u,t}$ triangles and has $d_{u, i}$ other |
| edges. The number $d_{u,t}$ is the *triangle degree* of $u$ and the number |
| $d_{u,i}$ is the *independent edge degree*. |
| |
| Parameters |
| ---------- |
| joint_degree_sequence : list of integer pairs |
| Each list entry corresponds to the independent edge degree and |
| triangle degree of a node. |
| create_using : NetworkX graph constructor, optional (default MultiGraph) |
| Graph type to create. If graph instance, then cleared before populated. |
| seed : integer, random_state, or None (default) |
| Indicator of random number generation state. |
| See :ref:`Randomness<randomness>`. |
| |
| Returns |
| ------- |
| G : MultiGraph |
| A graph with the specified degree sequence. Nodes are labeled |
| starting at 0 with an index corresponding to the position in |
| deg_sequence. |
| |
| Raises |
| ------ |
| NetworkXError |
| If the independent edge degree sequence sum is not even |
| or the triangle degree sequence sum is not divisible by 3. |
| |
| Notes |
| ----- |
| As described by Miller [1]_ (see also Newman [2]_ for an equivalent |
| description). |
| |
| A non-graphical degree sequence (not realizable by some simple |
| graph) is allowed since this function returns graphs with self |
| loops and parallel edges. An exception is raised if the |
| independent degree sequence does not have an even sum or the |
| triangle degree sequence sum is not divisible by 3. |
| |
| This configuration model-like construction process can lead to |
| duplicate edges and loops. You can remove the self-loops and |
| parallel edges (see below) which will likely result in a graph |
| that doesn't have the exact degree sequence specified. This |
| "finite-size effect" decreases as the size of the graph increases. |
| |
| References |
| ---------- |
| .. [1] Joel C. Miller. "Percolation and epidemics in random clustered |
| networks". In: Physical review. E, Statistical, nonlinear, and soft |
| matter physics 80 (2 Part 1 August 2009). |
| .. [2] M. E. J. Newman. "Random Graphs with Clustering". |
| In: Physical Review Letters 103 (5 July 2009) |
| |
| Examples |
| -------- |
| >>> deg = [(1, 0), (1, 0), (1, 0), (2, 0), (1, 0), (2, 1), (0, 1), (0, 1)] |
| >>> G = nx.random_clustered_graph(deg) |
| |
| To remove parallel edges: |
| |
| >>> G = nx.Graph(G) |
| |
| To remove self loops: |
| |
| >>> G.remove_edges_from(nx.selfloop_edges(G)) |
| |
| """ |
| |
| joint_degree_sequence = list(joint_degree_sequence) |
|
|
| N = len(joint_degree_sequence) |
| G = nx.empty_graph(N, create_using, default=nx.MultiGraph) |
| if G.is_directed(): |
| raise nx.NetworkXError("Directed Graph not supported") |
|
|
| ilist = [] |
| tlist = [] |
| for n in G: |
| degrees = joint_degree_sequence[n] |
| for icount in range(degrees[0]): |
| ilist.append(n) |
| for tcount in range(degrees[1]): |
| tlist.append(n) |
|
|
| if len(ilist) % 2 != 0 or len(tlist) % 3 != 0: |
| raise nx.NetworkXError("Invalid degree sequence") |
|
|
| seed.shuffle(ilist) |
| seed.shuffle(tlist) |
| while ilist: |
| G.add_edge(ilist.pop(), ilist.pop()) |
| while tlist: |
| n1 = tlist.pop() |
| n2 = tlist.pop() |
| n3 = tlist.pop() |
| G.add_edges_from([(n1, n2), (n1, n3), (n2, n3)]) |
| return G |
|
|
