|
|
"""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._dispatch(graphs=None) |
|
|
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 |
|
|
|
