Network controllability: algorithmics and applications in medicine

The problem of controlling a dynamic network has a long history in control theory, with roots in a diversity of mathematical methods from complex analysis to topology, graph theory and computational complexity. The basic problem setup is that of a dynamical system represented as a directed graph, with nodes influencing each other’s dynamics. Control is sought over a given set of targets, in the sense of being able to change their configuration through external interventions on some well-chosen input nodes in the network, taking advantage of the network topology. We are interested in finding a minimal set of input nodes in the network such that the behavior of the target nodes may be changed arbitrarily through a well-chosen sequence of signals to the input nodes, cascaded throughout the network through its wiring. We focus on formalizations of this network controllability problem that maximize its applicability in biomedicine, including a specific set of targets to choose from (e.g., disease-specific essential genes), a specific set of inputs to choose from (e.g., drug targets), as well as non-linear network topologies. We discuss some of our recent results on the computational complexity of the structural targeted network controllability problem, some fast heuristics for it, and some applications in cancer medicine.