networkx.generators.joint_degree_seq.joint_degree_graph¶
-
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 (hashable object, optional) – Seed for random number generator.
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
>>> import networkx as nx >>> 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) >>>
- joint_degrees (dictionary of dictionary of integers) – A joint degree dictionary in which entry