A quorum sensing inspired algorithm for dynamic clustering

Feng Tan, Jean-Jacques E. Slotine

Abstract

This paper introduces a novel, decentralized clustering algorithm inspired by biological quorum sensing, where data points act like cells secreting "auto-inducers" to form colonies. Unlike traditional methods, this algorithm is formulated as a continuous dynamical system, allowing it to seamlessly cluster time-varying data in real-time. It bridges machine learning and control theory, showing strong performance on both static benchmarks and dynamic robotic swarm tracking.

Introduction

Clustering is a fundamental unsupervised learning task, but existing algorithms like K-means, DBSCAN, or Spectral Clustering suffer from several limitations. They often require a pre-defined number of clusters, struggle with varying densities or arbitrary shapes, and are highly sensitive to noise.

More importantly, traditional algorithms are discrete and uni-directional. For data that changes over time—such as moving robots in a swarm or streaming video pixels—standard approaches generally require rerunning the algorithm from scratch for every new frame, losing historical context. This work addresses these gaps by designing a flexible, continuous clustering algorithm that adapts to changing data on the fly without needing a hard reset.

Methodology

The authors look to biology for inspiration—specifically quorum sensing, the decentralized process bacteria use to coordinate behavior based on local population density.

The biological quorum sensing mechanism involving LuxI/LuxR and auto-inducers.

The algorithm treats every data point as a single "cell" and models the clustering process using a system of differential equations:

  1. Density Diffusion: Each cell secretes "auto-inducers" (modeled as a Gaussian kernel) to establish an "influence radius."
  2. Adaptive Radius Tuning: Cells dynamically tune their influence radius to maintain a target local density. If a cell is isolated, it casts a wider net; if it's in a dense crowd, it shrinks its radius. The authors use contraction analysis from control theory to prove this tuning process is mathematically stable.
  3. Colony Formation: When a cell's local density hits a specific threshold, it establishes a "colony."
  4. Colony Interaction: Colonies compete for members. The algorithm uses a cost function inspired by Normalized Cuts, implemented as a continuous dynamic system where colonies expand and inhibit one another until they reach an equilibrium.
  5. Merging and Splitting: The algorithm continuously monitors the ratio of inter-colony to intra-colony connections, fluidly merging or splitting groups as the underlying data shifts.

Key Results

The algorithm was evaluated across a remarkably diverse set of benchmarks, including synthetic data (two-moons, spirals), community detection networks (Karate club, E-mail contacts), and biological allele clustering.

Performance comparison of the proposed algorithm against standard clustering methods on static benchmarks.

As shown in the table above, the algorithm achieved 97.3% accuracy on the Iris dataset and 86.6% on Pendigits, outperforming or matching several state-of-the-art methods. In dynamic tracking tests, the algorithm successfully tracked 200 mobile robots in real-time, fluidly updating cluster assignments as the swarm merged and split.

Discussion and Insights

By formulating clustering as a set of differential equations, the algorithm naturally tracks moving data, allowing history to inform the current state. Because every data point dynamically tunes its own influence radius, the algorithm is scale-free and does not rely on a single global bandwidth parameter. This allows it to recognize both dense and sparse clusters simultaneously.

While the current implementation scales at $O(n^3)$ on a single processor, the authors note that the decentralized nature of the algorithm makes it highly suited for distributed hardware, where complexity drops to linear time per agent. Future work will focus on automatic parameter tuning and applications in video segmentation and object tracking.

Summary updated

BibTeX
@inproceedings{tan2013quorum,
  author = {Feng Tan and Jean-Jacques E. Slotine},
  title = {{A quorum sensing inspired algorithm for dynamic clustering}},
  booktitle = {CDC},
  year = {2013},
  doi = {10.1109/cdc.2013.6760733},
}
Figure