Network formation models and traffic on networks
Network self-organization
Self-organized dynamics often leads to the organization of agents into networks. Examples of such networks are:
ant trails,
insect nests,
paths spontaneously generated by sheep or people in grassy areas,
paths marked in snow by white bears or montain hikers.
In all these cases, the interaction between the individuals is not direct, but instead, is mediated by a chemical substance or by the environment. Indeed:
ants lay down chemical markers (trail pheromones) as chemical markers ;
insects leave pellets of mud marked with a chemical marker (construction phreomone) ;
individual in displacement modify their environment and enhance the probability that followers will use the same path.
This phenomenon is referred to as stigmergy, a concept first forged by the entomologist Pierre-Paul Grassé.
The pictures (courtesy of G. Theraulaz) show an example of an ant trail network (top) and two examples of ant nest structures (middle and bottom).
A directed-pheromone deposition model
An Individual-Based Model of network generation by self-propelled particles has been developed. Each agent deposits directed pheromones and interacts with them through alignment interaction.
The directed pheromones consist of pairs of fixed positions and directions (corersponding to the agent's position and velocity direction at the moment of deposition). They model pieces of trails that the following agents will follow with a certain probability when they will cross them. Pheromones are deposited at random (Poisson) times and evaporate at a certain rate. Random changes in the direction of motion of the agents are also allowed.
The ant-pheromone interaction is modeled as follows (see picture): the ant looks around itself in a disk or radius R. With a certain probability, it picks up one of the pheromones in the disk and adopts its direction as new direction of motion.
The ant-pheromone interaction may be polar (the adopted orientation of motion is fixed by the orientation of the pheromone) or nematic (the adopted orientation of motion is such that the angle of direction change is acute). Nematic interaction is likely to be closer to the actual ant behavior.
Trail-network formation in the directed-pheromone deposition model
The top picture shows a typical outcome of the model. Two trails (identified by a clustering technique) have been highlighted in red and orange.
The middle picture displays the histogram of trail sizes, showing a large concentration of large trails which indicates the organization of the system into a network. By comparison, the distribution of trail sizes of a random distribution of ants would have an exponential decay.
The bottom picture presents the mean trail size as a function of the ant-pheromone interaction frequency. As the frequency is increased, the mean trail size shows a dramatic increase in less than a decade of values of the interaction frequency, indicating the occurrence of a phase transition from disorder to network order.
The formation of the network results from the positive feedback between the trail-laying behavior of the ants and the ant recruitment by the trails.
The following video shows a typical simulation outcome of the model (blue arrows are ants ; green arrows are pheromones).
Other videos can be found by following the links below. They display the dynamics of a colony where ants leave the nest located at the center of the domain, to harvest food. When they reach the boundary of the square computational domain, ants just leave. Nematic and polar interaction rules are compared (see previous section for the meaning of "nematic" and "polar").
Nematic interaction: we can notice the formation of closed paths.
Polar interaction: no closed paths are formed. More trails end up at the boundary.
Kinetic and macroscopic formulations of the model have also been investigated.
Applications of this model are also developped in cell biology, to model the formation of cell networks such as neural, vascular or stromal networks