Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Structural Target Controllabil...

Structural Target Controllability of Linear Networks

Eugen Czeizler, Kai-Chiu Wu, Cristian Gratie, Krishna Kanhaiya, Ion Petre, Structural Target Controllability of Linear Networks. IEEE-ACM Transactions on Computational Biology and Bioinformatics 15(4), 1217–1228, 2018.

http://dx.doi.org/10.1109/TCBB.2018.2797271

Abstract:

Computational analysis of the structure of intra-cellular molecular interaction networks can suggest novel therapeutic approaches for systemic diseases like cancer. Recent research in the area of network science has shown that network control theory can be a powerful tool in the understanding and manipulation of such bio-medical networks. In 2011, Liu et al. developed a polynomial time algorithm computing the size of the minimal set of nodes controlling a linear network. In 2014, Gao et al. generalized the problem for target control, minimizing the set of nodes controlling a target within a linear network. The authors developed a Greedy approximation algorithm while leaving open the complexity of the optimization problem. We prove here that the target controllability problem is NP-hard in all practical setups, i.e., when the control power of any individual input is bounded by some constant. We also show that the algorithm provided by Gao et al. fails to provide a valid solution in some special cases, and an additional validation step is required. We fix and improve their algorithm using several heuristics, obtaining in the end an up to 10-fold decrease in running time and also a decrease in the size of solutions.

BibTeX entry:

@ARTICLE{jCzWuGrKaPe18a,
  title = {Structural Target Controllability of Linear Networks},
  author = {Czeizler, Eugen and Wu, Kai-Chiu and Gratie, Cristian and Kanhaiya, Krishna and Petre, Ion},
  journal = {IEEE-ACM Transactions on Computational Biology and Bioinformatics},
  volume = {15},
  number = {4},
  publisher = {IEEE},
  pages = {1217–1228},
  year = {2018},
  keywords = {Controllability, Drugs, Linear systems, Diseases, Optimization, Heuristic algorithms, Approximation algorithms},
  ISSN = {1545-5963},
}

Belongs to TUCS Research Unit(s): Computational Biomodeling Laboratory (Combio Lab)

Publication Forum rating of this publication: level 2

Edit publication