“Abelian sandpile model”的意思、由来-开放百科全书

The Abelian sandpile model, also known as the Bak–Tang–Wiesenfeld model, was the first discovered example of a dynamical system displaying self-organized criticality. It was introduced by Per Bak, Chao Tang and Kurt Wiesenfeld in a 1987 paper.^[1]

The model is a cellular automaton. In its original formulation, each site on a finite grid has an associated value that corresponds to the slope of the pile. This slope builds up as "grains of sand" (or "chips") are randomly placed onto the pile, until the slope exceeds a specific threshold value at which time that site collapses transferring sand into the adjacent sites, increasing their slope. Bak, Tang, and Wiesenfeld considered process of successive random placement of sand grains on the grid; each such placement of sand at a particular site may have no effect, or it may cause a cascading reaction that will affect many sites.

The model has since been studied on the infinite lattice, on other (non-square) lattices, and on arbitrary graphs (including directed multigraphs).^[2]

Definition

The iteration rules for the model on the square lattice can be defined as follows:

is unstable and can topple, sending one of its chips to each of its four neighbors:

The process is guaranteed to terminate given that the initial configuration was finite. Moreover, although there will often be many possible choices for the order in which to topple vertices, the final configuration does not depend on the chosen order; this is one sense in which the sandpile is Abelian. The number of times each vertex topples in this process is also independent of the choice of toppling order.

On an arbitrary undirected graph, a special vertex called a sink is specified that is not allowed to topple. In the presence of a sink, the term chip configuration refers to a chip-counting vector (nonnegative and integral) indexed by the non-sink vertices. The rules are that any non-sink vertex

with

Multiple toppling operations can be efficiently encoded by using the Laplacian matrix

, a matrix in

-space. Deleting the row and column of

corresponding with the sink yields the reduced Laplacian

. If

is a nonnegative integral vector indexed by the non-sink vertices, then starting with a configuration

and toppling each vertex

a total of

times yields the configuration

, where

is the contraction product.

This and other models that involve a toppling operation are sometimes referred to as chip-firing models or chip-firing games.

Sandpile group

Given a configuration

, toppling unstable non-sink vertices on a finite connected graph until no unstable non-sink vertex remains leads to a unique stable configuration

, which is called the stabilization of

The set of stable configurations forms a commutative monoid under the operation

. The minimal ideal of this monoid is a group of recurrent configurations called the sandpile group. A stable configuration is recurrent if it can be obtained from any other configuration by adding chips and stabilizing.

The sandpile group is isomorphic to the group of equivalence classes of configurations obtained by reducing modulo the toppling operation, which can be written

The order of the sandpile group is the determinant of

, which by the matrix tree theorem is the number of spanning trees of the graph.

Self-organized criticality

The original interest behind the model stemmed from the fact that in simulations on lattices, it is attracted to its critical state, at which point the correlation length of the system and the correlation time of the system go to infinity, without any fine tuning of a system parameter. This contrasts with earlier examples of critical phenomena, such as the phase transitions between solid and liquid, or liquid and gas, where the critical point can only be reached by precise tuning (e.g., of temperature). Hence, in the sandpile model we can say that the criticality is self-organized.

Once the sandpile model reaches its critical state there is no correlation between the system's response to a perturbation and the details of a perturbation. Generally this means that dropping another grain of sand onto the pile may cause nothing to happen, or it may cause the entire pile to collapse in a massive slide. The model also displays 1/ƒ noise, a feature common to many complex systems in nature.

This model only displays critical behaviour in two or more dimensions. The sandpile model can be expressed in 1D; however, instead of evolving to its critical state, the 1D sandpile model instead reaches a minimally stable state where every lattice site goes toward the critical slope.

For two dimensions, the associated conformal field theory is suggested to be symplectic fermions with central charge c = −2.^[3]

Generalization to directed graphs

The sandpile model can be generalized to arbitrary directed multigraphs. The rules are that any vertex

with

is unstable; toppling again sends chips to each of its neighbors, one along each outgoing edge:

In this case the Laplacian matrix is not symmetric. If we specify a sink

such that there is a path from every other vertex to

, then the stabilization operation on finite graphs is well-defined and the sandpile group can be written

The order of the sandpile group is again the determinant of

, which by the general version of the matrix tree theorem is the number of oriented spanning trees rooted at the sink.

Least action principle

The stabilization of chip configurations obeys a form of least action principle: each vertex topples no more than necessary in the course of the stabilization.^[4]

This can be formalized as follows. Call a sequence of topples legal if it only topples unstable vertices, and stabilizing if it results in a stable configuration. The standard way of stabilizing the sandpile is to find a maximal legal sequence; i.e., by toppling so long as it is possible. Such a sequence is obviously stabilizing, and the Abelian property of the sandpile is that all such sequences are equivalent up to permutation of the toppling order; that is, for any vertex

, the number of times

topples is the same in all legal stabilizing sequences. According to the least action principle, a minimal stabilizing sequence is also equivalent up to permutation of the toppling order to a legal (and still stabilizing) sequence. In particular, the configuration resulting from a minimal stabilizing sequence is the same as results from a maximal legal sequence.

More formally, if

is a vector such that

is the number of times the vertex

topples during the stabilization (via the toppling of unstable vertices) of a chip configuration

, and

is an integral vector (not necessarily non-negative) such that

is stable, then

for all vertices

The divisible sandpile

A strongly related model is the so called divisible sandpile model, introduced in ^[5]

, in which instead of a discrete amount of particles in each site

, there is a real number

representing the amount of mass on the site. In case such mass is negative, one can understand it as a hole. The topple occurs whenever a site has mass larger than 1, it topples the excess evenly between its neighbors, this means that if a site is full at time

, it will be full for all later times.

Cultural references

The Bak–Tang–Wiesenfeld sandpile was mentioned on the Numb3rs episode "Rampage," as mathematician Charlie Eppes explains to his colleagues a solution to a criminal investigation.

The computer game Hexplode is based around the Abelian sandpile model on a finite hexagonal grid where instead of random grain placement, grains are placed by players.

References

1. ^{{cite journal | author = Bak, P. |author2=Tang, C. |author3=Wiesenfeld, K. | year = 1987 | title = Self-organized criticality: an explanation of 1/ƒ noise | journal = Physical Review Letters | volume = 59 | issue = 4 | pages = 381–384 | doi = 10.1103/PhysRevLett.59.381| bibcode=1987PhRvL..59..381B | pmid=10035754}}
2. ^{{cite book | author = Holroyd, A. |author2=Levine, L. |author3=Mészáros, K. |author4=Peres, Y. |author5=Propp, J. |author6=Wilson, B. | year = 2008 | title = Chip-Firing and Rotor-Routing on Directed Graphs | journal = In and Out of Equilibrium 2 | volume = 60 | pages = 331–364 | doi = 10.1007/978-3-7643-8786-0_17| bibcode=1987PhRvL..59..381B|arxiv=0801.3306|isbn=978-3-7643-8785-3 }}
3. ^{{cite journal |author=S. Moghimi-Araghi |author2=M. A. Rajabpour |author3=S. Rouhani |title=Abelian Sandpile Model: a Conformal Field Theory Point of View |arxiv=cond-mat/0410434 |year=2004 |doi=10.1016/j.nuclphysb.2005.04.002 |volume=718|issue=3|journal=Nuclear Physics B|pages=362–370|bibcode = 2005NuPhB.718..362M }}
4. ^{{cite journal| author = Fey, A. |author2=Levine, L.|author3=Peres, Y.| year=2010| issn=0022-4715| journal=Journal of Statistical Physics| volume=138| number=1-3| doi=10.1007/s10955-009-9899-6| title=Growth Rates and Explosions in Sandpiles| pages=143–159|arxiv = 0901.3805 |bibcode = 2010JSP...138..143F }}
5. ^{{Cite journal|last=Levine|first=Lionel|last2=Peres|first2=Yuval|date=2008-10-29|title=Strong Spherical Asymptotics for Rotor-Router Aggregation and the Divisible Sandpile|journal=Potential Analysis|language=en|volume=30|issue=1|pages=1–27|doi=10.1007/s11118-008-9104-6|issn=0926-2601}}