(Linear) Structural Control

Structural control is one of the major tools used to study control (and specifically controllability) of directed networks. Structural control is a relaxation of conventional control methods in which the (edge) weights of the interactions between nodes are omitted and properties are based only on the structure (topology) of the interconnections. Most work with structural control assumes a linear dynamics model of the underlying system (linear differential or difference equation describing the state).

netcontrolz provides tools to build the Cacti, which contains most information about the structural control properties of a network; tools to compute the control profile of a network, a statistic used to classify functional types of networks; and tools to compute the robustness of the network control properties of a graph under edge failure and attack.

To access the most basic structural control properties of a graph without building a Cacti, you may use the following complementary functions.

netcontrolz.num_dilations(G)[source]

Returns the number of dilations in the directed network G. This is also equivalent to the fewest number of controls that are required to structurally control the graph G (except in the degenerate case when there are zero dilations and there must still be one control).

netcontrolz.generic_rank(G)[source]

Returns the generic rank of the graph G. This is equivalent to the size of the maximum matching of the graph G; also equivalent to the difference between the number of nodes in the network and the number of dilations, see method netcontrolz.num_dilations.

Constructing the Cacti of a Directed Graph

netcontrolz provides several handles to create the Cacti for studying structural control. A cactus is a collection of a single stem and any number of buds, which are cycles that have a node with a distinguished inbound edge from a node in the stem or from a node in an existing bud. The follow constructor functions provide ways to build the cacti that cover a directed graph when provided with: no controls, specific nodes to be controlled, or only a number of controls to be used. Alternatively, you may provide a matching of your own choice and construct the Cacti from it.

netcontrolz.build_cacti(G)[source]

This method constructs Cacti for a given directed graph G using maximum unweighted matching. The resulting matching forms a cacti which also gives the minimum number (and one possible set of locations/configuration) of controls required for the full control of the network.

The degeneracy of the matching and the ambiguity/flexibility of attaching buds to stems and other cycles means that there are many ways to map the mapping into a collection of Cactus structures. In this implementation, we opportunistically (whichever comes first) attach cycles as buds to stems, then opportunistically attach cycles as buds to existing buds, then opportunistically attach cycles to other non-bud cycles. This serves to minimize the number of connections that the controls need to make in the network. There could be a variety of other strategies. This may effect energy quantifications or robustness qualities of the network, especially if the control properties are largely determined by the cycles in the network.

Returns a Cacti object.

netcontrolz.build_cacti_free_controls(G, num_ctls)[source]

This method constructs Cacti for a given directed graph G and a fixed number of controls that can be assigned to any nodes in G. Maximum perfect weighted matching is used to calculate reachable/controllable nodes given the number of controls.

Args:
  • num_ctls (int): Number of control nodes (must be greater than one) that are to be attached to the nodes in G. If num_ctls was 0, a degenerate matching of only cycles would be found.
KwArgs:
  • randomize[=False] (Boolean). Indicates whether the matching should be randomized.

Returns a Cacti object.

netcontrolz.build_cacti_fixed_controls(G, fixed_ctls[, with_cycles=False])[source]

This method constructs Cacti for a given directed graph G and set of controls that are fixed to some nodes in G. Maximum perfect weighted matching is used to calculate reachable/controllable nodes given the fixed controls.

Args: see method build_cacti_fixed_controls_
Only difference here is that fixed_ctls are node objs and not indices.

Returns a Cacti object.

netcontrolz.build_cacti_fixed_controls_(G, fixed_ctls[, with_cycles=False])[source]

This method constructs Cacti for a given directed graph G and set of controls that are fixed to some nodes in G. Maximum perfect weighted matching is used to calculate reachable/controllable nodes given the fixed controls.

Args:
  • fixed_ctls (LIST_OF_TUPLES)

    • LIST_OF_TUPLES: Represents control nodes that are attached to the nodes in G. e.g., [(1,),(3,)] represents two controls that are attached to node indices 1 and 3 in G.
KwArgs:
  • randomize[=False] (Boolean). Indicates whether the matching should be randomized.
  • with_cycles[=False] (Boolean). Indicates whether cycles not reachable from the fixed_ctls should be included in the matching/cacti.
Raises:
ValueError: if fixed_ctls is None.

Returns a Cacti object.

netcontrolz.build_cacti_from_matching(G, fixed_ctls, matching[, roots=None])[source]

This method constructs Cacti for a given directed graph G and a precomputed matching. This requires the matching, the roots of the matching and the subset of roots that are controlled (the fixed_ctrls).

Args: see method build_cacti_from_matching_
Only difference here is that fixed_ctls are node objs and not indices. The matching is passed as tuples of node pairs.

Returns a Cacti object.

netcontrolz.build_cacti_from_matching_(G, fixed_ctls, matching[, roots=None])[source]

This method constructs Cacti for a given directed graph G and a precomputed matching. This requires the matching, the roots of the matching and the subset of roots that are controlled (the fixed_ctrls).

Args:
  • fixed_ctls (LIST_OF_TUPLES)

    • LIST_OF_TUPLES: Represents control nodes that are attached to the nodes in G. e.g., [(1,),(3,)] represents two controls that are attached to node indices 1 and 3 in G. These indices should be a subset of the roots of the matching or part of a cycle.
  • matching (list) The list of edge indices that indicate the edges belonging to a maximum-matching for the graph.

  • roots (list) The roots of the matching (the indices of the nodes at the base of the stems of the matching); if none, the roots are identified automatically.

Raises:
ValueError: if fixed_ctls or matching is None.

Returns a Cacti object.

Accessing the Cacti of a Directed Graph

Once the Cacti are formed, questions regarding the number of controls or the number of nodes that are controllable can be answered. The Stem and Cycle classes provide handles to traverse the cacti.

class netcontrolz.cacti.Cacti[source]

The Cacti class represents the cacti control structure of a given network. It can be used to find the location (and number) of inputs required to control the network as well as to access the underlying cacti structure. It can also be used to find the extent to which a network can be controlled by a specified set of controls and the related constrained cacti.

controllable_nodes()[source]

Returns the set of nodes (objects) that are controllable.

controllable_nodes_()[source]

Returns the set of nodes (indices) that are controllable.

controls()[source]

Returns list of nodes (objects) where controls are attached. In case of unweighted matching, it is the minimum number of controls required for full control of the network. In case of weighted matching (when fixed set of controls are given), this method returns the controls that are sufficient for controlling the maximum possible nodes of the network.

controls_()[source]

Returns list of nodes (indices) where controls should be attached. In case of unweighted matching, it is the minimum number of controls required for full control of the network. In case of weighted matching (when fixed set of controls are given), this method returns the controls that are sufficient for controlling the maximum possible nodes of the network.

cycles()[source]

Returns a lit of cycles contained in the cacti. Some cycles may be buds connected to either the stem or another bud via a distinguished edge.

matching()[source]

Returns the matching used to create this Cacti object, in form of a list of edges (u,v) where u and v are node objects, as calculated by the maximum matching algorithm (unweighted or weighted as the case maybe). Note that there is degeneracy in the matching, so this may be just one possible matching.

matching_()[source]

Returns the matching used to create this Cacti object, in form of a list of edge indices, as calculated by the maximum matching algorithm (unweighted or weighted as the case maybe). Note that there is degeneracy in the matching, so this may be just one possible matching.

non_bud_cycles()[source]

Returns the non-bud (independent cycles without distinguished edges).

num_controllable_nodes()[source]

Returns the number of nodes that are controllable.

num_controls()[source]

Returns the number of controls/inputs used to control the network.

stems()[source]

Returns a list of stems comprising the cacti.

class netcontrolz.cacti.Stem[source]

An instance of Stem represents a single stem (with reference to any associated buds) in a cacti structure.

buds()[source]

Returns a list of buds (Cycle objects) that are attached to this stem

buds_iter()[source]

Returns an iterator over buds (Cycle objects) that are attached to this stem

length_with_buds()[source]

Returns the length of the stem including the buds attached to it.

origin()[source]

Returns the origin or starting node (object) of the stem.

origin_()[source]

Returns the origin or starting node (index) of the stem.

terminus()[source]

Returns the terminus or end node (object) of the stem.

terminus_()[source]

Returns the terminus or end node (index) of the stem.

class netcontrolz.cacti.Cycle[source]

Cycle can either be a bud that is connected to a stem by a distinguished node or an independent cycle (no associated stem).

buds()[source]

Returns a list of buds (Cycle objects) that are attached to this cycle

buds_iter()[source]

Returns an iterator over buds (Cycle objects) that are attached to this stem

dist_edge()[source]

Returns the distinguished edge (u,v) (node objects) where u is in the stem and v is in this cycle/bud of the stem. Returns None if this cycle is not a bud.

dist_edge_()[source]

Returns the distinguished edge e (edge index) where src(e) is in the stem and tgt(e) is in this cycle/bud of the stem. Returns -1 if this cycle is not a bud.

dist_node()[source]

Returns the distinguished node (object) of the stem to which this cycle is attached if it is a bud, otherwise return None.

dist_node_()[source]

Returns the distinguished node (index) of the stem to which this cycle is attached if it is a bud, otherwise return -1.

distinguished_root()[source]

Returns the stem or cycle to which this cycle is attached if it is a bud, otherwise return None.

is_bud()[source]

Returns True if this cycle is a bud.

length_with_buds()[source]

Returns the length of the cycle including the buds attached to it.

origin()[source]

A starting node (object) of this cycle, in the case of a bud this is the node where the distinguished edge is pointing to. In the case of a non-bud cycle, returns None.

origin_()[source]

A starting node (index) of this cycle, in the case of a bud this is the node where the distinguished edge is pointing to. In the case of a non-bud cycle, returns -1.

Computing & Plotting the Control Profile

Control profiles were devised as a measure for quantifying the structures responsible for dictating how many controls a network requires and where these controls much attach to the network.

See also

Justin Ruths and Derek Ruths. Control Profiles of Complex Networks. Science, 343(6177), 1373-1376 (2014).

netcontrolz.profile(G[, normalized=True])[source]

Compute the control profile for the directed network G.

KwArgs:
  • normalized [=True] (boolean). Indicates whether each element in the control profile should be normalized by the number of controls.
Returns:
(s,e,i). The control profile consisting of the source controls, external-dilation controls, and internal-dilation controls. Un-normalized, these values with the the number of each. Normalized these values will be the fraction of all controls needed by the network belonging to each type.

Visualizing control profile plots can be particularly helpful when comparing the control profiles of different networks. Two functions are provided for this purpose.

netcontrolz.profile_plot(G, ...)[source]

Plots a set of control profiles on a triangular control profile plot. Each of the items specified can be either a control profile 3-tuple, 3-list, or zen.DiGraph (in which case the control profile of the graph will be computed and then plotted).

Most of the usual matplotlib plotting features are supported (see keyword arguments supported below).

KwArgs:

  • color [='b'] (any matplotlib-supported color). The color of the markers.
  • marker [='o'] (any matplotlib-supported marker). The marker that will be used for each control profile.
  • markersize [=8.0] (float). The size of the marker.
  • mfc [='none'] (any matplotlib-supported color). The color of the marker face.
  • mec [=None] (any matplotlib-supported color). The color of the marker edge face.
  • mew [=1.0] (float). The weight of the marker edge.
netcontrolz.profile_heatmap(G, ...)[source]

Plots a set of control profiles as a heatmap on a triangular control profile plot. Each of the items specified can be either a control profile 3-tuple, 3-list, or zen.DiGraph (in which case the control profile of the graph will be computed and then plotted).

The resolution of the mesh can be controlled using num_steps. If no matplotlib color map name or color map is supplied (cmap), one will be generated using a gradient between white and color.

KwArgs:

  • num_steps [=15] (int). The resolution of the heatmap mesh.
  • cmap [=None] (colormap). The colormap that will be used when producing the heatmap.
  • color [='b'] (any matplotlib-supported color). Specify a color instead of a colormap for ease.
Returns:
A dictionary with boundaries for the individual regions being rendered in the heatmap.
netcontrolz.profile_heatmap_weighted(G, ...)[source]

Plots a weighted combination of control profiles as a heatmap on a triangular control profile plot. items is a list of other lists composed of: control profile 3-tuple, 3-list, or zen.DiGraph (in which case the control profile of the graph will be computed and then plotted). A weights parameter can be specified to weight the combination, typically used to combine multiple categories together in and equitable manner.

The resolution of the mesh can be controlled using num_steps. If no matplotlib color map name or color map is supplied (cmap), one will be generated using a gradient between white and color.

KwArgs:

  • num_steps [=15] (int). The resolution of the heatmap mesh.
  • cmap [=None] (colormap). The colormap that will be used when producing the heatmap.
  • color [='b'] (any matplotlib-supported color). Specify a color instead of a colormap for ease.
Returns:
A dictionary with boundaries for the individual regions being rendered in the heatmap.

Robustness of Network Controllability

Network controllability properties change as the graph is altered. An important class of network alterations includes random failures and attacks.

See also

Jijju Thomas, Supratim Ghosh, Deven Parek, Derek Ruths, Justin Ruths. Robustness of Network Controllability to Degree-Based Edge Attacks. Complex Networks & Their Applications V, 2016.

netcontrolz.edge_percolation(G, attack, ...)[source]

Computes robustness metrics of controllability for the directed network G according to the edge selection method indicated by attack.

See method edge_percolation_. The only difference is that the controls here are given as a list of tuples of node objects instead of node indices.

netcontrolz.edge_percolation_(G, attack, ...)[source]

Computes robustness metrics of controllability for the directed network G according to the edge selection method indicated by attack.

Args
  • attack indicates the type of edge selection method to use. Supported values of attacks include:
    • netcontrolz.EDGE_ATTACK_ININ_DEG (degree-based attack)
    • netcontrolz.EDGE_ATTACK_INOUT_DEG (degree-based attack)
    • netcontrolz.EDGE_ATTACK_OUTIN_DEG (degree-based attack)
    • netcontrolz.EDGE_ATTACK_OUTOUT_DEG (degree-based attack)
    • netcontrolz.EDGE_ATTACK_TOTAL_DEG (degree-based attack)
    • netcontrolz.ATTACK_RAND (random failure)
    • callable function which takes in a zen.DiGraph and returns the edge index that should be removed next

    For degree-based attacks, for example, INOUT ranks edges according to their source node’s IN-degree and their target node’s OUT-degree; OUTIN ranks edges according to their source node’s OUT-degree and their target node’s IN-degree; etc.

KwArgs:

  • controls[=None] (LIST_OF_TUPLES)

    • LIST_OF_TUPLES: Representing control nodes (indices) that are attached to the nodes in G e.g. [(1,),(3,)] represents two controls that are attached to node indices 1 and 3. When controls is not given (or None), a control set with minimal number of controls will be calculated and used.
  • frac_rm_edges [=0.5] (float). The fraction of edges to remove from the network. If num_steps does not divide this number of edges evenly, the actual fraction of edges removed may be slightly smaller than frac_rm_edges.

  • num_steps [=10] (int). The number of steps of percolation.

  • metrics (py:tuple). The metrics to calculate and return. The options are:
    • netcontrolz.CONTROL_ROBUSTNESS which measures the increase in the minimum number of controls required to control the network.
    • netcontrolz.REACHABILITY_ROBUSTNESS_FIXED which measures the decrease in the number of nodes controllable by a fixed set of controls.
    • netcontrolz.REACHABILITY_ROBUSTNESS_FREE which measures the decrease in the number of nodes controllable by a fixed number of controls.
Returns:
  • frac_edges_removed. The fraction of edges remaining after each percolation steps, length num_steps+1.
  • metrics_result. A dictionary containing the chosen metrics at the percolation steps, each item in the dictionary has length num_steps+1.