joint_degree_graph

joint_degree_graph(joint_degrees, seed=None)

Generates a random simple graph with the given joint degree dictionary.

Parameters:

joint_degreesdictionary of dictionary of integers

A joint degree dictionary in which entry joint_degrees[k][l] is the number of edges joining nodes of degree k with nodes of degree l.

seedinteger, random_state, or None (default)

Indicator of random number generation state. See Randomness.

Returns:

GGraph

A graph with the specified joint degree dictionary.

Raises:

NetworkXError

If joint_degrees dictionary is not realizable.

Notes

In each iteration of the “while loop” the algorithm picks two disconnected nodes v and w, of degree k and l correspondingly, for which joint_degrees[k][l] has not reached its target yet. It then adds edge (v, w) and increases the number of edges in graph G by one.

The intelligence of the algorithm lies in the fact that it is always possible to add an edge between such disconnected nodes v and w, even if one or both nodes do not have free stubs. That is made possible by executing a “neighbor switch”, an edge rewiring move that releases a free stub while keeping the joint degree of G the same.

The algorithm continues for E (number of edges) iterations of the “while loop”, at the which point all entries of the given joint_degrees[k][l] have reached their target values and the construction is complete.

References

[1]

M. Gjoka, B. Tillman, A. Markopoulou, “Construction of Simple Graphs with a Target Joint Degree Matrix and Beyond”, IEEE Infocom, ‘15

Examples

>>> joint_degrees = {
...     1: {4: 1},
...     2: {2: 2, 3: 2, 4: 2},
...     3: {2: 2, 4: 1},
...     4: {1: 1, 2: 2, 3: 1},
... }
>>> G = nx.joint_degree_graph(joint_degrees)
>>>