The Azimuth Project
Network theory (changes)

Showing changes from revision #12 to #13: Added | Removed | Changed

The idea

Network theory is a sprawling subject that uses graphs with extra structure to model complex systems. The study of networks is developing as a tool 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.

General references

The Azimuth Blog has a long series of posts on network theory, which can be accessed most conveniently here:

The posts on Petri nets and chemical reaction networks are being collected into a book, which is available in draft form:

Some textbook treatments include:

What follows is an annotated list of references on diagrammatic notations for specific kinds of networks.

Contents

Systems dynamics

The study of complex systems with the help of diagrams was advocated starting in the 1950s by Jay Forrester. He called this subject systems dynamics. Here is an example:

For more on the history of this topic let us quote

System dynamics was created during the mid-1950s by Professor Jay Forrester of the Massachusetts Institute of Technology. In 1956, Forrester accepted a professorship in the newly-formed MIT Sloan School of Management. His initial goal was to determine how his background in science and engineering could be brought to bear, in some useful way, on the core issues that determine the success or failure of corporations. Forrester’s insights into the common foundations that underlie engineering, which led to the creation of system dynamics, were triggered, to a large degree, by his involvement with managers at General Electric (GE) during the mid-1950s. At that time, the managers at GE were perplexed because employment at their appliance plants in Kentucky exhibited a significant three-year cycle. The business cycle was judged to be an insufficient explanation for the employment instability. From hand simulations (or calculations) of the stock-flow-feedback structure of the GE plants, which included the existing corporate decision-making structure for hiring and layoffs, Forrester was able to show how the instability in GE employment was due to the internal structure of the firm and not to an external force such as the business cycle. These hand simulations were the beginning of the field of system dynamics.

During the late 1950s and early 1960s, Forrester and a team of graduate students moved the emerging field of system dynamics from the hand-simulation stage to the formal computer modeling stage. Richard Bennett created the first system dynamics computer modeling language called SIMPLE (Simulation of Industrial Management Problems with Lots of Equations) in the spring of 1958. In 1959, Phyllis Fox and Alexander Pugh wrote the first version of DYNAMO (DYNAmic MOdels), an improved version of SIMPLE, and the system dynamics language became the industry standard for over thirty years. Forrester published the first, and still classic, book in the field titled Industrial Dynamics in 1961.

From the late 1950s to the late 1960s, system dynamics was applied almost exclusively to corporate/managerial problems. In 1968, however, an unexpected occurrence caused the field to broaden beyond corporate modeling. John Collins, the former mayor of Boston, was appointed a visiting professor of Urban Affairs at MIT. The result of the Collins-Forrester collaboration was a book titled Urban Dynamics. The Urban Dynamics model presented in the book was the first major non-corporate application of system dynamics.

The second major noncorporate application of system dynamics came shortly after the first. In 1970, Jay Forrester was invited by the Club of Rome to a meeting in Bern, Switzerland. The Club of Rome is an organization devoted to solving what its members describe as the “predicament of mankind”—that is, the global crisis that may appear sometime in the future, due to the demands being placed on the Earth’s carrying capacity (its sources of renewable and nonrenewable resources and its sinks for the disposal of pollutants) by the world’s exponentially growing population. At the Bern meeting, Forrester was asked if system dynamics could be used to address the predicament of mankind. His answer, of course, was that it could. On the plane back from the Bern meeting, Forrester created the first draft of a system dynamics model of the world’s socioeconomic system. He called this model WORLD1. Upon his return to the United States, Forrester refined WORLD1 in preparation for a visit to MIT by members of the Club of Rome. Forrester called the refined version of the model WORLD2. Forrester published WORLD2 in a book titled World Dynamics.

Systems ecology

The ‘Energy Systems Language’, or ‘Energese’ 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, Energese is similar to the Systems Modeling Language recently developed by INCOSE, an international Systems Engineering body.

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

See also

On Google+, Ted Pavlic wrote:

A number of prominent control theorists (like Richard Murray and his most recent graduate students and postdocs) have turned to synthetic biology as a major application area. Consequently, they make heavy use of another diagram used in living systems – the gene regulatory network. Gene regulatory networks are very similar to signal flow diagrams as they incorporate negative and positive feedback and amplification. You didn’t mention gene regulatory networks, but I think you should consider them as you venture outside of control.

At larger ecosystem scales, it is important to consider food webs and how to augment them with mass-balance constraints. To this end, researchers have developed “ecological stoichiometry” which turns food webs into chemical reaction networks. More recently, ES researchers in ecology have retuned it to consider the scale of the cell. This new version is being called “biological stoichiometry.” Both cases seem to fit into your ultimate goal.

I’m a control theorist working in a behavioral ecology lab – splitting my collaborative time between engineers, physicists, mathematicians, and biologists (behavioral, neuroethological, physiological). Additionally, I periodically interact with biogeochemists interested in geological engineering that lives exactly at the technology–biosphere interface. So there are a lot of people working in this space, and it would probably be useful to survey how people are already shuttling ideas about abstraction across these disciplinary boundaries.

Systems modeling language

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. Process Descriptions correspond to systems of ordinary differential equations.
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. Entity Relationships correspond to rule-based models (e.g. models encoded in BioNetGen?, Kappa?, etc.).
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. Activity Flows correspond to logical models of the sort used by Stuart Kauffman and Rene Thomas.
AF

Electrical circuit diagram

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.

Bond graph

Bond graphs are an alternative formalism to electrical circuit diagrams, which are also widely applied in other engineering contexts. For an introduction, see This Week’s Finds starting in week289. They 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 network

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. See Neural network.

Adaptive network

The term adaptive network is sometimes used to denote a network whose topology changes with time in a way that interacts with dynamics on the network. For an introduction see:

A quote:

A network consists of a number of network nodes connected by links (….) The specific pattern of connections defines the network’s topology. For many applications it is not necessary to capture the topology of a given real-world network exactly in a model. Rather, in many cases the processes of interest depend only on certain topological properties (Costa et al. 2007). The majority of recent studies revolve around two key questions corresponding to two distinct lines of research: what are the values of important topological properties of a network that is evolving in time? And, how does the functioning of the network depend on these properties?

The first line of research is concerned with the dynamics of networks. Here, the topology of the network itself is regarded as a dynamical system. It changes in time according to specific, often local, rules. Investigations in this area have revealed that certain evolution rules give rise to peculiar network topologies with special properties. Notable examples include the formation of small world (Watts & Strogatz 1998) and scale-free networks (Price 1965; Barabàsi & Albert 1999).

The second major line of network research focuses on the dynamics on networks. Here, each node of the network represents a dynamical system. The individual systems are coupled according to the network topology. Thus, the topology of the network remains static while the states of the nodes change dynamically. Important processes that are studied within this framework include synchronization of the individual dynamical systems (Barahona & Pecora 2002) and contact processes such as opinion formation and epidemic spreading (Kuperman & Abramson 2001; Pastor-Satorras & Vespignani 2001; May & Lloyd 2001; Newman 2002; Boguñá et al. 2003). These studies have made it clear that certain topological properties have a strong impact on the dynamics. For instance, it was shown that vaccination of a fraction of the nodes cannot stop epidemics on a scale-free network (May & Lloyd 2001; Pastor-Satorras & Vespignani 2001).

Until recently, the two lines of network research were pursued almost independently in the physical literature. While there was certainly a strong interaction and cross-fertilization, a given model would either describe the dynamics of a certain network or the dynamics on a certain network. Nevertheless, it is clear that in most real-world networks the evolution of the topology is invariably linked to the state of the network and vice versa. For instance, consider a road network. The topology of the network, that is the pattern of roads, influences the dynamic state, e.g. the flow and density of traffic. But if traffic congestions are common on a given road, it is probable that new roads will be built in order to decrease the load on the congested one. In this way a feedback loop between the state and topology of the network is formed. This feedback loop can give rise to a complicated mutual interaction between a time varying network topology and the nodes’ dynamics. Networks which exhibit such a feedback loop are called coevolutionary or adaptive networks (….)

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 network

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.

This book has a chapter on Bayesian networks:

  • Edward A. Bender, Mathematical Methods in Artificial Intelligence

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 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 network

Chemical reaction networks are diagrams widely used in chemistry:

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,BA, B and CC are three molecular species, and we have four reactions between them:

A+AB A + A \to B
CA+A C \to A + A
BC B \to C
CBC \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.

The formalism of chemical reaction networks is essentially equivalent to the formalism of stochastic Petri nets. For more, see

Also see:

and 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.

Petri net

basic chemical Petri net

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. For details, see:

Petri nets are different from, but entirely equivalent to, chemical reaction networks. On Azimuth, Manoj Gopalkrishnan wrote:

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 DeLeenheer, 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 (Banatre 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}S = \{m_1, \dots, 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.

Complex agent-based dynamic network

There is a research group called Complex Agent-Based Dynamic Networks 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.

Tensor network

‘Tensor networks’ are very close to the well-understood aspects of diagrammatic mathematics discussed in the review articles by Baez mentioned above. They are spin networks, or Feynman diagrams, where the symmetry group is the trivial group. However, while Feynman diagrams and spin networks are used in quantum field theory and quantum gravity, tensor networks are used it some other ways, for example to describe states of multi-part quantum systems. See for example this post on the nCafe about the following paper:

Tensor network states have a long history, with many independent tracks of research arriving at related ideas. While the above 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:

  • John Baez and Jacob Biamonte, [Tensor Network States], nLab.

Wikipedia articles

Here are some Wikipedia articles that seem connected to the topics here, and warrant further investigation to integrate into this page:

Textbooks

A free online textbook on network theory:

The Network Science Book Project aims to produce an interactive textbook for network science. It is a work in progress, as we add chapters as they are finalized. Currently you will find Chapter 1-6, and we hope to have ten chapters by the end of the year. It is freely available under the Creative Commons licence for iPad and in pdf, together with the slides to teach the material.

Games

As an adjunct to a MOOC run by the Center for Infectious Disease Dynamics at Penn State University with +Coursera, redditor Ells86 has created an online game allowing users to learn how diseases spread through networks. It’s fun!