Congestion and centrality in traffic flow on complex networks

The relation between centrality assessed from the static network structure measured in simulations of some simple traffic flow models has been discussed here. Routing communication along the shortest paths is of course beneficial for speed and economy, but if there is a limit to the vertex load and network traffic is heavy, congestion is a threat to central vertices.

Networks with power-law degree distribution and tunable clustering

To be able to monitor the traffic density as a function of betweenness we need networks with a broad betweenness distribution. This can be obtained by using scale-free networks as generated by the Barabasi-Albert (BA) model.

Particle hopping dynamics

Particle hopping is a widely used modeling technique in vehicular flow theory. In this approach a road is represented as a string of cells. These cells can be empty or occupied by exactly one particle. Modeling traffic flow by such a cellular automaton formalism is believed to give minimal models for the universal behaviors of traffic flow. To be able to compare different particle densities we use the number of updates divided with the number of particle as a time unit, i.e. one unit of time is the average number of iterations between the updates of one particle. The different dynamical updating rules for particle moves we consider are:

Random walk (RW)

In this case the particle choose an unoccupied neighbor site uniformly at random. If no unoccupied neighbors exists the particle rests.

Detour at obstacle (DO)

The particles chooses randomly among the neighbors closest to the target; it do jump even if the distance stays constant or increases.

Wait at obstacle (WO)

Like the DO case the particle starts by trying to get closer to the target. If no neighbor vertex closer to the target exists the particle rests. In this dynamics the particles necessarily travels along geodesics.

Relationship between congestion and betweenness centrality

This is a graph which shows the relationship between occupation time as a function of betweenness centrality.

Assuming that traffic-jams preferably are centered around vertices of high degree (that most likely have high betweenness), neighbours of high-degree vertices will also have a high occupation number. But since the degrees of neighboring vertices are uncorrelated this will give a constant contribution to the w(CB)-curves (CB is almost proportional to degree for the model networks in question).

Clustering does not only give more vertices of high betweenness, points with high betweenness have larger occupation ratios. During the off-peak hours the fastest routes are the shortest and goes through the largest streets, whereas during the rush hours an experienced driver can save minutes by navigating through back-alleys. In the dense limit, particles (as well as cars) are forced to make a detour around the traffic-jams.

In a congested traffic situation one can expect that a vertex is likely to be jammed if a neighbor is jammed. To test this we measure the w-W correlation coefficient, where W is the maximum occupation ratio of w’s neighbors (W(v) = max(u∈Γv) w(u)):

A positive value means that there is a positive correlation between w and W; i.e. if much traffic passes v then it is likely to have a neighbor with high occupation ratio (and vice versa). A large positive rwW would then support the idea that there are congestion centers in the network; and since a large w implies a large CB (more or less) it would support the intuitive idea that traffic jams are centered around vertices of high betweenness.

Summary and Conclusions

We have used particle hopping models adapted from vehicular traffic flow theory as minimal models for a communication systems that can be congested. To make the investigation of the influence of the underlying network structure on these dynamical systems, we need networks with (just as many real world communication networks) a wide spread in the betweenness distribution. This is obtained by using the BA model for scale-free networks.

High clustering slows down the dynamics, but does not lead to any qualitative change. The slowing down can be explained since higher clustering stretches the tail of the betweenness distribution, and high betweenness is likely to form congestion centers that slows down the dynamics. Even at very low particle concentrations, the picture from betweenness distribution changes. In particular vertices over a wide range of small and medium betweennesses all have quite constant occupation ratios.