Beyond the Web: PageRank and Predicting Traffic Flow in Cities
While the main application of PageRank is for ordering webpages for the purpose of web search, there are a variety of surprising applications of PageRank beyond just the internet. One incredibly interesting application is the use of PageRank to predict pedestrian and vehicular traffic flow through a city, as studied by Bin Jiang of The Hong Kong Polytechnic University.
On the surface, it might not seem that PageRank could be applied to physical spaces, but Jiang devised a system based on existing methods to turn a physical, top-down map of a city into a connected graph with nodes and edges by approximating city locations to axial lines that are connected to each other. Nodes in this graph represent a physical “space” in the city visible by a single person (for example, a block of a neighborhood or a park), and the arcs between spaces represent the ways in which a person can move directly from one space to another. As an example, Jiang provided a fictitious location and its graph counterpart, pictured below from left to right (with the intermediate axial map counterpart in between).
Jiang chose to focus on three central areas in London. After converting the three areas to graphs, Jiang executed the weighted PageRank algorithm. The weighted PageRank algorithm he used is a slightly modified version of the basic PageRank algorithm used in class; instead of PageRank being split equally among the nodes each node is linked to, more PageRank goes to the node or “space” that is more popular and has more links going into and out of it. While PageRank is also typically used on directed graphs, the graph analogous to a city layout is undirected; Jiang used PageRank on the undirected graph by treating each edge as going both ways. Spaces with higher PageRank were predicted to be more popular and receive more human traffic, and the edges with a lot of PageRank flowing through them also indicated heavier traffic through those routes.
Jiang used this model to model traffic in the three distinct areas in London he chose. The real-life data amounted to approximately 15,000 nodes and 50,000 edges in Jiang’s graph. He discovered that not only was human traffic correlated with his PageRank predictions, but also that the urban network of the central London locations displayed small-world network behavior by determining the clustering coefficients of the nodes in the graphs that corresponded to the real-world locations. This means that spaces showed high clustering coefficients (neighbors of a node were likely to also be neighbors of each other) and that one could move from space to space in the city with a relatively small number of steps.
In this way, Jiang was able to combine the use of PageRank and graph theory. He even discovered that PageRank predictions were more correlated with human and vehicular traffic in London than another popular ranking metric used at the time, called local integration, which used graph theory for social networks. PageRank predictions accounted for 60% of the actual behavior in cities that Jiang observed. With this information, city planners and transportation systems engineers can apply network traffic analysis in order to design cities with optimal layouts or reduce traffic time in congested areas, and business owners can determine the optimal locations in cities to open a new business so that they will get a lot of traffic. Jiang’s research and its far-reaching applications serve as an insightful example of the power of the PageRank algorithm and how it can be applied to areas outside the web.
Sources:
Jiang’s research: https://arxiv.org/pdf/physics/0612011.pdf
Purdue overview of Jiang’s research (page 335): https://www.cs.purdue.edu/homes/dgleich/publications/Gleich%202015%20-%20prbeyond.pdf