[[ Check out my Wordpress blog Context/Earth for environmental and energy topics tied together in a semantic web framework ]]

Saturday, October 17, 2009

The Scaling Laws of Human Travel

I spotted a fairly recent-vintage paper on the statistics of human travel published in Nature magazine. This had the novelty of using the internet to collect indirect travel information by compiling the spread of money, via the bill tracking system http://www.whereisgeorge.com.

I can't argue the basic premise behind the approach. The authors, Brockmann, et all, assume that people disperse throughout a geographic region and make the claim that you can essentially track their motion (indirectly) by following the trajectory of the money they carry. They also make the correct interpretation that dispersion via random walk mechanisms plays a big role in the spread. That part seems quite reasonable. And the utility of understanding this phenomena holds great promise. For example, one can use it to understand the implications of reducing the travel overhead as we enter an energy-scarce era, as well as understanding the dynamics of pandemics. Yet, considering how important the concept is and the prestige of the journals that publish the work, they completely hose up the mathematics behind the phenomena. By that I mean they made the result horribly complex and opaque.

If they had used the correct formulation of dispersion, the agreements to their premise would have shown a very simple universality; yet they invoke some sophisticated notion of Levy flights and other esoteric models of stochastic mathematics to derive an overly complex result. Eventually they come up with a scaling law exponent which they affix with the value 0.59 and 1.05. They claim these odd numbers holds some notion of "universality" and claim that this results in some new form of "ambivalent" process. It seems a bit pretentious and I will use this post to derive some actual, much more practical, laws. For context, my own arguments use some of the same concepts that I have used for Dispersive Discovery of oil.

The statistics of what they want to model stems from sets of collected data from timestamped geographical locations. The figure below shows typical vector traces of travel across the USA.

Figure 1 : Typical bill travel traces due to Brockmann

The collected information appears very comprehensive and the fact that everyone uses money, attests to the fact that the approach should show little bias with minimal sample error. I don't have the data directly in my hands so some parts I may have misinterpreted, but so far so good.

We part company from that point. I don't really care to know the sophisticated random-walk model they use but it appears pretty much derived from the Scher-Montrose Continuous Time Random Walk (CTRW) model that I have looked at previously (see
http://mobjectivist.blogspot.com/2009/06/dispersive-transport.html and notice how that problem on a microscopic scale is similarly overly complicated)

Instead of overt formality, I would set up the mathematical premise straightforwardly. We have a dispersion of velocities described by a maximum entropy probability distribution function (PDF).
p(v) = alpha*e-alpha*v
The PDF above describes a mean velocity with a standard variance equal to the mean. This places all moments as finite values and becomes an intuitive minimally biased estimate considering no further information is available. We next assume that the actual distance traveled happens over a period of time.

The authors first describe a PDF of money traversing a distance r in less than 4 days.
p(r | t less than 4 days) = probability that the bill traveled r distance in less than 4 days
This becomes very easy to solve (if we assume that the distance traveled is uniformly distributed across the interval -- another maximum entropy estimator for that constraint). So for any one time, the cumulative distance traveled at any one time is expressed by the following cumulative distribution function (CDF), with r scaled as a distance:
P(r,t) = e-alpha*r/t
The term alpha has the units of time/distance. As we haven't considered the prospects of waiting time variation yet, this point provides a perfect place to add that to the mix. Intuitively, money does not constantly stay in motion, but instead may sit in a bank vault or a piggy bank for long periods of time. So we smear the term alpha again with a maximum entropy value.
p(alpha) = beta*e-beta*alpha
But we still have to integrate this over all smeared values, with respect to P(r,t). This gives the equation
P(r,t) = beta/(beta + x/t)
To generate the final PDF set, we take the derivative of this equation with respect to time, t, to get back the temporal PDF, and with respect to r, to get the spatial PDF (ignoring any radial density effects) .
dP/dt = beta*r/(beta*t+r)^2
dP/dr = beta*t/(beta*t+r)^2
So we can generate a PDF for r for a specific value of T=4 days and then fit the curve to a value for beta. So beta becomes the average velocity/waiting time for a piece of paper money (the bank note the authors refer to) between the times it makes trips from place to place. This approach only differs from the use of dispersion for oil discovery in the fact that velocity shows a greater dispersion than it would otherwise; the fact that time acts as the dispersive parameter and this goes in the denominator of velocity=r/t, implies that the fat tails appear in both the spatial dimension and the temporal dimension.

Figure 2: Contour profile in spatial/temporal dimensions for
dispersion of money. High levels and hot colors are high probability.

To verify the model, the authors plot the results in two orthogonal dimensions. First against time:
P(t | r less than 20 kilometers) = The probability that a bill has traveled 20 km or less in a set time.
The constrained curve fits are shown below with beta set to 1 kilometer per day. The various sets of data refer to 3 classes of initial entry locations (metropolitan areas, intermediate cities, and small towns).

Figure 3a and 3b: Profiles of probability along two orthogonal axis.
The red lines are fits for dispersion with beta = 1.

The short-distance spatial curve has some interesting characteristics. From the original paper, a plot of normalized probabilities shows relative invariance of distance traveled with respect to time for short durations of less than 10 days.

Figure 4: Contour profile from Brockmann.

Time appears bottle-necked for around 10 days on the average. This is understandable as the waiting time between transactions can contain 5 distinct stages. As most of these transactions may take a day or two at the minimum, it is easy to conceive that the total delay is close to T=10 days between updates to the bill reporting web site. So this turns into a weighted hop invariant to time but scaled to reflect the average distance that the money would actually travel.

Figure 5: Latency at short time intervals has to go through 5 processing steps.
This is similar to what occurs in oil processing, see here.

If we plot our theory on a similar color scale, it looks like the 2-dimensional profile below. :

Figure 6: Contour plot of scaled probability values.
This shows good agreement with the Brockmann data in Figure 4.

Note that these look different than the first contour color scale in Figure 2 since the authors multiplied the probability values by r to maintain a similar dynamic range across all values. Otherwise the probability values would diminish at large r or t.

Figure 7
: Alternate perspective of Figure 6. Note that the scaling by r
keeps the dynamic range intact, in comparison to Figure 2.

The bottom-line is that the actual model remains simple and both CTRW and the scaling-law exponent do not come into play. They also curiously called the process ambivalent (what the heck does that even mean?). I consider it the opposite of ambivalent and the solution remains rather straightforward. The authors Brockmann and company simply made a rookie mistake and did not consider Occam's razor, in that the simplest explanation works the best. Consider this par for the course when it comes to understanding dispersion.

As far as using the simple model for future policy decisions, I say why not. It essentially features a single parameter and covers the entire range of data. One can use it for modeling the propagation of infectious diseases (a depressing topic) and trying to minimize travel (an optimistic view).

I would almost say that case closed and problem solved, yet this is such a simple result that I have concerns I might have missed something. I definitely ignored the diffusional aspects and the possibility of random walk in 2-dimensions, yet I believe these largely get absorbed in the entropic smearing and the USA is not as much of a random two-dimensional stew as one may imagine. But as with all these simple dispersion arguments, I get the feeling that somehow this entire analysis approach has been unfortunately overlooked over the years.

  1. "The scaling laws of human travel", D. Brockmann, L. Hufnagel & T. Geisel, Nature, Vol 439|26, 2006.


Professor Blogger Dirk said...

Hi, this is very interesting. I'm Dirk Brockmann on of the authors. The concept that you introduce is well known, it's a superposition of exponentials that yield the power P(r,t) you describe. There's actually a number of models that can account for fig1 c,d in the manuscript that we published. I wonder what your alternative approach would say about the scaling function displayed in Fig. 2b. The problem is that in the bifraction diffusion velocities cannot be defined just as in ordinary diffusion although it is tempting to identify such velocities because the ratio of alpha/beta is almost unity. If you want we can discuss this more. Feel free to contact me any time. Cheers,

9:08 AM  
Professor Blogger WHT said...

If it is so well known then why doesn't anyone use the approach I describe?

These are not diffusion velocities, they are plain old velocities in getting from point A to B. Not my fault that people are barking up the wrong tree in trying to understand the problem. Occam's razor always wins in these kinds of problems.

9:41 PM  

Post a Comment

<< Home

"Like strange bulldogs sniffing each other's butts, you could sense wariness from both sides"