Skip to main content
`Ctrl`+`K`

# is_valid_directed_joint_degree

is_valid_directed_joint_degree(in_degrees, out_degrees, nkk)

  Checks whether the given directed joint degree input is realizable

  Parameters:
    in_degrees list of integers

      in degree sequence contains the in degrees of nodes.

    out_degrees list of integers

      out degree sequence contains the out degrees of nodes.

    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.

  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.