  A team of identical and oblivious ant-like agents - a(ge)nts - leaving
pheromone traces, are programmed to jointly patrol an area modeled as a graph.
They perform this task using simple local interactions, while also achieving
the important byproduct of partitioning the graph into roughly equal-sized
disjoint sub-graphs. Each a(ge)nt begins to operate at an arbitrary initial
location, and throughout its work does not acquire any information on either
the shape or size of the graph, or the number or whereabouts of other a(ge)nts.
Graph partitioning occurs spontaneously, as each of the a(ge)nts patrols and
expands its own pheromone-marked sub-graph, or region. This graph partitioning
algorithm is inspired by molecules hitting the borders of air filled elastic
balloons: an a(ge)nt that hits a border edge from the interior of its region
more frequently than an external a(ge)nt hits the same edge from an adjacent
vertex in the neighboring region, may conquer that adjacent vertex, expanding
its region at the expense of the neighbor. Since the rule of patrolling a
region ensures that each vertex is visited with a frequency inversely
proportional to the size of the region, in terms of vertex count, a smaller
region will effectively exert higher "pressure" at its borders, and conquer
adjacent vertices from a larger region, thereby increasing the smaller region
and shrinking the larger. The algorithm, therefore, tends to equalize the sizes
of the regions patrolled, resembling a set of perfectly elastic physical
balloons, confined to a closed volume and filled with an equal amount of air.
The pheromone based local interactions of agents eventually cause the system to
evolve into a partition that is close to balanced rather quickly, and if the
graph and the number of a(ge)nts remain unchanged, it is guaranteed that the
system settles into a stable and balanced partition.
