Research ArticleNETWORK SCIENCE

Lost in transportation: Information measures and cognitive limits in multilayer navigation

See allHide authors and affiliations

Science Advances  19 Feb 2016:
Vol. 2, no. 2, e1500445
DOI: 10.1126/sciadv.1500445
  • Fig. 1 Fastest and simplest paths in primal and dual networks.

    (A) In the primal network of the New York City (NYC) metropolitan system, a simplest path (light blue) from 125th Street on line 5 (dark green) to 121st Street on line J (brown) differs significantly from a fastest path (gray). There is only one connection for the above simplest path (Brooklyn Bridge–City Hall/Chambers Street) in Lower Manhattan. In contrast, the above fastest path needs three connections (5→F→E→J). We compute the duration of this path using travel times from the Metropolitan Transportation Authority (MTA) Data Feeds (see Materials and Methods). We neglect walking and waiting times. (B) In the dual space, nodes represent routes [where ACE, BDFM, and NQR are service names (49)], and edges represent connections. A “simplest path” in the primal space is defined as a shortest path with the minimal number of edges in the dual space (light-blue arrow). It has a length of C = 1 and occurs along the direct connection between line 5 (dark-green node) and line J (brown node). The above fastest path in the primal space has a length of C = 3 (gray arrows) in the dual space, as one has to change lines three times. [We extracted the schematic of the NYC metropolitan system from a map that is publicly available on Wikimedia Commons (45).]

  • Fig. 2 Information threshold.

    (A) Cumulative distribution of the information needed to encode trips with two connections in the 15 largest metropolitan networks. The largest value occurs for the NYC metropolitan system (red solid curve), which has trips with a maximum of Smax ≈ 8.1 bits. Among the 15 networks, the Hong Kong (red dashed curve) and Beijing (black solid curve) metropolitan networks have the smallest number of total connections and need the smallest amount of information for navigation. The Paris MRT (Metropolitan, Light Rail, and Tramway) network (orange dashed-dotted curve) from the official metro map (33) includes three transportation modes (which are managed by two different companies) and reaches values that are similar to those for the (larger) NYC metropolitan system. (B) Information threshold versus total number of connections in the dual space. This plot illustrates that the average amount of information needed to encode trips with two connections is strongly correlated with the total number of connections in the dual network, as can be predicted for a square lattice (see Materials and Methods). See table S1 for the definitions of the abbreviations. The color code is the same as in (A), and the red solid line represents the square-lattice result Embedded Image. This relationship permits one to associate the information threshold Smax with the cognitive threshold Embedded Image, which one can interpret as the maximum number T of intraroute connections that can be represented on a map.

  • Fig. 3 Primal (left) and dual (right) networks for a square lattice.

    In this example, the lattice has N = 8 routes. Each route has k = N/2 = 4 connections, so the total number of connections is Ktot = k2 = 16. In the dual network, the four east–west routes (A to D) and the four north–south routes (E to H) yield a graph with a diameter of 2.

  • Fig. 4 Information entropy of multilayer networks.

    The solid curves represent the cumulative distributions of Embedded Image for multilayer networks that include a metro layer for NYC, Paris, and Tokyo. (We associate one layer with bus routes and another layer with metro lines.) Most of the trips require more information than the cognitive limit Smax ≈ 8.1. The fractions of trips under this threshold are as follows: 15.6% for NYC, 10.7% for Paris, and 16.6% for Tokyo. The dashed curves are associated with all possible paths in a metro layer. In this case, the amount of information is always under the threshold, except for Paris, which includes trips with C = 3 (see table S3). Note that the threshold value lies in a relatively stable part of all three cumulative distributions, suggesting that our results are robust with respect to small variations of the threshold.

Supplementary Materials

  • Supplementary material for this article is available at http://advances.sciencemag.org/cgi/content/full/2/2/e1500445/DC1

    Table S1. Network characteristics of the largest connected component for the 15 largest metropolitan systems in the world.

    Table S2. Network characteristics of the Bus-Metro multilayer networks.

    Table S3. Structure of the simplest paths in three metropolitan systems.

    Table S4. Percentages of paths with Formula with C = 1 and C = 2 connections.

    Fig. S1. Examples of paths with growing Formula.

    Fig. S2. Entropy distribution for MRT layer, bus layer, and complete multilayer transportation network in Paris.

    Fig. S3. Effects of multiplexity.

    Fig. S4. Growth of the Paris metropolitan network.

    Fig. S5. Information entropy of multilayer transportation networks.

    Fig. S6. Dual-space degree of low-information starting points for paths with C = 2 in the Tokyo multilayer network.

    Fig. S7. Empirical validation of Eq. 7.

  • Supplementary Materials

    This PDF file includes:

    • Table S1. Network characteristics of the largest connected component for the 15
      largest metropolitan systems in the world.
    • Table S2. Network characteristics of the Bus-Metro multilayer networks.
    • Table S3. Structure of the simplest paths in three metropolitan systems.
    • Table S4. Percentages of paths with S < 8.1 bits with C = 1 and C = 2
      connections.
    • Fig. S1. Examples of paths with growing S (s, t).
    • Fig. S2. Entropy distribution for MRT layer, bus layer, and complete multilayer
      transportation network in Paris.
    • Fig. S3. Effects of multiplexity.
    • Fig. S4. Growth of the Paris metropolitan network.
    • Fig. S5. Information entropy of multilayer transportation networks.
    • Fig. S6. Dual-space degree of low-information starting points for paths with C = 2
      in the Tokyo multilayer network.
    • Fig. S7. Empirical validation of Eq. 7.

    Download PDF

    Files in this Data Supplement:

Navigate This Article