IDEAS home Printed from https://ideas.repec.org/a/wsi/acsxxx/v19y2016i03ns0219525916500065.html
   My bibliography  Save this article

Finding And Analyzing The Minimum Set Of Driver Nodes In Control Of Boolean Networks

Author

Listed:
  • WENPIN HOU

    (Department of Mathematics, The University of Hong Kong, Pokfulam Road, Hong Kong 999077, Hong Kong)

  • TAKEYUKI TAMURA

    (Bioinformatics Center, Institute for Chemical Research, Kyoto University, Kyoto 611-0011, Japan)

  • WAI-KI CHING

    (Department of Mathematics, The University of Hong Kong, Pokfulam Road, Hong Kong 999077, Hong Kong)

  • TATSUYA AKUTSU

    (Bioinformatics Center, Institute for Chemical Research, Kyoto University, Kyoto 611-0011, Japan)

Abstract

We study the minimum number of driver nodes control of which leads a Boolean network (BN) from an initial state to a target state in a specified number of time steps. We show that the problem is NP-hard and present an integer linear programming-based method that solves the problem exactly. We mathematically analyze the average size of the minimum set of driver nodes for random Boolean networks with bounded in-degree and with a small number of time steps. The results of computational experiments using randomly generated BNs show good agreements with theoretical analyses. A further examination in realistic BNs demonstrates the efficiency and generality of our theoretical analyses.

Suggested Citation

  • Wenpin Hou & Takeyuki Tamura & Wai-Ki Ching & Tatsuya Akutsu, 2016. "Finding And Analyzing The Minimum Set Of Driver Nodes In Control Of Boolean Networks," Advances in Complex Systems (ACS), World Scientific Publishing Co. Pte. Ltd., vol. 19(03), pages 1-32, May.
    • Handle: RePEc:wsi:acsxxx:v:19:y:2016:i:03:n:s0219525916500065
    DOI: 10.1142/S0219525916500065
    as

    Download full text from publisher

    File URL: http://www.worldscientific.com/doi/abs/10.1142/S0219525916500065
    Download Restriction: Access to full text is restricted to subscribers
    File URL: https://libkey.io/10.1142/S0219525916500065?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Hiroaki Kitano, 2002. "Computational systems biology," Nature, Nature, vol. 420(6912), pages 206-210, November.
    2. Yang-Yu Liu & Jean-Jacques Slotine & Albert-László Barabási, 2011. "Controllability of complex networks," Nature, Nature, vol. 473(7346), pages 167-173, May.
    3. Andrea Leibfried & Jennifer P. C. To & Wolfgang Busch & Sandra Stehling & Andreas Kehle & Monika Demar & Joseph J. Kieber & Jan U. Lohmann, 2005. "WUSCHEL controls meristem function by direct regulation of cytokinin-inducible response regulators," Nature, Nature, vol. 438(7071), pages 1172-1175, December.
    4. Pu, Cun-Lai & Pei, Wen-Jiang & Michaelson, Andrew, 2012. "Robustness analysis of network controllability," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(18), pages 4420-4425.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Chen, Shi-Ming & Xu, Yun-Fei & Nie, Sen, 2017. "Robustness of network controllability in cascading failure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 471(C), pages 536-539.
    2. Li, Xin-Feng & Lu, Zhe-Ming, 2016. "Optimizing the controllability of arbitrary networks with genetic algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 447(C), pages 422-433.
    3. Ding, Jin & Lu, Yong-Zai & Chu, Jian, 2013. "Studies on controllability of directed networks with extremal optimization," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(24), pages 6603-6615.
    4. Yin, Hongli & Zhang, Siying, 2016. "Minimum structural controllability problems of complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 443(C), pages 467-476.
    5. Li, Jian & Dueñas-Osorio, Leonardo & Chen, Changkun & Berryhill, Benjamin & Yazdani, Alireza, 2016. "Characterizing the topological and controllability features of U.S. power transmission networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 453(C), pages 84-98.
    6. Andreas Koulouris & Ioannis Katerelos & Theodore Tsekeris, 2013. "Multi-Equilibria Regulation Agent-Based Model of Opinion Dynamics in Social Networks," Interdisciplinary Description of Complex Systems - scientific journal, Croatian Interdisciplinary Society Provider Homepage: http://indecs.eu, vol. 11(1), pages 51-70.
    7. He, He & Yang, Bo & Hu, Xiaoming, 2016. "Exploring community structure in networks by consensus dynamics," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 450(C), pages 342-353.
    8. Ellinas, Christos & Allan, Neil & Johansson, Anders, 2016. "Project systemic risk: Application examples of a network model," International Journal of Production Economics, Elsevier, vol. 182(C), pages 50-62.
    9. Yang, Hyeonchae & Jung, Woo-Sung, 2016. "Structural efficiency to manipulate public research institution networks," Technological Forecasting and Social Change, Elsevier, vol. 110(C), pages 21-32.
    10. Meng, Tao & Duan, Gaopeng & Li, Aming & Wang, Long, 2023. "Control energy scaling for target control of complex networks," Chaos, Solitons & Fractals, Elsevier, vol. 167(C).
    11. Tao Jia & Robert F Spivey & Boleslaw Szymanski & Gyorgy Korniss, 2015. "An Analysis of the Matching Hypothesis in Networks," PLOS ONE, Public Library of Science, vol. 10(6), pages 1-12, June.
    12. Yang, Xu-Hua & Lou, Shun-Li & Chen, Guang & Chen, Sheng-Yong & Huang, Wei, 2013. "Scale-free networks via attaching to random neighbors," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(17), pages 3531-3536.
    13. Zhang, Rui & Wang, Xiaomeng & Cheng, Ming & Jia, Tao, 2019. "The evolution of network controllability in growing networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 520(C), pages 257-266.
    14. Wouter Vermeer & Otto Koppius & Peter Vervest, 2018. "The Radiation-Transmission-Reception (RTR) model of propagation: Implications for the effectiveness of network interventions," PLOS ONE, Public Library of Science, vol. 13(12), pages 1-21, December.
    15. Chandra, Yanto & Wilkinson, Ian F., 2017. "Firm internationalization from a network-centric complex-systems perspective," Journal of World Business, Elsevier, vol. 52(5), pages 691-701.
    16. Xizhe Zhang & Huaizhen Wang & Tianyang Lv, 2017. "Efficient target control of complex networks based on preferential matching," PLOS ONE, Public Library of Science, vol. 12(4), pages 1-10, April.
    17. Pang, Shao-Peng & Hao, Fei, 2018. "Effect of interaction strength on robustness of controlling edge dynamics in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 497(C), pages 246-257.
    18. Mika Gustafsson & Michael Hörnquist, 2010. "Gene Expression Prediction by Soft Integration and the Elastic Net—Best Performance of the DREAM3 Gene Expression Challenge," PLOS ONE, Public Library of Science, vol. 5(2), pages 1-8, February.
    19. Xiao, Guanping & Zheng, Zheng & Wang, Haoqin, 2017. "Evolution of Linux operating system network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 466(C), pages 249-258.
    20. Gennady Ougolnitsky & Olga Gorbaneva, 2022. "Sustainable Management in Active Networks," Mathematics, MDPI, vol. 10(16), pages 1-22, August.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wsi:acsxxx:v:19:y:2016:i:03:n:s0219525916500065. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Tai Tone Lim (email available below). General contact details of provider: http://www.worldscinet.com/acs/acs.shtml .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.