The Theory

Motivation of SALR clustering comes from the fundamental physics of modeling classical Wigner crystals¹ and modeling the formation of clusters^2,3. This page goes over the theoretical model driving the particle dynamics, and then discusses how/why/when SALR clustering is able to perform better than other clustering/seed-point detection methods.

How the particles are modeled

A set of N interacting charge particles can be described by the Hamiltonian (1), where m, p, r, and q represent the mass, momentum, position, and charge of a particle, and |r_i - r_j| is the distance between r_i and r_j. V is the confining potential, and V_int is the short-range attractive long-range repulsive (SALR) interaction potential created with a Gaussian attractive term and a 1/r repulsive term, given by (2). An example of what this potential looks like is shown in the figure. The values A, µ, and σ in (2) are set implicitly by giving the potential depth, d_o; the location of the potential minimum, r_o; and the location at which the potential switches from being attractive to repulsive, referred to as the attractive extent, r_a.

The equations actually describing the motion of the particles can be found from the Hamiltonian, and are given by (3) and (4). And extra term has been added to (3), -α(t) / m_i · p_i, that does not come from the Hamiltonian; this term slows the particles down over time so that they eventually come to a stop.

Equations (3) and (4) give a set of 2N differential equations that are modeled until the solution converges. The solution is said to converge when the average particle speed over the last few solution steps is below a pre-defined threshold.

How, why, and when SALR clustering works?

The answer comes by analyzing the force on the particles in the simulation: the confining potential puts a force on the particles with a magnitude of |∇V| (which is the slope of the confining potential, like a ball rolling down a hill), and the particles repel each other with a force of about r_a^-2. If the force from the confining potential is much larger than the repulsive force, |∇V|≫r_a^-2, then the particles will only find the local minimum of the confining potential—this is what most/all other methods do in finding the local extrema of a voting landscape or finding the local maxima of the point density (mean-shift¹). Alternatively, if the repulsive force is much larger than the confining force, r_a^-2≫|∇V|, then the particles will ignore the confining potential minima and spread out as far apart from each other as possible—this will result is clusters of particles, separated by at least a distance r_a, that uniformly cover the region. In between these two regimes, when the two forces are approximately the same order of magnitude, |∇V|~r_a^-2, there is an interaction between the confining potential and the particle repulsion, and this is the regime that leads to SALR clustering’s improved performance. J. Kapaldo et al., (submitted)²

For additional details, please consult the publication ²