Sunday, 8 June 2014



Controllability and Observability of Complex Systems




YANG-YU LIU
Northeastern University
Center for Complex Network Research
Physics Department

VIDEO



OVERVIEW: The ultimate proof of our understanding of complex systems is reflected in our ability to control them. Although control theory offers mathematical tools for steering engineered systems towards a desired state, a framework to control complex systems is lacking. In this talk I will show that many dynamic properties of complex systems can studied be quantitatively, via a combination of tools from control theory, network science and statistical physics. In particular, I will focus on two dual concepts, i.e. controllability and observability, of general complex systems. Controllability concerns our ability to drive the system from any initial state to any final state within finite time, while observability concerns the possibility of deducing the system's internal state from observing its input-output behavior. I will show that by exploring the underlying network structure of complex systems one can determine the driver (or sensor) nodes that with time-dependent inputs (or measurements) will enable us to fully control (or observe) the whole system. 

READINGS:
    Liu, Y. Y., Slotine, J. J., & Barabasi, A. L. (2011). Controllability of complex networksNature473(7346), 167-173. 
    Zhao, C., Wang, W. X., Liu, Y. Y., & Slotine, J. J. (2014). 
Universal Symmetry in Complex Network ControlarXiv preprint arXiv:1403.0041.


31 comments:

  1. Il me semble que la description de la théorie de contrôle de M. Liu me fait beaucoup penser au système de transition d'états d'un système informatique.

    Actuellement, est-ce que le champ de l'ingénierie logicielle fait utilisation de la théorie de contrôle? Est-ce qu'il y a des études qui poussent vers cette direction? Est-ce qu'il existe des implémentations concrètes?

    ReplyDelete
    Replies
    1. Rapidement, j'ai trouvé un article scientifique qui discute de l'utilisation de la théorie de contrôle dans les applications logicielles; plus spécifiquement, il discute de son utilisation avec les interfaces graphiques :
      http://www.theserverside.com/feature/Applying-control-theory-concepts-in-software-applications

      Delete
    2. Translation:

      Network control theory is reminiscent of state transitions in a computational system: Has control theory been applied to software engineering? e.g. http://www.theserverside.com/feature/Applying-control-theory-concepts-in-software-applications

      Delete
    3. Thanks for sharing this interesting article. I have never thought about the potential application of control theory to software engineering. And I could not find any peer-reviewed journal articles discussing this point. It sounds a rather tough problem to me, because I/we don’t know how to write down a reasonable dynamic model for software engineering. If this is doable, then a bunch of control theoretical concepts can be applied, e.g., optimal control, adaptive control, etc.

      Delete
  2. Thank you for this talk. My question concerns the robustness of scale-free networks. Dr. Liu mentioned that the Web can be modeled as a scale-free network, which implies that it is very robust to random failure, but very fragile to targeted attacks. I was wondering if the techniques presented by Dr. Liu can tell us something about how to protect networks like the Web from targeted attacks. Perhaps something like adding redundant links? Is there an optimal quantity of redundant links in a system to prevent failure due to targeted attacks?

    ReplyDelete
    Replies
    1. This is a very interesting question. In the context of structural controllability, our approach can be used to classify links into critical, redundant, and ordinary. In engineered systems, this classification implies that in order to make controllability more robust, one can simply double (or triple) each critical link, formally making each of these links redundant and therefore ensuring there is no critical link in the controlled system.

      But your question is about attack prevention, rather than the robustness of structural controllability. Here is a fair recent paper “Attack Detection and Identification in Cyber-Physical Systems” written by Pasqualetti et al. They use control theoretical approach to address the attack detection problem. Hopefully, it can be used to protect WWW from targeted attacks.

      Also, this paper tried to address this question from the design prospective:
      http://link.springer.com/article/10.1140%2Fepjb%2Fe2004-00112-3
      (I am not sure if we are allowed to make this high-level or centralized decision to construct WWW. The construction of WWW sounds more like a self-organized or decentralized process.)

      Delete
    2. Thank for the response and reference, Dr. Liu!
      A follow-up question I have would be which of the two strategies you just outlined (increasing robustness with redundancy versus using control theoretical approaches to address attack detection) makes more sense? Maybe both should be used in tandem. Do you have a preference for one or the other?

      Delete
  3. Dear Yang-Yu, What a great presentation! I have a “little” question: If the semantics of a text can be thought as a dynamic building and transmission of a complex system, how do you think the theories that you presented are fruitful and sufficient to have a controllability and observability of this system?

    ReplyDelete
    Replies
    1. It is not a little question. :) I could not find any papers talking about the application of control theory to semantics. The word “control” used in linguistics (e.g., in this paper
      http://web.mit.edu/susi/www/research/files/CGSW15.pdf) seems to have a completely different meaning from the control notion used in control theory. I am not sure about the applicability of control theory to linguistics. (I wish I could be more optimistic. :( )

      Delete
  4. Can Controllability of Complex Networks be applied to the human brain? Some recent evidence describes scale-free organization of the human brain, in addition to small-world organization (http://www.ncbi.nlm.nih.gov/pubmed/18786642). Scale-free properties may help explain the simultaneous occurrence of a seeming robustness to insult and susceptibility to gross malfunction in the brain upon targeted insult to key connector hubs (e.g., the onset of Alzheimer's Disease when the posterior cingulate cortex, a key connector hub of the default mode network becomes compromised).

    In addition to applying control theory in the context of disease, perhaps it could also be applied to manipulate networks in the brain to influence cognition and behaviour. That would be exciting!

    ReplyDelete
    Replies
    1. Definitely. It is a fantastic research topic. An interesting paper “A network diffusion model of disease progression in dementia” written by Raj et al. inspired us to explore the potential application of control theory to disease progression. We are still working on that. No concrete results yet.

      Delete
    2. Hi Dr. Liu, I'd recommend getting in touch with Dr. Alan Evans who gave a talk on mapping the brain connectome on the first day of the conference. He mentioned to me a model of disease progression in dementia that his group is working on that includes a "clearance" term, providing his model with a more accurate picture of disease. Looking forward to your results! Could you give any more detail on how you apply control theory to disease progression in dementia? Are you using modelling a particular pharmacological agent?

      Delete
    3. This also has interesting implications for BCI/deep brain stimulation or even TMS in that, were we to be able to map specific areas in the brain that can act as sensor or control nodes, it would be possible to actively monitor electrical dynamics in the brain such that electrical stimulation could be applied to control nodes in order to shift the network from a pathological state to a more manageable one.

      Delete
  5. Dr. Liu’s discussed this type of networking in respect to biochemical reactions. Are these concepts also applicable to social networking? Are there ‘hub’ and ‘driver’ users on social media? Would this be a ‘dense and homogeneous’ network as all users are similar? Dr. Liu mentioned that dense homogeneous networks are the easiest to control. If so, what can we do with this knowledge?

    ReplyDelete
    Replies
    1. The linear dynamics we studied may be suitable for the consensus or agreement dynamics in multi- agent networks, e.g., social media. Hubs are nodes that have high degree (connectivity). Driver users can be identified using the maximum matching algorithm, provided that we know the structure of the social network and the structure does not vary over time. For dense and homogeneous networks with linear time-invariant dynamics, in principle we do need less driver nodes. But in reality, it may require lots of “energy” to fully control the system. FYI:
      http://journals.aps.org/prl/abstract/10.1103/PhysRevLett.108.218703

      Delete
  6. I did not know much about structural control theory and I found this talk very informative.
    You said hubs were the "Achilles heel" of scale-free networks. Is there anything we, as web scientists/network theorists, can do to prevent this? Or are scale-free networks powerful enough that we should ignore this weak point?

    ReplyDelete
    Replies
    1. That’s the price we need to pay. Scale-free networks are robust to random failure, but fragile to targeted attack. There is not much we can do. This paper tried to address this question from the design prospective:
      http://link.springer.com/article/10.1140%2Fepjb%2Fe2004-00112-3
      (But I am not sure if we are allowed to make this high-level or centralized decision to construct scale-free networks. Many networks are constructed in a self-organized or decentralized manner.)

      Delete
  7. Thank you YANG-YU LIU. You show me an example about a simple dynamic system. I would like to know more about cactus structure. It is possible to see it, in the last book, showed in the last slide?

    ReplyDelete
    Replies
    1. I didn’t show any books on structural control theory. :) But here is a nice review paper on structural control theory:
      “Generic properties and control of linear structured systems: a survey”
      Jean-Michel Diona, Christian Commaulta, Jacob van der Woudeb

      Delete
  8. I don’t know much about controllability theory and I am wondering what could be a concrete use or impact for this study?

    ReplyDelete
    Replies
    1. It reminds us that for linear dynamics, network structure plays a very important role in controlling the network. And many analytical results can be obtained. The linear dynamics we studied may be suitable for the consensus or agreement dynamics in multi-agent networks.

      Delete
  9. Using cactus structure to reduce a complexity of network its wonderful way to make it controllable. My question it’s about complexes networks that we do not know all the interaction between nodes, can we apply this reduction by ignoring unknown relations or do we have another way to do it !!

    ReplyDelete
    Replies
    1. This question is about how to infer the network structure. If you consider network structure itself (e.g., the edge presence/absence or edge weights) is a state variable, we can formalize the inference problem as an observability problem.
      This paper (http://arxiv.org/abs/1308.5261) has addressed this question in a very satisfactory manner.

      Delete
  10. Very enjoyable talk. I'm wondering if there is a way to connect some of the things from this talk to the previous talk about network dynamics?

    ReplyDelete
    Replies
    1. I'd wager Dr. Liu's works on controlability would give a priori constraints, which would limit the search space when trying to find suitable interventions to bring a dynamic system to a desired state.

      Delete
    2. e studied the algebraic observability of nonlinear (rational or polynomial) dynamic systems. For controllability of nonlinear dynamical systems, we don’t have concrete results yet. And I wonder if any general statements can be made about the impact of network structure on the nonlinear controllability of a general nonlinear dynamical systems.

      Delete
  11. The end of the lecture focused on directional aspects of complex networks. Could you apply this analysis to the concepts of top-down and bottom up processing. In the context of controllability and observability, where you you look to better understand the mind and its interaction with web technologies?

    ReplyDelete
    Replies
    1. That’s a tough question. If we have a very quantitative understanding of the dynamics of the interaction between the mind and the web technologies, then perhaps we can apply control theory.
      Also, fuzzy control theory might be potentially useful.
      FYI: http://www.site.uottawa.ca/~petriu/Fuzzy-tutor.PDF

      Delete
  12. I tried to be concise with my question but have perhaps neglected the interdisciplinary nature of it. Perhaps these resources will help your formulate an opinion. The article's is 10 years old and the video is from March this year.

    Raz, A. (2004). Anatomy of Attentional Networks

    http://www.ted.com/talks/david_chalmers_how_do_you_explain_consciousness

    ReplyDelete
  13. Thank you for an interesting talk. It was interesting to see that control ability and observability depend primarily on topological characteristic of a network. I wonder about cases where the network is not controllable can you device algorithms that will indicate the minimal changes in the network topology that are needed to achive control ability.

    ReplyDelete