Gallery

The spectrum of the non-backtracking operator of a random graph with community structure

Spectral clustering is a popular (and fast) method of finding communities in networks. But using the adjacency matrix or graph Laplacian can fail badly in the sparse case, due to the presence of localized eigenvectors. In Krzakala, Moore, Mossel, Neeman, Sly, Zdeborova, and Zhang, PNAS 110, no. 52 (2013) pp 20935-20940 (or see the arxiv version) we conjectured that using the non-backtracking or Hashimoto operator instead removes this problem, giving a spectral algorithm that succeeds all the way down to the detectability transition in the stochastic block model. This conjecture was recently proved by Bordenave, Lelarge, and Massoulie.

Here is the spectrum of a sparse random graph. Note how there are isolated eigenvalues at the average degree and to the community structure; the bulk of the spectrum appears to be confined to a disk in the complex plane of radius sqrt(average degree).

The 3-body (and n-body) Problem

In 1993 I wrote a paper in Physical Review Letters in which I discovered solutions of the n-body problem in the plane where masses describe various types of braids around each other, including one where three equal masses orbit each other in a figure-8. This orbit was subsequently rediscovered by Alain Chenciner and Richard Montgomery, who provided a rigorous proof of its existence, and many additional "choreographies" were found (with much more precise numerical work than mine) by Carles Simo. Here are movies of the figure-8 and a similar orbit with 21 masses, made by Michael Nauenberg of UC Santa Cruz.

My 1993 work was based on a simple action-minimizing approach in which I discretized the trajectory and then performed gradient descent with the position at each time. Michael pioneered a different approach, in which we perform gradient descent in the coefficients of the trajectories' Fourier transform. Using this approach, Michael and I have found a number of lovely three-dimensional orbits, including a family with cubic symmetry where 4k masses travel around 4 roughly circular interlocked orbits (where k is odd). Topologically, these orbits form the edges of a cuboctahedron. Since they have cubic symmetry, their total angular momentum is zero and their moment of inertia tensor is diagonal in the x,y,z basis.

(If you have trouble with the following movies, note that both Quicktime and RealPlayer can play .gif files. Also, I am indebted to Greg Egan for helping me loopify these movies in postproduction.)

Here is a 4-mass orbit with cubic symmetry. (Note that this is not the same as the "hip-hop", in which the two pairs of masses co-rotate around the z-axis.) Movies in Quicktime and GIF.

Here also is a very nice page by Vicki Johnson with real-time simulations of this and other orbits, which allow you to rotate the point of view with your mouse.

Here is the cubic 12-mass orbit (which has some additional symmetry), in Quicktime and GIF. Here is another movie which shows the 4 orbits from a rotating point of view, Quicktime and GIF.

Here is the cubic 20-mass orbit, in Quicktime and GIF.

And here is the 28-mass one, in Quicktime and GIF.

Here is another lovely orbit, in which 6 masses orbit each other in two intersecting (roughly Lagrange) orbits: Quicktime and GIF.

And here is another, in which 6 masses orbit each other with dihedral symmetry. We can think of this as two Lagrange orbits which co-rotate and interleave with each other each time they pass through a common plane. This is a (large) perturbation of a 6-mass Lagrange orbit; it is an example of a class of "hip-hop" orbits found by Chenciner and Venturelli. Quicktime and GIF.

The figure-8 can be perturbed in various ways. Nauenberg and Marchal independently found this version, which rotates around the x-axis and forms a continuous family of orbits connecting the figure-8 with the Lagrange orbit. Quicktime and GIF.

Here is another orbit, which I call the "criss-cross". It was first found numerically by Henon in 1976 as one of a family of orbits in rotating frames, starting with Schubart's one-dimensional orbit. I rediscovered it in 1993 by looking for orbits with a particular braid type, and its existence was proved rigorously by Kuo-Chang Chen. (This movie was made with Michael's Fourier technique.) Quicktime and GIF. It appears to be dynamically stable, and it exists for a wide range of mass ratios: here is an example Michael found where the masses are 1, 2, and 3. Quicktime and GIF.

Finally, here is a lovely applet by Gregory T. Minton of Microsoft Research, which lets you draw a choreography and then tries to minimize its action.

Flows in Young diagrams

Here is a picture of elements of a random permutation flowing through a Young diagram under the Robinson-Shensted-Knuth process. (It's oriented so that the top row of the Young diagram is at the left.) I would love to have a hydrodynamic description of these flows...

Sandpiles

The Abelian sandpile possesses a unique identity state on each lattice, with the property that if we add it to any recurrent state x and let the subsequent avalanches take place, we will end up with the same state x we started with. Not much is known about these besides their existence, but there are many conjectures about the identities for the square lattice that remain unproven. Here is the identity for the 500x500 lattice, produced by Vishal Sanwalani of UNM.

And here is a "mandala" produced from a stream of sand particles at the origin, also by Vishal Sanwalani. Jim Propp of the University of Wisconsin would like to know whether the limiting shape is a circle, or some kind of complex polygon. Some partial results in this direction, showing that it contains a diamond of radius r and is contained in a square of radius r, for some r ~ sqrt(n), were recently obtained by Babai and Gorodezky in SODA 2007, and Levine and Peres showed that it is bounded between two circles.

Cellular automata

My friend David Griffeath studies cellular automaton growth rules that produce pleasing fractal patterns. When the number of steps is a power of 2, the cluster fills most of a square or diamond, but in between its boundary is like a "Koch snowflake." Here are clusters grown after 512 steps, starting with a single seed in the upper-left corner. The color cycles every 86 steps. Shown are five different rules, depending on how many neighbors you need in the cluster in order for your site to be added. The first four are on the Moore neighborhood (no relation) where each site has the eight King's-move neighbors; the last one is on the von Neumann neighborhood, where each site has just the four NSEW neighbors.

Potts models and vortex loops

Here is a picture of vortex loops in the three-dimensional, three-state antiferromagnetic Potts model on the cubic lattice. In other words, we are trying to color the cells of the cubic lattice with three different colors, so that cells are colored differently from each of their six neighbors. However, here there are still neighboring pairs of the same color, and these pairs form loops analogous to smoke rings or cosmic strings.

Random domino tilings of Aztec diamonds and stop signs

Here are random domino tilings of a series of "stop sign" shapes going from an Aztec diamond to a square. There is a frozen region outside an "arctic circle," but for stop signs the arctic circle seems to get squashed by the sides of the stop signs as the region gets squarer. Each of these was made by starting will all horizontal dominoes, and then performing a billion moves (ten billion for the 512x512) in which a random pair of dominoes is rotated, replacing two horizontals with two verticals or vice versa. Horizontal dominoes are red or green, depending on parity, and vertical ones are blue or yellow.

Here is a set of applets illustrating the Propp-Wilson coupling from the past algorithm.

Random three-colorings of the square lattice

A similar "arctic circle" phenomenon happens in random 3-colorings of the square lattice when the boundary conditions are analogous to those of an Aztec diamond --- forcing the height function to increase and decrease as fast as possible between the corners, which are alternating maxima and minima. Here the frozen region, in which the coloring is forced into a periodic pattern, has been removed. You can look at colorings of the 128x128, 256x256, or 512x512 lattices. They seem to be roughly circular, although there are theoretical reasons to believe that they might be some sort of superellipse instead. Note also the bands of different colors, which correspond to contours in the height function. (This is joint work with Joakim Linde of Goeteborg University.)

Quantum random walks

Quantum random walks consist of a diffusive process which is unitary rather than stochastic. Interference between paths of different phase can cause the probability to spread out faster than in classical random walks, mixing over a region of size L in time linear, instead of quadratic, in L. Here are some random walks on a two-dimensional lattice. Note the beautiful interference effects in the interior. (This is joint work with Alex Russell of the University of Connecticut.)
Copyright 2000 by Cris Moore. All rights reserved.