is_valid_directed_joint_degree

is_valid_directed_joint_degree(in_degrees, out_degrees, nkk)[source]

Checks whether the given directed joint degree input is realizable

Parameters
in_degreeslist of integers

in degree sequence contains the in degrees of nodes.

out_degreeslist of integers

out degree sequence contains the out degrees of nodes.

nkkdictionary of dictionary of integers

directed joint degree dictionary. for nodes of out degree k (first level of dict) and nodes of in degree l (seconnd level of dict) describes the number of edges.

Returns
boolean

returns true if given input is realizable, else returns false.

Notes

Here is the list of conditions that the inputs (in/out degree sequences, nkk) need to satisfy for simple directed graph realizability:

  • Condition 0: in_degrees and out_degrees have the same length

  • Condition 1: nkk[k][l] is integer for all k,l

  • Condition 2: sum(nkk[k])/k = number of nodes with partition id k, is an

    integer and matching degree sequence

  • Condition 3: number of edges and non-chords between k and l cannot exceed

    maximum possible number of edges

References

[1] B. Tillman, A. Markopoulou, C. T. Butts & M. Gjoka,

“Construction of Directed 2K Graphs”. In Proc. of KDD 2017.