pymnet.sampling.reqs.default_check_reqs

pymnet.sampling.reqs.default_check_reqs(network, nodelist, layerlist, sizes, intersections, nnodes=None, nlayers=None, intersection_type='strict')

Checks whether a multilayer induced subgraph of the form [nodelist][layerlist] is connected, whether it has no empty layers or nodes, and whether it fulfills the given sizes and intersections requirements. Works on one-aspect multilayer networks.

Parameters:

networkMultilayerNetwork

A one-aspect multilayer network containing the induced subgraph.

nodelistlist of node names

The nodes in the induced subgraph.

layerlistlist of layer names

The layers in the induced subgraph.

sizeslist of ints > 0

How many nodes should be on each layer of an acceptable induced subgraph. One integer for each layer of an acceptable subgraph.

intersectionslist of ints >= 0 or Nones

How many nodes should be shared between sets of layers in an acceptable induced subgraph. If an entry in the list is None, any number of shared nodes is accepted. The order of the intersections is taken to follow the order of layers in sizes, with two-layer intersections being listed first, then three-layer intersections, etc. For more details, see section “Constructing the requirements”.

nnodesint

How many nodes an acceptable subgraph should have. If not provided, it will be calculated based on the sizes and intersections parameters. Required if there are Nones in intersections or if intersection_type is not “strict”. If you cannot guarantee the correctness of this number, do not use this parameter. Can be used in scripts to bypass calculating the correct number of nodes based on the sizes and intersections parameters.

nlayersint

How many layers an acceptable subgraph should have. If not provided, it will be calculated based on the sizes and intersections parameters. Required if there are Nones in intersections. If you cannot guarantee the correctness of this number, do not use this parameter. Can be used in scripts to bypass calculating the correct number of layers based on the sizes and intersections parameters.

intersection_typestring, “strict” or “less_or_equal”

If intersection_type is “strict”, all intersections must be exactly equal to entries in the intersections parameter. If intersection_type is “less_or_equal”, an intersection is allowed to be less than or equal to the corresponding entry in the intersections parameter. Usage is case-sensitive.

Returns:

True if the requirements are fulfilled, the induced subgraph has no empty nodes

or layers, and the induced subgraph is connected. False otherwise.

Notes

Empty nodes or layers

The phrase ‘does not contain any empty layers or nodes’ means that for each layer, there is at least one nodelayer in the induced subgraph, and that for each node, there is at least one nodelayer in the induced subgraph. In other words, each node in the nodelist and each layer in the layerlist appears at least once as the node identity or the layer identity, respectively, among the nodelayers present in the induced subgraph.

Constructing the requirements

The sizes list contains the desired number of nodes on each layer in any order. This means that the layers in the actual found sub-network can be in any order. However, the order of entries in sizes determines the order of entries in intersections. The intersections list is constructed as follows:

First, think of each size in the size list as having a specific role: the first entry in sizes corresponds to layer role A, the second to role B, the third to role C, and so on. This order determines how intersections in the intersections list are interpreted when checking if the requirements are fulfilled.

Then, construct the intersections list so that first all size-two intersections are listed, then size-three intersections, and so on, until the intersection between all layers is reached. The entry for each intersection can be an integer or None. An integer signifies the number of nodes in the intersection (the cardinality of the intersection set), and it can be followed strictly or less strictly, depending on the intersection_type parameter. The value None signifies that the intersection in question can have any size in an acceptable induced subgraph. If intersections contains Nones, the nnodes and nlayers parameters must also be specified.

The order of listing size-n intersections is such that the closer the role is to the beginning of the size list, the later it is iterated over. More specifically, this is the order that itertools.combinations() uses to iterate. Since we signify the roles by letters A, B, C and so on, this means that the intersections are listed in “alphabetical order” within each size category.

For example, suppose we have a length-four sizes list. Now, we think of the first size entry as layer (role) A, the second as layer B, the third as layer C, and the fourth as layer D. The intersections list is then assumed to contain the intersections in the following order:

intersections = [A∩B, A∩C, A∩D, B∩C, B∩D, C∩D, A∩B∩C, A∩B∩D, A∩C∩D, B∩C∩D, A∩B∩C∩D]

When checking whether the size and intersection requirements are fulfilled, each possible set of role assignments to the actual layers is checked. If even one is suitable, the function returns True.

Continuing from the example above, if the actual induced subgraph has layers [X,Y,Z,W], all possible role assignment combinations are checked (X takes role from the set {A,B,C,D}, Y takes role from {A,B,C,D} minus {role(X)}, Z takes role from {A,B,C,D} minus {role(X),role(Y)}, W takes role from {A,B,C,D} minus {role(X),role(Y),role(Z)}). The role assignment is iterated until an acceptable role assignment is found – at which point the function returns True – or until all possible role assignments have been considered without success – at which point the function returns False.

This also means that the orderings of the [nodelist] and [layerlist] of the induced subgraph to be tested do not matter (i.e calling this function with nodelist = [1,2] and layerlist = [‘X’,’Y’] gives the exact same return value as nodelist = [2,1] and layerlist = [‘Y’,’X’], etc.).

Using Nones

If we only care about the cardinalities of some specific intersections, we can set the rest to None. For example, calling

>>> default_check_reqs(some_network,some_nodelist,some_layerlist,[1,2,3],[None,None,2,None],nnodes=4,nlayers=3)

means that the algorithm will find the induced subgraphs which are connected, have 4 nodes and 3 layers, have no empty layers or nodes, have one node on one layer, two nodes on another layer, three nodes on the third layer, and have a cardinality-2 (size-2) intersection between the layer that has two nodes and the layer that has three nodes (with no constraints on the cardinalities of the other intersections).

When using Nones, nnodes and nlayers have to be specified, since if all intersection cardinalities are not unambiguous, the nnodes and nlayers cannot be calculated based on the sizes and intersections alone. It is up to the user to provide nnodes and nlayers that are sensible (for example, nnodes cannot sensibly be more than the sum of all sizes). It is also up to the user to not give contradictory requirements. Technically, only nnodes would be required, but both have to be given to make the function call more explicit and more intuitive to read.

Examples

Suppose we have the multilayer network N:

(1,'X')----(2,'X')    (3,'X')
              |
              |
           (2,'Y')

where (a,b) are nodelayer tuples with a = node identity and b = layer identity. Now,

>>> default_check_reqs(N,[1,2],['X','Y'],[1,2],[1])

returns True, as do

>>> default_check_reqs(N,[2,1],['Y','X'],[1,2],[1])

and

>>> default_check_reqs(N,[1,2],['Y','X'],[2,1],[1])

(and naturally so do also all the other ways of defining the same induced subgraph and the same requirements).

On the other hand,

>>> default_check_reqs(N,[2,3],['X','Y'],[1,2],[1])

returns False, since the induced subgraph is not connected.