graphscope.nx.generators.joint_degree_seq.directed_joint_degree_graph¶

graphscope.nx.generators.joint_degree_seq.directed_joint_degree_graph(in_degrees, out_degrees, nkk, seed=None)[source]¶

Generates a random simple directed graph with the joint degree.

Parameters:

degree_seq (list of tuples (of size 3)) – degree sequence contains tuples of nodes with node id, in degree and out degree.
nkk (dictionary of dictionary of integers) – directed joint degree dictionary, for nodes of out degree k (first level of dict) and nodes of in degree l (second level of dict) describes the number of edges.
seed (hashable object, optional) – Seed for random number generator.

Returns:

G – A directed graph with the specified inputs.

Return type:

Graph

Raises:

NetworkXError – If degree_seq and nkk are not realizable as a simple directed graph.

Notes

Similarly to the undirected version: In each iteration of the “while loop” the algorithm picks two disconnected nodes v and w, of degree k and l correspondingly, for which nkk[k][l] has not reached its target yet i.e. (for given k,l): n_edges_add < nkk[k][l]. It then adds edge (v,w) and always 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 disconnected nodes v and w, for which nkk[degree(v)][degree(w)] has not reached its target, even if one or both nodes do not have free stubs. If either node v or w does not have a free stub, we perform a “neighbor switch”, an edge rewiring move that releases a free stub while keeping nkk the same.

The difference for the directed version lies in the fact that neighbor switches might not be able to rewire, but in these cases unsaturated nodes can be reassigned to use instead, see [1] for detailed description and proofs.

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

References

[1] B. Tillman, A. Markopoulou, C. T. Butts & M. Gjoka,: “Construction of Directed 2K Graphs”. In Proc. of KDD 2017.

Examples

>>> in_degrees = [0, 1, 1, 2]
>>> out_degrees = [1, 1, 1, 1]
>>> nkk = {1: {1: 2, 2: 2}}
>>> G = nx.directed_joint_degree_graph(in_degrees, out_degrees, nkk)
>>>