Scaling in Biological and Social Networks - Abstract - Gastner

Workshop Navigation Home Agenda Abstracts Attendees Speakers Travel Information

The design of spatial distribution networks

Abstract:

We consider the problem of constructing facilities such as hospitals, airports, or malls, in a country with a non-uniform population density, such that the average distance from a person's home to the nearest facility is minimized. We review some previous approximate treatments of this problem which indicate that the optimal distribution of facilities should have a density that increases with population density, but does so slower than linearly, as the two-thirds power. We confirm this result numerically for the particular case of the United States with recent population data.

We also consider strategies for linking the facilities to form a spatial network, such as a network of flights between airports, so that the combined cost of maintenance of and travel on the network is minimized. We show specific examples of such optimal networks for the case of the United States.

While these networks are designed to optimize the social benefit, uncoordinated users pursuing their personally optimal routing strategies generally do not achieve the social optimum. Society, therefore, has to pay a "price of anarchy" for the lack of coordination among its members. In the last part of the talk, we give a quantitative assessment of this price of anarchy for the road networks of Boston, New York, and London. Our simulation shows that uncoordinated drivers possibly spend up to 30% more time than they would in socially optimized traffic. Contrary to common intuition, we also find that uncoordinated traffic can be partially improved by blocking certain streets.