# Why are physicists interested in graph theory?

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?

• Both answers have nothing to do with complex network theory which the concept of "small world graphs" originates from. Commented Dec 13, 2010 at 16:10
• @KennyTM: well, I don't know anything about that topic (at least under this terminology) so I answered the question in the title and the question of how does graph theory come into physics. Perhaps a little clarification on the side of OP wouldn't hurt. Still, I think answers are quite useful (even if they answer something a little different). Commented Dec 13, 2010 at 16:37
• @KennyTM: but reading about the references further, I think I've seen this stuff come up at some place or other in statistical physics. I'll try to look up the references and perhaps will provide another answer more directly connected to these topics. Commented Dec 13, 2010 at 16:40
• @Marek: I know the topic (BTW you can find lots of papers about it on PRE) but I don't know why physicists study them. :) Commented Dec 13, 2010 at 17:51
• I hope the advice ends up being beneficial. Commented Dec 13, 2010 at 18:30

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!

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.

• +1 Although there is no physics in this I like the answer very much. Also, I took a liberty of fixing some typos and one link; I hope you don't mind. Commented Dec 13, 2010 at 21:55
• By the way, do you know whether there is any connection to things like $k$-SAT and graph coloring problems? I know some of these problems (which seem to be purely in the domain of complexity theory) were studied by methods very close in spirit to statistical physics. In particular, random $k$-SAT problems can be shown to have different phases characterized as "clustered" and "frozen" (among others). See e.g. this paper. Of course, this was made quite famous recently because of an $P\neq NP$ attack of Deolalikar. Commented Dec 13, 2010 at 22:00
• This is a very nice answer +1
– user346
Commented Dec 13, 2010 at 22:50
• @Marek: Thanks. I don't think it is related to algorithmic/combinatorics stuff like k-SAT and graph coloring. Commented Dec 14, 2010 at 15:02

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.

• If you care to add spectral graph theory and its role to that list, you'll get my vote. :) Commented Dec 13, 2010 at 20:50
• @Noldorin: I will have to think about it. Most of the uses of spectral graph theory I know of are pure mathematics or computer science. But thanks to your comment I recalled other places graphs pop up: relation between Potts model and number of graph colorings; relation between electrical resistance on the graph and its spanning trees; and also Markov chains on graphs. Latter two cases can be studied by the means of some associated matrix. But it's not quite an adjacency matrix and so not quite a spectral theory. If you have anything concrete in mind, please let me know :-) Commented Dec 13, 2010 at 21:38
• @Marek: That is in fact true nowadays, but spectral graph theory (hinted by its name) actually originated in quantum chemistry... Not that I know much about it - was hoping you would know more heh. Commented Dec 13, 2010 at 22:15
• @Noldorin: ah, if the quantum chemistry origin is indeed correct, I had no idea about that at all! What I always implicitly assumed is that spectral refers to the spectrum of the (adjacency) matrix. And this is quite general term pertaining to many areas of mathematics (as in spectrum of some operator). I'll try to find out which version is the correct one. Commented Dec 13, 2010 at 22:25
• @Marek: You could be right, though I do remember some relation with quantum chemistry.... Commented Dec 13, 2010 at 23:09

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.

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.