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
a similar orbit with 21 masses,
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'
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
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
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
GIF. Here is another movie
which shows the 4 orbits from a rotating point of view,
Here is the cubic 20-mass orbit, in
And here is the 28-mass one, in
Here is another lovely orbit, in which 6 masses orbit each other
in two intersecting (roughly Lagrange) orbits:
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.
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
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.)
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.
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...
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
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.
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
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
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.)
- With a particle initially pointing to the left, after
- With an equal distribution of initial directions, after
- With a different unitary operator with less symmetry, after
Copyright 2000 by Cris Moore. All rights reserved.