(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 graphG
(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 graphG
; also equivalent to the difference between the number of nodes in the network and the number of dilations, see methodnetcontrolz.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 graphG
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 nonbud 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 graphG
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 graphG
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. Args: see method

netcontrolz.
build_cacti_fixed_controls_
(G, fixed_ctls[, with_cycles=False])[source]¶ This method constructs
Cacti
for a given directed graphG
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 inG
.
 KwArgs:
randomize[=False]
(Boolean
). Indicates whether the matching should be randomized.with_cycles[=False]
(Boolean
). Indicates whether cycles not reachable from thefixed_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 graphG
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. Args: see method

netcontrolz.
build_cacti_from_matching_
(G, fixed_ctls, matching[, roots=None])[source]¶ This method constructs
Cacti
for a given directed graphG
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 inG
. 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 maximummatching 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.

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.


class
netcontrolz.cacti.
Stem
[source]¶ An instance of
Stem
represents a single stem (with reference to any associated buds) in a cacti structure.

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).
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.

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), 13731376 (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, externaldilation controls, and internaldilation controls. Unnormalized, 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 3tuple, 3list, orzen.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 matplotlibsupported color). The color of the markers.marker [='o']
(any matplotlibsupported marker). The marker that will be used for each control profile.markersize [=8.0]
(float
). The size of the marker.mfc [='none']
(any matplotlibsupported color). The color of the marker face.mec [=None]
(any matplotlibsupported 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 3tuple, 3list, orzen.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 matplotlibsupported 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 3tuple, 3list, orzen.DiGraph
(in which case the control profile of the graph will be computed and then plotted). Aweights
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 matplotlibsupported 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 DegreeBased 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 byattack
.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 byattack
. Args
attack
indicates the type of edge selection method to use. Supported values ofattacks
include:netcontrolz.EDGE_ATTACK_ININ_DEG
(degreebased attack)netcontrolz.EDGE_ATTACK_INOUT_DEG
(degreebased attack)netcontrolz.EDGE_ATTACK_OUTIN_DEG
(degreebased attack)netcontrolz.EDGE_ATTACK_OUTOUT_DEG
(degreebased attack)netcontrolz.EDGE_ATTACK_TOTAL_DEG
(degreebased 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 degreebased attacks, for example, INOUT ranks edges according to their source node’s INdegree and their target node’s OUTdegree; OUTIN ranks edges according to their source node’s OUTdegree and their target node’s INdegree; 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. Ifnum_steps
does not divide this number of edges evenly, the actual fraction of edges removed may be slightly smaller thanfrac_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, lengthnum_steps+1
.metrics_result
. A dictionary containing the chosenmetrics
at the percolation steps, each item in the dictionary has lengthnum_steps+1
.