
Community Forum : Model Analysis SIG 






Subject : Complexity of finding all (major) feedback loops in a model..
09/24/2018 11:06:03 AM



Guido W. Reichert 

Posts: 6
Location: 



Hi Everyone,
As System Dynamicists we like to say "Structure drives behavior" and by this tenet we more precisely mean that the structure of interconnected stocks and flows will explain dynamic behavior. In short: It is major feedback loops we will look for.
That got me wandering about the problem of finding all feedback loops in a System Dynamics model and the computational complexity of this task.
Wouldn't finding all feedback loops in a model be equivalent to the following problem:
 Turn the SD model into a graph by making its stocks be the nodes and by inserting a directed edge between any two nodes i and j whenever there is a path from i to j.
 For each possible subgraph (e.g. a set of nodes and the edges that contain just these nodes) decide whether there exists a Hamiltonian Cycle and find it.
 The list of all discovered cycles would be the complete list of major feedback loops of the model.
If this were the case, wouldn't the problem of finding all major feedback loops be NPcomplete by necessity, since finding a Hamiltonion Cycle in a graph is an NPcompleteproblem? And if so, will feddback loops quickly become intractable for bigger models? 






Subject : Re:Complexity of finding all (major) feedback loops in a model..
09/26/2018 08:05:25 PM



Dr. John Hayward 

Posts: 5
Location: 



Hi Guido
You raise a really interesting point about what structure is best to use to understand behaviour. I agree I think for most people this is the "major" loops. I wonder if there may be some ambiguity about the concept of "major". I have looked at loop dominance in a number of models and it is often firstorder loops that have the biggest influence on curvature. I am not sure people would always regard these loops, especially balancing/draining processes, as "major".
I think you are correct about the graph theory approach to finding all the loops. The 2012 paper by Christian Kampmann (ref below) uses directed graphs to enumerate loops and in particular to extract an independent loop set. The trouble is there may be more than one independent loop set. We (Hayward & Roach, 2017) considered the inter stock connections rather than the loops they form as the fundamental structure to explain behaviour as inter stock links are always unique, unlike feedback loops.
Reducing an SD model to a directed graph is interesting. If all the model elements are included, i.e. stocks, flows and converters, then this is a directed graph (digraph) in the narrow sense used in graph theory as there will be no multiple edges between elements or edges from an element to itself. But if only the stocks are used this is no longer a digraph as there may be multiple edges and edges from a stock to itself. Some people call these multidigraphs, but names vary according to the application  a bit confusing. I don't this should affect the search strategy you selected. I suspect this approach has been investigated in control theory and maybe biological systems, see refs below. It would be worth a look.
Thank you for your message on the noticeboard
best wishes
John
References:
Kampmann CE. 2012. Feedback loop gains and system behaviour (1996). System Dynamics Review 28(4): 370–395.
Hayward J and Roach P.A. Newton's laws as an interpretive framework in system dynamics. System Dynamics Review, 33(3–4):183–218, 2017.
You might like to check out:
O. Cinquin and J. Demongeot. Roles of positive and negative feedback in biological systems. Comptes rendus biologies, 325(11):1085–1095, 2002.
Finding the positive feedback loops underlying multistationarity
Elisenda Feliu, Carsten Wiuf, 2014 arXiv:1410.7642v1 [qbio.MN] 28 Oct 2014 






Subject : Re:Complexity of finding all (major) feedback loops in a model..
10/17/2018 10:13:48 AM



Guido W. Reichert 

Posts: 6
Location: 



Hello John,
Thank you for your reply and the references you have given, which I will look at. I only recently found some time to think about your answer and I cannot quite follow you with regard to the reduced system (e.g. there are only stocks and functions thereof) being a multigraph in the sense that by eleminating converters and constants we end up having a graph where there can be multiple arcs from a source node to and end node.
That would imply that there are different polarities to consider which cannot be true, can it? In other words, that multigraph should by "expanding all functions" (e.g. "flattening") always be reducible to a graph where there can only be two edges at most between any pair of vertices/nodes.
We should be able to provide one function for each stock in which its causes (stocks appearing on the right hand side of the equation) may appear multiple times, but where the polarity at any given point in time will be unambiguous with regard to any such input. Thus we should need imo only one arc for any stock appearing on the right hand side of an (ODE) equation defining a stock.
Such reductions are mentioned at least for linear signal flow graphs.
It is interesting to consider the upper boundary for the number of feedback loops in a reduced system dynamics model:
It is well known that there are (n1)! Hamiltonian Cycles in a complete graph with n nodes if we consider A>B>C>A different from the reverse cycle (as we usually do in System Dynamics).
From this it follows that the total number of feedback loops in a complete graph is given by
Sum[ Binomial[n,k] * (k1)!, {k, 1, n} ]
to use Mathematicanotation. That number grows as fast as n!.( There are of course n minor feedback loops so that we can simply subtract n to arrive at the maximum number of major feedback loops )
Even though we will of course have no complete graphs the challange of identifying feedback loops in bigger models (and then using them to calculate elasticities?) seems daunting to me.
Best regards,
Guido 






Subject : Re:Complexity of finding all (major) feedback loops in a model..
10/19/2018 10:10:49 AM



Guido W. Reichert 

Posts: 6
Location: 



The article by Christian E. Kampmann (1996/2012) is "spot on" and does answer my question rather clearly. As I understand its main points and to keep this for reference:
 While the number of feedback loops in the reduced graph (i.e. any node in the graph will be a stock) does indeed grow like n! we only have to care for strongly connected components (SCC) of that graph and the set of independent loops.
 There exist algorithms that will identify SCC within a graph in linear time (e.g. O(number of vertices + number of edges)), for example Kosaraju's algorithm, Tarjan's algorithm, and the Pathbased strong component algorithm.

Last Edited On: 11/20/2018 02:57:03 PM By Guido W. Reichert 






Subject : Re:Complexity of finding all (major) feedback loops in a model..
11/19/2018 06:00:57 PM



JeanJacques Lauble 

Posts: 8
Location: 



Hi Guido and John
Practically, I consider feed back loops only with extremely simple models.
Apart from that, I do not study them for the following reasons.
The set of causalities does not explain fully the behaviour of a system. One has to consider the nature of the causalities (the equations) and the value of the parameters. It is easy to change considerably the behaviour of a system, by changing the values of the parameters or changing the equations. Then for me, it is true that the causal structure influences the behaviour, but partially and in a not very well defined way. I think that the set of causality explains the mental representation of a problem and it is useful for that. And as the mental representation of a problem may change with every body, models should include structural parameters that reflect these possible changes. I am then interested in the causal structure called CLD by some people, but I do not try generally to study the set of feed back loops that are generally too many (some of my models have 1000 of loops). Another problem rarely mentioned is the fact that many loops are subscripted and logically when considering individual feed back loops, one should not use subscripted variables.
How must one consider a subscripted feed back loop?
Then I generally do not study feed back loops, because there are too many of them, it ignores the nature of the causalities (the equations), the values of the parameters and the fact that many feed back loops are subscripted.
But the set of causalities (the CLD) is interesting because it represents well the modeller's qualitative mental representation of the problem.
Sorry I do not see the utility of going into mathematical stuff like oriented graphs etc…
Regards.
JJ 






Subject : Re:Complexity of finding all (major) feedback loops in a model..
11/20/2018 03:33:11 PM



Guido W. Reichert 

Posts: 6
Location: 



Hi JJ,
The number of loops for a model can grow as fast a faculty which was what started this conversation: Can all feedback loops really be identified in reasonable time (e.g. polynomial time)? Will it be sufficiently "practical" (or useful) to know about all loops to deduce behavior from this structural knowledge?
To answer your question about a subscripted model: It clearly has to be "flattened", e.g. the model has to be considered as if each stock had been named "stockName_i_j_k" instead of "stockName[i,j,k]".
You mention that your models have 1000 and more loops  but how do you know? In Vensim I will have to select a variable (say a stock) and then the number of loops and the variables contained within them are displayed in what is called the "loopstool". But there is no tool I know of that will give you all the loops for the model, e.g. eliminating redundancies from the union of all loopstoolreports.
Probabilistic Graphical Models, for example, show how graphtheory (GT) helps to tackle complicated joint probability models; why should graphtheory not also be helpful in analyzing SDmodels which can rather naturally be represented as graphs as well?
Kampmann's paper shows that GT does help because we only need to look at strongly connected components (a concept from graph theory)  greatly reducing the complexity of the analytical task.
Certainly, I have so far not used graphrepresentation other than for finding all loops in a model and for "bragging" about the complexity of a model  something I should not be proud of... ;)
I am also not yet convinced that loop gains and partition metrics are really helpful for my daily work  but it is the job of academics to drive this further. "Utility" and "Usefulness" must never risk to be too shortsighted concepts.
Best regards,
Guido 






Subject : Re:Complexity of finding all (major) feedback loops in a model..
11/20/2018 04:27:57 PM



Dr. John Hayward 

Posts: 5
Location: 



Hi Guido
I thought you would find the Kampmann paper interesting. It is a mine of information.
1. Reduced system. By this I mean the differential equation form of the system dynamics model. For example, look in Hayward & Roach 2017. There we have an inventory workforce system with just two stocks. The stockflow model, fig 14, has 11 equations, including all converters. If this were expressed as a graph it would be a standard directed graph, where the stocks, flows and converters would be nodes, no multiple edges and no edges from a node to itself – tautologous. But the system is only order 2, and using substitution, it can be written as two differential equations, equations 13 and 14 where the edges are labelled. These two stocks would be the only two nodes in a reduced system. Now a node can have an edge to itself, e.g. that of workforce represents the first order balancing loop. It is the network structure. of this loop system that determines behaviour. If I am still not making sense, email me (my email is on the paper Hayward & Roach) and I will try and explain with diagrams. We called it a reduced system as it lost the information about the converters, and thus model assumptions. The polarities of the links are still fixed in this format as, unlike standard differential equations, we label the pathways that came via different converters, thus there is no danger of pathways with different polarities being combined into a single pathway where polarities can change.
2. You refer to major loops and minor loops. Could you give a definition of what you mean by major and minor loops? Thank you.
3. It is certainly true that the number of possible loops expands rapidly – but I think there may be some results that enable us to extract system behaviour information out of even large systems. See the next item (4)
Hi JJ
4. I agree that all the feedback loops/causalities do not fully describe system behaviour, that their use is less helpful as system size and complexity grows. However, results from graph theory may allow feedback loops to give insight into the structure behaviour relationship even in large systems. The graph theory approach to feedback loops is used in cell biology. In this research domain, they often talk about Thomas’s conjectures. Here are two:
a. The presence of a positive feedback loop is a necessary condition for multistationarity (multiple stable equilibria) Gouzé (1998)
b. A negative loop is a necessary condition for stable periodic behaviour Gouzé (1998)
Positive is reinforcing, negative is balancing. I think both conjectures are fully proved. Thus if an SD model has no reinforcing loop, then there would at most one stable equilibrium state. Thus although the knowledge of loops has only given a partial insight into behaviour they are important insights. These two conjectures are important in cell biology because multistationarity and stable periods have physical significance. My feeling is there are other results such as these, provable from graph theory, that could be relevant to SD modellers. I am not aware of anyone who has tackled this. It would help people even with a large number of loops.
Hope some of the above is of help
John
Hayward, J. and Roach, P.A., 2017. Newton's laws as an interpretive framework in system dynamics. System Dynamics Review, 33(34), pp.183218.
Gouzé, J.L., 1998. Positive and negative circuits in dynamical systems. Journal of Biological Systems, 6(01), pp.1115. 






Subject : Re:Complexity of finding all (major) feedback loops in a model..
11/21/2018 10:19:43 AM



Guido W. Reichert 

Posts: 6
Location: 



Hi John,
Thank you very much for putting up some effort to provide more clarity. I will come back once I will find a bit more time to follow up on this topic.
The terms "major" and "minor" feedback loop are common in System Dynamics and Control Engineering as I just convinced myself using a well known search engine. Prominently, Mohammad Mojtahedzadeh (2008) uses these very terms in his paper "Do parallel lines meet? How can pathway participation metrics and eigenvalue analysis produce similar results?" in System Dynamics Review, 24(4), pp. 451478.
Mojtahedzadeh uses the terms as I remember them from courses at Worcester Polytechnic Institute:
A minor feedback loop will contain exactly one stock.
A major feedback loop will contain at least two stocks.
Hope that helps
Guido 
Last Edited On: 11/21/2018 05:20:23 AM By Guido W. Reichert 






Subject : Re:Complexity of finding all (major) feedback loops in a model..
11/22/2018 09:19:26 AM



JeanJacques Lauble 

Posts: 8
Location: 



Hi Guido
I can calculate the number of 'subscripted loops' by starting first with one level, something that Vensim can do. From that list I sort the loops that go through other levels and I calculate the number of loops that have only one level, that first level.
I go to the next level and I take out of its list the loops that were in the first level sorted groups already so as to have only loops that do not include the first level. And I start the process again, grouping the levels that are included and adding the loops that go through the first and second level only etc..
Of course this can be rather tedious.
But as my models are generally rather heavily subscripted, it done not even work in that case.
Then to make an evaluation, I do it rather intuitively as it does not have an impact on my capacity to analyse a model.
In fact I eliminate step by step all the redundancies you were talking about.
If I flatten my loops, I will get millions of loops, something that makes feed back loops study still less useful.
The problem with SD, is that it is very easy to build big untested models, much more less easy to build big tested models, and much more difficult to analyse big models even fully tested.
This is why there are plenty of big models full of bugs, rare big models fully tested, and even more rare big fully tested models well understood by the decision makers and useful.
This is why a place in the SDS where models could be criticised anonymously (beware of Big Brother) as you suggested could be extremely useful.
Best regards.
JJ
Hi John.
I do not contest the usefulness of research in SD and in general.
I have just with the years, found out that the Vensim tools that I use are sufficient for my type of problems, and that the problem is for me to make the size of my models adapted to my capacity and my available time and after that to take that time to use and analyse them mainly using qualitative and common sense thinking, something that is much more easy to talk about than to do effectively.
I have too found out that there is a gap between the sophistication of many SD studies and the extremely bad level of most published SD models where people do not need that sophistication but just to apply very basic and simple SD principles, something that would already do a lot of good for the image of SD.
Then your remarks may be useful for someone engaged into research but unfortunately not for me, being essentially concerned with practical problems.
I know that you are too interested in agent based modelling, does that field suffer from the same problems than SD?
Best regards.
JJ 
Last Edited On: 11/25/2018 09:31:09 AM By JeanJacques Lauble 






Subject : Re:Complexity of finding all (major) feedback loops in a model..
12/09/2018 05:58:05 PM



Dr. John Hayward 

Posts: 5
Location: 



Hi Guido
Thanks for the info on major and minor loops. It is Mohamed Mojtahedzadeh' 2004 paper on Digest. I had read this, so I should have remembered this. I guess I would prefer to give the order of the loop as secondorder loops have different behaviour to third order etc, even though they are all classed as major. But I am coming at this from a different perspective  forces rather than feedback. Again thank you for this
John 






Subject : Re:Complexity of finding all (major) feedback loops in a model..
12/09/2018 06:09:49 PM



Dr. John Hayward 

Posts: 5
Location: 



Hi JJ
You said > "I know that you are too interested in agent based modelling, does that field suffer from the same problems than SD?"
I am really an expert on agentbased (ABM). I used to teach basic ABM using Netlogo and a former research student had a paper, with me, using a more analytical ABM approach  just out in Physica A. My frustration with ABM is the inability to see the model, compared with SD (stocks and flows) or differential equations. Some people present code, some transition diagrams. But there does not seem to be any structural diagrams or notation that would show the causal connections between agent, its neighbours, and its global environment. I have models where there is clearly feedback within the agent, between neighbours, and into the environment and back. I wish I could think of an easy way to express this in a diagram!
John 






Subject : Re:Complexity of finding all (major) feedback loops in a model..
12/10/2018 06:29:41 AM



JeanJacques Lauble 

Posts: 8
Location: 



Hi John.
My question was about the general success of AB as a tool to solve problems, compared to the low success of SD.
I studied AB with Railsback book and stopped in the middle of it, after realizing that I could do the same job with Vensim DSS than Netlogo. I tried too Anylogic but found it too complex and especially too slow.
I practically do not rely anymore on specific paradigms but try to build credible, robust and implementable policies taking into consideration my own experience, available time,tools and problems at hand, working towards possible solutions and avoiding to dream about theoretic ones.
Best regards.
JJ 






Subject : Re:Complexity of finding all (major) feedback loops in a model..
12/10/2018 08:45:06 AM



Dr. John Hayward 

Posts: 5
Location: 



Hi JJ
My response to that may be related to my early comment about the inability to see the model structure in AB. I don't hear many practitioners talking about AB as an approach. Epidemiological modelling uses many quantitative methods including SD, differential equations and stochastic methods, but I can't say I have seen much AB, except to illustrate the effects of networks. I think the Anylogic/netlogo approach is too opaque to inspire confidence. However many practitioners do not publish. People like Google and Facebook must have network models for their marketing strategies  and this is a form of AB  but they would not be in the public domain. Just had a sift around on the internet and one author highlights the difficulties of verification and validation as a barrier to the uptake of AB.
I can understand why anyone who wants practical solutions to problems will not want to tie themselves to one paradigm. Academics have to publish papers and that limits approach that is taken.
I am not sure I have been of much help  sorry
John
John 






Subject : Re:Complexity of finding all (major) feedback loops in a model..
12/11/2018 09:44:13 AM



JeanJacques Lauble 

Posts: 8
Location: 



Hi John
You have not to be sorry. Exchanging ideas may always help.
And in these circumstances they made me understand, one of the big difference in the way I am working now and the way how most system dynamicist's work and how I was working in the past.
It is related to the level of understanding needed if one wants to solve a problem.
The traditional SD method is based on causality and wants to understand the root causes of everything expecting a feed back loop that will prevent the endless search of the final root cause.
It can then represent the studied world with a set of causes included in feedbacks, leaving outside from the causes all the rest of the world that can too influence the system studied at the condition that there is no feedback between the outside exogenous world and the endogenous one, or the feedback is insignificant.
This rather academic representation is very elegant and attracting, but has lots of drawbacks.
It generates very easily huge models not verifiable or usable, because the search of the causes does not finish with a feedback or there is no boundary where the system studied leaves endogenous explained causes and exogenous unexplained ones without feedback loops between them or sufficiently week ones.
Even if there is such a solution, the modeller has still to generate the behaviour of the exogenous world that influences the endogenous one and verify its compatibility.
This world view is then strongly based on the belief that good policies are dependant on good understanding.
I have with the time strongly modified this point of view.
I think that good decisions come with the quality of the policies and their credibility, independently from the level of understanding of the decision maker.
To resume, the future is made out of our decisions and not from our thinking.
And practically, when I make a model, I ask from it to deliver credible policies.
And anyhow most of my models are too complex to be globally understood.
I can verify the credibility of the model using the reality checks of Vensim or the likes or trying to understand from the model what can be understood partially by extracting generally smaller models from it that can be fully and deeply understood (not more that 3 or 4 structural parameters and 3 or 4 policy parameters with preferably not more than 3 feedback levels and no subscripting).
And I may spend a lot of time doing such a study with even a small model.
But I will do it only if I need it.
I can too suppress hundreds of equations that explain lots of things that do not need to be explained by simple lookup tables if I judge that it does the job, precisely enough.
So for me it is the credibility that counts and not the understanding, even if a certain level of understanding may help more or less.
This point of view permits more creativity and frees action from the necessity of understanding everything. It is oriented towards people who have to act.
I do not expect a lot of understanding from a community mostly interested by theory, but wanted to suggest some other paths, especially with the low practical success of SD, lasting now for more than 60 years.
I explained that because you complained about the low level of understanding of AB. But in SD, excepted for very small models, the problem is the same.
Best regards.
JJ 






Subject : Re:Complexity of finding all (major) feedback loops in a model..
12/27/2018 11:30:17 AM



Martin Schaffernicht 

Posts: 13
Location: 



Hi,
sorry to come late, and I know the discussion has moved towards AM, but as far as hierarchies of loops are concerned, I wondered if you have looked into the following article:
Oliva, Rogelio, 2004. Model structure analysis through graph theory: partition heuristics and feedback structure decomposition, System Dynamics Review Vol. 20, No. 4, (Winter 2004): 313–336
Rogelio took up Erik Kampman's "independent loop set" and developed an algorithm to detect a "shortest independent loop set".
Best greetings,
Martin Schaffernicht 




