Why are physicists interested in graph theory?

Question

Can you tell me how graph theory comes into physics, and the concept of small world graphs?

(inspired to ask from comment from sean tilson in):

Which areas in physics overlap with those of social network theory for the analysis of the graphs?

Answer 1

Richard Feynman reformulated quantum mechanics (and quantum field theory) in terms of a path integral, meaning that in order to find the likelihood of some process occurring, you take a kind of weighted average over all potential trajectories. The weighting function is the exponentiated "action," $\exp(iS/\hbar).$ and the dominant contribution comes from paths which extremize this function, i.e. classical trajectories.

Typically -- almost always -- this integral is too hard for anyone to do (let alone define rigorously), so Feynman developed a perturbation theory, an expansion in terms of graphs. The nature of the graphs depends on the interactions and coupling constants of your model -- that is, on the action.

An (oversimplified) example: Suppose you only had one degree of freedom, x, and the action is $S_0(x) = i\hbar x^2/2$, so that $\exp(iS_0/\hbar) = \exp(-x^2/2).$ (You can ignore $\hbar$ in this example.) Then the path integral is $\int \exp(-x^2/2) dx$ and equals $\sqrt{\pi}$. However, if we add a cubic "interaction" term, so $S = S_0 - i\hbar a x^3$ then we can expand $\int \exp(iS/\hbar)$ in powers of $a,$ the first nonzero contribution being $a^2 \int (x^3)^2 \exp(-x^2/2) dx,$ which you can do exactly. (The term linear in $a$ is zero because the three powers of $x$ can't be paired up ["contracted"].) The graph for this term has two vertices (the two powers of $a$), each with three edges attached (the three powers of $x$ in the interaction term).

So graphs are ubiquitous in QFT!

Answer 2

I don't know why physicists are interested in complex network theory, but well, whenever you can create a physical model describing some behavior you could call it "physics" (econophysics, sociophysics, etc), and this is likely the reason why they study complex network. I will just answer the 2nd part of the question — the concept of small-world network.

Short average distance

The small-world phenomena is best known as the six degree of separation, i.e. two persons are related to each other by at most 6 steps in a network of human relationship.

In this network, people are represented by nodes, and if two people knows each other directly we create a link between the two nodes. If there are two nodes without a direct link, we could possibly take other routes. The smallest number of links need to be traversed is called the distance (a.k.a. path length) between the two nodes.

A small-world network (with size N) needs to satisfy a condition, that the average distance $\langle\ell\rangle$ over all possible node pairs is "short", i.e. $ \langle\ell\rangle \sim \log N $.

Many natural and artificial complex networks, like the human relationship network above, neural network, metabolic networks etc. have short average distance, which is why this property is being studied, because physicists wanted to have a model that describes most of these complex networks. The Erdős-Rényi model — which is essentially a network that the links are constructed with some constant probability — has the short average distance property.

High clustering coefficient

The ER model was one of the first models used to describe real-world complex networks, but was soon found to be insufficient because it doesn't have another important property — a "high" clustering coefficient.

The (local) clustering coefficient was introduced by Duncan J. Watts and Steven Strogatz in 1998 as a measure of how well nodes are "clustered" together locally. It is defined as $$ c_{v} = \frac{\text{number of triangles containing }v}{\frac{k_v(k_v-1)}2} $$ where $k_v$ is the number of links connected to $v$, i.e. its degree. The local clustering coefficient is actually a ratio of "neighbors of $v$ that knows each other", and "maximum number of potential neighbors of $v$ that can know each other". For example, in this graph:

the clustering coefficient of the central green node is $$ c = \frac{\text{number of triangles}}{\frac{k(k-1)}2} = \frac{4}{\frac{5(5-1)}2} = 0.4. $$

If the local clustering coefficient is 0, then all your friends don't know each other, which is not true in the social network. The expected behavior is a large clustering coefficient, where groups of your friends know each other (thus forming triangles, i.e. A knows B, B knows C, C knows A). This property is where the ER model breaks down — its clustering coefficient is close to zero with the same number of nodes and links with a real network.

When a network has both short average distance and high average local clustering coefficient, we call it a small-world network.

And beyond

The Watts-Strogatz model was invented to address the small-world property. However, it was soon determined that even the WS model is not good enough as it is not scale-free. And then the Barabási-Albert model was created to describe why real-world networks both small-world and scale-free, although it also cannot explain other properties like the clustering coefficient distribution, hierarchical structure, etc, and of course more and more sophisticated models are proposed as well.

In the end, these properties are studied to construct a universal model that describes all (if not possible, "most") real-world complex networks, and use it to test and improve behaviors such as error and attack tolerance, evolution dynamics etc.

If you don't fear a lot of mathematics, the 2002 review paper Statistical mechanics of complex networks by Réka Albert and Albert-László Barabási is a (IMO) must-read classic for anyone beginning to study complex networks. All of the above can be found in this paper.

Answer 3

Not sure this is what you are aiming at, but graphs are ubiquitous in statistical physics!

They really crop up all over the place. To give you some ideas from the top of my head:

Probability

Classical statistical physics is built on the concept of microstates. Each microstate has a certain energy $E$ gets a probability $P = {1 \over Z} exp(-\beta E)$ where $\beta$ is a parameter depending on the temperature of the system and $$Z = \sum_{microstates} exp(-\beta E)$$ is the partition function.

Once you make this assignment of probabilities you can ask for things like average energy of the system and fluctuations and lots of other interesting stuff. And all of that stuff can be computed easily if you can somehow carry out the summation and determine the partition function. That is, the problem can often (at least in the discrete case) be reduced to counting, which means combinatorics. And often the combinatorial problem has to do with graph theory (either directly or by means of some clever duality).

Crystals

Statistical physics often investigates lattices. This is because they model crystals or other ordered forms of matter. These are very special graphs that possess translational symmetries (and more generally also some rotational and reflectional symmetries; think about hexagonal lattice). Once again you can define energy for microstates as in the first example and proceed to formulate the probabilistic problem. But it can be observed that lots of methods that work for investigation of the system on the lattice can actually be generalized to arbitrary graphs.

Arbitrary graphs

Perhaps nicest connection (and one positively stunning if you haven't heard about it before) is between correlation function of the Gaussian free field on the graph and random walks on the same graph (see e.g. this recent blog on the topic). This is a discrete version of the Feynman path integral which gives you probability amplitudes of particle getting from one place to another in terms of summing over every path between the two points.

Polymer model

One more model I'd like to mention is the Polymer model. The idea is that you have some objects, called polymers, that usually live on some kind of lattice (imagine e.g. cycles on the edges of the hexagonal lattice). Now the requirement is that these objects do not occupy the same space of the lattice (i.e. they don't intersect). This idea can be rigorously captured by the means of a huge infinite-dimensional graph where vertices are all of the possible polymers with edges between any two of them that are not compatible (that is, when they intersect on the original lattice).

This looks like a hard problem but actually it can be investigated by the means of cluster expansion. To give (an oversimplified) idea: it all stems from the simple but very useful combinatorial identity $$ \exp(\sum_i x_i) = \sum_N {1 \over N!} (\sum_i x_i)^N = \sum_N \sum_{i_1 + \cdots + i_N = N} \prod_k{x_k^{i_k} \over i_k!}$$ Using this one can transform the partition function $Z$ (which is an ugly sum over all possible subgraphs of the original huge graph) into an exponential of sum over just connected subgraphs of the polymer graph. Now connected subgraphs are much nicer objects than arbitrary subgraphs and one indeed obtains nice results by expanding the logarithm of the partition function in this way.

Answer 4

One context in which graphs can be useful in physics is in the discrete representation of spacetime in quantum gravity, where events are represented by the nodes of a type of poset (partially ordered set) called a causet and causal relationships are represented by the edges. This is particularly suited to a graph-theoretic interpretation, since posets can be intuitively visualized as DAGs.

Answer 5

Graph theory is very useful in design and analysis of electronic circuits.

It is very useful in designing various control systems.

E.g. Signal Flow Graphs and Meson's Rule make your life a lot easier while trying to find transfer functions.

Also, while solving differential equations numerically Graph Theory is used for mesh generation.