Here’s an interesting question: how do you identify the most important junctions in a city? One way it is to measure the origin, route, and destination of each road trip through a city and then work out where they cross.

That’s never been possible in the past because this kind of data has always been hard to collect. But in recent years, the growing use of GPS navigating devices has changed all that.

Today, Ming Xu at Tsinghau University in Beijing and a few pals have collected the GPS data from hundreds of thousands of taxi journeys in Beijing and use it to do exactly this calculation. The result is a comprehensive map of the most important crossroads in Beijing, information that traffic planners could make good use of to keep the traffic flowing during roadworks, building projects, and so on.

Beijing has a population of more than 21 million people and its road traffic network is correspondingly huge. It contains 13,722 crossroads connected by over 25,000 roads. The network of roads in Beijing is dominated by four more or less concentric ring roads along with a number of arterial routes that head into the city center. To discover the most important of these crossroads, Ming and co used the routes taken by 10,000 taxicabs in Beijing during the month of October 2012.

This dataset consisted of each taxi’s GPS location sampled around once a minute. The team was particularly interested in the peak traffic conditions and so used only the data taken between 7:30 a.m. and 10 a.m. and between 5 p.m. and 7:30 p.m. This consisted of more than 500,000 fare-paying taxi trips between one location and another.

First, they mapped each of these trips onto a map of Beijing to determine the origin, route and destination of each. They also counted the number of crossroads traversed on each trip, a number that varied mainly between 7 and 18. That allowed the team to calculate things like the amount of traffic that passes through any given crossroads during the peak commuter period.

But then notion of an “important crossroad” is more subtle in Ming and co’s model of a city and they use a Pagerank-style algorithm to calculate this.

The Pagerank algorithm is Google’s famous method for ranking important webpages. It judges a webpage to be important if it is linked to by other important webpages. It works by a process of iteration, in which the importance of each webpage is calculated at every step and this is then used to update the calculation in the next step.

Ming and co use the same approach to rank the importance of crossroads. In their algorithm, called CRRANK, a crossroad is important if it is linked to by important roads. And roads are important if they link important crossroads. By iterating this algorithm, a ranking of important crossroads emerges.

The results clearly show which crossroads in Beijing are the most significant. The most important is called Deshengmen Bridge. It is the junction of the second ring road with the Badaling Expressway, near the Deshengmen city gate in the northern part of the city wall. It is well known as a major transportation mode.

The second is Xuanwumen Bridge in the southern part of the city and the former location of another gate in the city wall. It is also known as a major transportation hub.

The ranking lists over 100 important, with the most important being on the second ring road. It picks out important junctions on the third and fourth ring roads as well, which are further out. But the trend is that more important junctions tend to be nearer the center. “This is consistent with our daily experience,” say Ming and co.

Incidentally, the most important route is between Jinrong Street in the center of town and Beijing airport.

That’s an interesting way of ranking the importance of crossroads. Other groups have studied the network of roads within cities by creating a model of road traffic, and then removing nodes to see how the network performs without them. This simulates the crossroads becoming blocked by an accident, for example. That also reveals crucial junctions, some of which are so important that entire cities can come to a standstill when they become blocked.

The trouble with these earlier studies is that they have to be done with traffic flow simulations. But the availability of large amounts of high quality traffic data from real vehicles makes this kind of work much more valuable. There’s no reason now why these different approaches can’t be combined in future.

That should help when planning traffic flow during building works.

Nevertheless, the traffic in big cities has always been bad. Victorian commentators describe people running over the roofs of horse-drawn cabs in the traffic-jammed streets of 19th-century London. Any Londoners reading this will know that things haven’t improved much since then.

But with data like this and the ability to number crunch it effectively, perhaps it is reasonable hold out a small candle of hope that traffic jams will become a thing of the past. Then again, possibly not.

Ref: arxiv.org/abs/1407.2506 : Discovery of Important Crossroads in Road Network using Massive Taxi Trajectories