John Baez
Diagrams

Skip the Navigation Links | Home Page | All Pages | Recently Revised | Authors | Feeds | Export |

Abstract

This is an annotated list of references on diagrammatic notations for networks, compiled by John Baez and Jacob Biamonte.

Introduction

Network theory, and the use of diagrams, have emerged independently in many fields of science. There should be a mathematical theory underlying the use of networks in all these disciplines. Such a theory could expose important relations between seemingly different subjects. A unified mathematical language of networks could provide mappings from one network model into another, and hence provide interoperability between—for example—ecological and chemical reactions networks, field theories, analog electrical circuits and tensor networks. Techniques and simulation software developed in one field could then be applied in other fields.

Our goal here is simply to collect and briefly explain some references on various diagrammatic notations for networks. For the most part we will not include references that are already covered here:

We prefer instead to focus on references from communities that are not yet already in close contact with pure mathematicians, especially category theorists. These other communities are doing work that still needs to be integrated with category theory.

Related blog articles

Contents

Tensor networks

‘Tensor networks’ are very close to the well-understood aspects of diagrammatic mathematics discussed in my review articles above. They are spin networks for the trivial group. However they are applied in a different way, for example to describe states of multi-part quantum systems. See for example this post on the nCafe about Jacob Biamonte’s paper.

  • Biamonte, Clark and Jaksch, Categorical Tensor Network States, preprint 2010. arXiv:1012.0531.

Tensor network states have a long history, with many independent tracks of research arriving at related ideas. While this article makes no attempt to outline the history of this subject, it is interesting to note that the basic idea of using products of matrices as an effective and compact way to describe physical systems arose in the field of statistical physics as early as 1941!

  • H.A. Kramers and G.H. Wannier, Phys. Rev. 60 (1941), 263-276.

In recent times, these ideas seem to have been rediscovered several times. The theory was improved by researchers working in the field of quantum information science. This new approach has explained the computational efficiency of many established numerical simulation methods.

The basic idea is to consider finite products of matrices (with the internal entries representing state vectors) as a description for quantum states and operators. This enables one to recover a complex quantum state by simply tracing over this product of matrices.

Tensor networks to describe time-independent quantum states and operators are broken into the following classes:

  • Matrix Product States (MPS) - called Tensor Product States in some papers.
  • Projected Entangled Pair States (PEPS).
  • Multiscale Entanglement Renormalization Ansatz (MERA).

Time dependence can be handled in several ways, the most notable being Time-Evolving Block Decimation (TEBD), a method based on MPS which allows for the simulation of quantum dynamics.

Here are some review articles on tensor network states:

You can see more papers on tensor network states here:

Electrical circuits

If you look at these, what do you see? Circuit diagrams, or morphisms in a symmetric monoidal category?

amplifier with bass boost
Top: 10-watt amplifier with bass boost.
Bottom: ±16 Volt power supply with power-on indicator light.

In fact they are both! To learn how electrical circuit diagrams are morphisms in a symmetric monoidal category, read This Week’s Finds starting around week288 and also my paper Electrical Circuits. This paper only covers circuits made of linear resistors, the simplest kind. As explained in This Week’s Finds, this should blossom out into a full-fledged theory that includes the theory of ‘bond graphs’.

In addition to categories where circuits are morphisms, there are categories where circuits are objects. See this paper (not easy to obtain yet):

  • Larry Harper, Morphisms for resistive electrical circuits.

  • Duality is an important concept in electrical circuits. See Dual Circuit.

  • There is a nice correspondence between Markov Chains and Circuits. See Random Walks and Electrical Networks.

  • The present page lists references about analog circuits. See Switching Networks for references related to digital circuits, as well as the connection between such networks and tensor networks.

Bond graphs

For bond graphs see This Week’s Finds starting in week289. These were invented by Henry Painter, an engineer at MIT:

Here is an example from his original work:

Paynter's bond graph of a hydroelectric plant

Bond graphs were further developed by Jean Thoma:

  • Jean U. Thoma, Introduction to Bond Graphs and Their Applications, Pergamon Press, Oxford, 1975.

There is by now a vast literature:

Here is an online course:

Control theory

The subject of bond graphs overlaps with control theory, a subject does not in itself require use of diagrammatic techniques, but focuses on ‘open systems’, which can be glued together in a way that’s nicely clarified by diagrams:

  • Bernard Brogliato, Rogelio Lozano, Bernhard Maschke and Olav Egeland, Dissipative Systems Analysis and Control: Theory and Applications, 2nd edition, Springer, Berlin, 2007.

‘Port-controlled Hamiltonian systems’ are Hamiltonian systems where certain pairs of variables, corresponding to ‘ports’, can be adjusted from outside:

  • B. M. Maschke and A. J. van der Schaft, Port controlled Hamiltonian systems: modeling origins and system theoretic properties, in Proceedings of the 2nd IFAC Symp. on Nonlinear Control Systems Design, NOLCOS’92 (1992), pp. 282-288,

  • B. M. Maschke and A. J. van der Schaft, The Hamiltonian formulation of energy conserving physical systems with ports, Archiv fur Elektronik und Ubertragungstechnik 49 (1995), 362-371.

  • A. J. van der Schaft, L2-gain and Passivity Techniques in Nonlinear Control, 2nd edition, Springer, Berlin, 2000.

Jan Willems’ work is particularly ripe for a category-theoretic treatment:

Stramigioli’s thesis has some bond graphs in the appendix:

  • Stefano Stramigioli, Modeling and IPC control of Interactive Mechanical Systems: a Coordinate-Free Approach, Lectures Notes in Control and Information Sciences 266, Springer, Berlin, 2001.

Stramigioli has written a number of books on port-controlled Hamiltonian systems:

  • Cristian Secchi, Stefano Stramigioli, and Cesare Fantuzzi, Control of Interactive Robotic Interfaces: A Port-Hamiltonian Approach, Springer Tracts in Advanced Robotics. 29, 2007.

  • Vincent Duindam, Alessandro Macchelli, Stefano Stramigioli, and Herman Bruyninckx, Modeling and Control of Complex Physical Systems: The Port-Hamiltonian Approach, 2009.

  • Vincent Duindam and Stefano Stramigioli, Modeling and Control for Efficient Bipedal Walking Robots: A Port-Based Approach, Springer Tracts in Advanced Robotics, 2009.

Jenny Santoso has recommended a number of other references. A recent general reference:

  • Bernard Brogliato, Rogelio Lozano, Bernhard Maschke, and Olav Egeland, Dissipative Systems Analysis and Control: Theory and Applications, Communications and Control Engineering, 2nd edition, 2010.

She also pointed out a literature on control theory using ideas from differential geometry (‘flatness’) and module theory. Some of this is touched on in the review papers by Willems, but also see these:

  • M. Fliess, J. Lévine, Ph. Martin, and P. Rouchon, Sur les systèmes non linéaires différentiellement plats, C. R. Acad. Sci. Paris Sér. I Math. 315 (1992), 619–624.

  • M. Fliess, J. Lévine, Ph. Martin, and P. Rouchon. On differentially flat nonlinear systems, in Proc. IFAC-Symposium NOLCOS ‘92, Bordeaux, 1992, pp. 408–412.

  • M. Fliess, J. Lévine, Ph. Martin, and P. Rouchon, Flatness and defect of nonlinear systems: introductory theory and examples, Int. J. Control 61 (1995), 1327–1361.

  • M. Fliess, J. Lévine, Ph. Martin, and P. Rouchon, A Lie-Bäcklund approach to equivalence and flatness of nonlinear systems, IEEE Trans. Automatic Control 44 (1999), 922–937.

  • Joachim Rudolph, Beiträge zur Flachheitsbasierten Folgeregelung Linearer und Nichtlinearer Systeme Endlicher und Unendlicher Dimension, Shaker Verlag, 2003.

or shorter versions in English:

  • Joachim Rudolph, Flatness Based Control of Distributed Parameter Systems, Shaker Verlag, 2003.

  • Joachim Rudolph, J. Winkler, F. Woittennek, Flatness Based Control of Distributed Parameter Systems: Examples and Computer Exercises from Various Technological Domains, Shaker Verlag](http://www.shaker.de/de/content/catalogue/index.asp?lang=de&ID=8&ISBN=978-3-8322-1195-0), 2003.

Also see:

Pierre Rouchon has many papers on flatness, and see also:

Neural networks

The term neural network was traditionally used to refer to a network or circuit of biological neurons. Our usage of the term (at least for now) refers to artificial neural networks, which are composed of artificial neurons or nodes.

Artificial neurons were first proposed in 1943 by Warren McCulloch, a neurophysiologist, and Walter Pitts, a logician. The concept of a neural network appears to have first been proposed by Alan Turing in his 1948 paper “Intelligent Machinery”.

Neural networks Connectionism is a set of approaches in the fields of artificial intelligence, cognitive psychology, cognitive science, neuroscience and philosophy of mind, that models mental or behavioral phenomena as the emergent processes of interconnected networks of simple units.

In a neural network model, simple nodes, which can be called “neurons”, “processing elements” or “units”, are connected together to form a network. While a neural network does not have to be adaptive per se, its practical use comes with algorithms designed to alter the strength (weights) of the connections in the network to produce a desired signal flow.

One classical type of artificial neural network is the recurrent Hopfield net.

Attractor network

In general, an attractor network is a network of nodes (i.e., neurons in a biological network), often recurrently connected, whose time dynamics settle to a stable pattern.

Hopfield network

A Hopfield network is a recurrent neural network having synaptic connection pattern such that there is an underlying Lyapunov function for the activity dynamics. Started in any initial state, the state of the system evolves to a final state that is a (local) minimum of the Lyapunov function.

Also see chapters 13 and also 12 of this online book:

Graphical models in statistics

In statistics and related areas, graphical model refers to a probabilistic model for which a graph denotes the conditional independence structure between random variables. They are most commonly used in probability theory, statistics particularly Bayesian statistics and machine learning.

Bayesian networks

A Bayesian network, also known as a belief network, is used to represent knowledge about an uncertain domain: it consists of a directed acyclic graph or ‘DAG’ where the nodes are labelled by random variables and the edges represent probabilistic dependencies between these random variables. These conditional dependencies in the graph are often estimated by using known statistical and computational methods. These networks combine principles from graph theory, probability theory, computer science, and statistics.

For more, see:

and other papers on Jordan’s website.

Structural equation modeling

Structural equation modeling or SEM is a statistical technique for testing and estimating causal relations using a combination of statistical data and qualitative causal assumptions. It was developed by the geneticist Sewall Wright (1921), the economist Trygve Haavelmo (1943) and the cognitive scientist Herbert Simon (1953), and formalized by Judea Pearl (2000). A bunch of papers can be found here:

In particular, graphical techniques appear here:

On page 10 we see that a ‘path diagram’ is a directed acyclic graph (DAG) with vertices labelled by variables and with edges corresponding to ‘causal relations’. This is presumably the same as a Bayesian network (see above). For example:

structural equation modeling

More can be found here:

with all diagrams relegated to the end.

There are interesting relations between Bayesian networks and algebraic geometry:

This may be related in interesting ways to the theory of tensor networks and also the applications of toric varieties to chemical reaction networks (see Diagrams#Chemical Reaction Networks?|below). Note that Bernd Sturmfels is involved in both!

On the Azimuth Blog, Krystof also recommends the following related references:

The paper by Jordan is particularly interesting in how it relates Bayesian networks to ideas from information geometry. This relation is also discussed in the Geiger-Meek-Sturmfels paper On the toric algebra of graphical models.

Chemical reaction networks

Chemical reaction networks are diagrams widely used in chemistry. They are quite similar to Petri nets?, but in some sense more primitive and less expressive:

chemical reaction network

A chemical reaction network shows a collection of different molecular species (types of molecules). For example, in the above diagram taken from Feinberg’s lectures below, A,B and C are three molecular species, and we have four reactions between them:

A+A→BA + A \to B
C→A+AC \to A + A
B→CB \to C
C→BC \to B

which can occur at various rates. After specifying the reaction rates, we obtain an ordinary differential equation describing the time evolution of the concentration of the various molecular species. We can infer some qualitative properties of the solutions of this equation just from the picture of the reaction network.

For details, start with:

and then try these classic references:

The last is apparently not free online, but here’s a quote that explains the philosophy:

A physical chemist usually consider electrons atoms, molecules and their interaction as primitive notions, and is interested in studying the mechanism of rearrangement of atoms into new molecules during chemical reactions. He may also explore what inferences may be drawn regarding reaction rates, possibly with the assistance of statistical mechanics.

The formal kineticist, on the other hand, takes a macroscopic viewpoint and his primitive concept is the elementary reaction. This is defined by a set of stoichiometric coefficients, together with a rule relating reaction rate to composition and temperature. The primary macroscopic observable is the rate of change of composition of the mixture, and an expression for this is constructed by adding the rates of elementary reactions, each weighted by the corresponding set of stoichiometric coefficients. The elementary reactions thus provide a framework for constructing differential equations to be satisfied by the composition.

The abstract is also useful:

Abstract: The familiar idea of mass action kinetics is extended to embrace situations more general than chemically reacting mixtures in closed vessels. Thus, for example, many reaction regions connected by convective or diffusive mass transport, such as the cellular aggregates of biological tissue, are drawn into a common mathematical scheme. The ideas of chemical thermodynamics, such as the algebraic nature of the equilibrium conditions and the decreasing property of the free energy, are also generalized in a natural way, and it is then possible to identify classes of generalized kinetic expressions which ensure consistency with the extended thermodynamic conditions. The principal result of this work shows that there exists a simply identifiable class of kinetic expressions, including the familiar detailed balanced kinetics as a proper subclass, which ensure consistency with the extended thermodynamic conditions. For kinetics of this class, which we call complex balanced kinetics, exotic behavior such as bistability and oscillation is precluded, so the domain of search for kinetic expressions with this type of behavior, which is of considerable biological interest, is greatly narrowed. It is also shown that the ideas of complex balancing and of detailed balancing are closely related to symmetry under time reversal.

See also:

Here’s the abstract:

Abstract: Abstract bifurcation theory is one of the most widely used approaches for analysis of dynamical behaviour of chemical and biochemical reaction networks. Some of the interesting qualitative behaviour that are analyzed are oscillations and bistability (a situation where a system has at least two coexisting stable equilibria). Both phenomena have been identified as central features of many biological and biochemical systems. This paper, using the theory of stoichiometric network analysis (SNA) and notions from algebraic geometry, presents sufficient conditions for a reaction network to display bifurcations associated with these phenomena. The advantage of these conditions is that they impose fewer algebraic conditions on model parameters than conditions associated with standard bifurcation theorems. To derive the new conditions, a coordinate transformation will be made that will guarantee the existence of branches of positive equilibria in the system. This is particularly useful in mathematical biology, where only positive variable values are considered to be meaningful. The first part of the paper will be an extended introduction to SNA and algebraic geometry-related methods which are used in the coordinate transformation and set up of the theorems. In the second part of the paper we will focus on the derivation of bifurcation conditions using SNA and algebraic geometry. Conditions will be derived for three bifurcations: the saddle-node bifurcation, a simple branching point, both linked to bistability, and a simple Hopf bifurcation. The latter is linked to oscillatory behaviour. The conditions derived are sufficient and they extend earlier results from stoichiometric network analysis as can be found in (Aguda and Clarke in J Chem Phys 87:3461–3470, 1987; Clarke and Jiang in J Chem Phys 99:4464–4476, 1993; Gatermann et al. in J Symb Comput 40:1361–1382, 2005). In these papers some necessary conditions for two of these bifurcations were given. A set of examples will illustrate that algebraic conditions arising from given sufficient bifurcation conditions are not more difficult to interpret nor harder to calculate than those arising from necessary bifurcation conditions. Hence an increasing amount of information is gained at no extra computational cost. The theory can also be used in a second step for a systematic bifurcation analysis of larger reaction networks.

This paper says that a fundamental reference on stochastic network analysis is:

  • B.L. Clarke and I. Prigogine, Stability of complex reaction networks, Adv. Chem. Phys., Wiley, New York, 43 (1980), 1–-216.

There is an interesting relation between chemical reaction networks (or, better, Petri nets) and toric varieties. See:

and also the paper by Mirela Domijan and Markus Kirkilionis cited above.

There is a nice introduction to chemical reaction networks here:

This paper is about situations where you have a bunch of independent Poisson random variables X j with known Poisson parameters, and you want to know the distribution of one conditioned on the values of some linear combinations of these variables.

It give some ways to efficiently compute this distribution using ‘Wilf-Zeilberger theory’ and the ‘Apagodu-Zeilberger algorithm’. The authors wrote a Maple Package that does the job.

However, Section 6, on biochemical applications, is about chemical reaction networks. It’s a self-contained detailed introduction to this subject, with lots of examples, and references to a bunch of the most important papers on the subject!

The connection is that chemical reaction networks satisfying a certain technical condition have stable equilibrium states where the number X j of molecules of the jth type is a Poisson random variable, and these random variables are independent. So, the work in this paper applies.

Petri nets

Petri nets are mainly used to study concurrency in computer science, but they are also used to describe chemical reaction networks, manufacturing operations, and other systems. See:

and

for more details. As far as applications to chemistry go, Petri nets are more or less equivalent to chemical reaction networks. On Azimuth, Manoj Gopalkrishnan writes:

Though Carl Petri invented his nets to represent chemical reaction networks, I don’t know if they were used much to study these networks. The first application I know of in this direction is some rather recent work by David Angeli with Patrick De Leenheer?, and Eduardo Sontag. See, for example, A Petri Net approach to the study of persistence in chemical reaction network." and On modularity and persistence of chemical reaction networks."

Petri nets are just one of several formalisms that exploit an analogy between chemistry and concurrency in computer science. Another is the ‘Chemical Abstract Machine’ or ‘CHAM’:

  • Gérard Boudol, Some chemical abstract machines, in A Decade of Concurrency - Reflections and Perspectives, Lecture Notes in Computer Science 803 (1994), 92-123.
A quote:

Intuitively, the state of a system in (Ban&ahat;tre and Le Métayer’s formalism) Gamma is like a chemical solution in which floating molecules can interact with each other according to reaction rules. A magical mechanism stirs the solution, allowing for possible contacts between molecules. This stirring mechanism is assumed to be given—i.e. it is provided by the implementation. The task of implementing the “Brownian motion” and the reactions may be difficult—it involves the usual problems regarding fairness deadlocks and termination detection—see 4 but it is definitely taken apart from the design of parallel programs. Technically, a chemical solution is just a finite multiset of elements ( = molecules) denoted S={m 1,…,m k}. This accounts for the stirring mechanism—since the elements are unordered—so that they may always be assumed to be in contact with each other.

Systems ecology

The ‘Energy Systems Language’ was developed by Howard T. Odum and his colleagues in the 1950s during studies of the tropical forests funded by the United States Atomic Energy Commission. Odum is the founder of ‘systems ecology’:

Energy Systems Symbols

His most detailed book on diagrams for systems ecology seems to be this:

  • Howard T. Odum, Systems Ecology: an Introduction, Wiley-Interscience, New York, 1983.

In this book:

  • R. L. Kitching, Systems Ecology: An Introduction to Ecological Modelling, University of Queensland Press, 1983.

the author writes:

Because of its electrical analogy, the Odum system is relatively easy to turn into mathematical equations … If one is building a model of energy flow then certainly the Odum system should be given serious consideration…

This makes it sound like Paynter’s ‘bond graphs’, mentioned above. According to the Wikipedia article on Odum,

Odum’s language appears to be similar in approach to the Systems Modeling Language recently developed by INCOSE, an international Systems Engineering body.


Some common symbols used in Forrester diagrams. From Kitching, UQP, 1983.

Here is a more recent paper on ecological networks. One of the authors is the head of the Complex Agent-Based Dynamic Networks group at Oxford, mentioned below:

Phillip P. A. Staniczenko, Owen T. Lewis, Nick S. Jones and Felix Reed-Tsochas, Structural dynamics and robustness of food webs, Ecology Letters

Systems modeling

According to Wikipedia,

The Systems Modeling Language (SysML) is a general-purpose modeling language for systems engineering applications. It supports the specification, analysis, design, verification and validation of a broad range of systems and systems-of-systems. SysML was originally developed by an open source specification project, and includes an open source license for distribution and use. SysML is defined as an extension of a subset of the Unified Modeling Language (UML) using UML’s profile mechanism.

The Systems Modeling Language has 9 types of diagrams.

Also according to Wikipedia,

The SysML initiative originated in a January 2001 decision by the International Council on Systems Engineering (INCOSE) Model Driven Systems Design workgroup to customize the UML for systems engineering applications. Following this decision, INCOSE and the Object Management Group (OMG), which maintains the UML specification, jointly chartered the OMG Systems Engineering Domain Special Interest Group (SEDSIG) in July 2001.

See also:

Systems biology

Diagrams are used extensively in a variety of ways in biology, and this project is an attempt to clarify and standardize their different uses:

SBGN is made up of three different languages, representing different visions of biological systems. Each language involves a comprehensive set of symbols with precise semantics, together with detailed syntactic rules how maps are to be interpreted:

  • The SBGN Process Description (PD) language shows the temporal courses of biochemical interactions in a network. It can be used to show all the molecular interactions taking place in a network of biochemical entities, with the same entity appearing multiple times in the same diagram.
PD
  • The SBGN Entity Relationship (ER) language allows you to see all the relationships in which a given entity participates, regardless of the temporal aspects. Relationships can be seen as rules describing the influences of entities nodes on other relationships.
ER
  • The SBGN Activity Flow (AF) language depicts the flow of information between biochemical entities in a network. It omits information about the state transitions of entities and is particularly convenient for representing the effects of perturbations, whether genetic or environmental in nature.
AF

The last one sounds closest to ‘bond graphs’, but it’s different in detail.

Complex agent-based dynamic networks

There is a research group of this name at the University of Oxford, run by Felix Reed-Tsochas:

For more on time-evolving networks see

  • S.N. Dorogovtsev and J.F.F. Mendes, Evolution of Networks: From Biological Nets to the Internet and WWW, Oxford U. Press, Oxford, 2006.

  • Mark Newman, Albert-Laszlo Barabasi and Duncan J. Watts, The Structure and Dynamics of Networks, Princeton Studies in Complexity, Princeton U. Press, Princeton, New Jersey, 2006.

Software for working with diagrams

WireIt is an open-source javascript library to create web wirable interfaces for dataflow applications, visual programming languages, graphical modeling, or graph editors:

LabVIEW is a graphical programming environment used by engineers and scientists to develop measurement, test, and control systems using graphical icons and wires that resemble a flowchart:

John Furey writes:

Electrical engineers (in the US anyway) probably have more experience and need to use LabVIEW then any other programming environment. There was a time, say 15 years ago, we would say NI makes great data acquisition hardware but their software needs work. Now it’s almost the other way around, except their hardware is still pretty good.

FWIW, LabVIEW is the standard programming environment for robotics for a number of reasons. One is still that often there is no good substitute for a NI hardware component. Another is that, like Matlab, it works. And has a large user repository. High school and younger students have to use versions of LabVIEW in the FIRST competitions.

Further additions

These are wikipedia topics that seem connected to the topics here, and warrant further investigation to integrate into this page.

Revised on August 28, 2011 05:13:01 by Jacob Biamonte (216.16.224.186)
Edit | Back in time (42 revisions) | See changes | History | Views: Print | TeX | Source | Linked from: Home Page