graphscope.nx.generators.joint_degree_seq.joint_degree_graph
- graphscope.nx.generators.joint_degree_seq.joint_degree_graph(joint_degrees, seed=None)[source]
Generates a random simple graph with the given joint degree dictionary.
- Parameters
joint_degrees (dictionary 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.seed (integer, random_state, or None (default)) – Indicator of random number generation state. See Randomness.
- Returns
G – A graph with the specified joint degree dictionary.
- Return type
- 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) >>>