Density-based and transport-based core-periphery structures in networks

Networks often possess mesoscale structures, and studying them can yield insights into both structure and function. It is most common to study community structure, but numerous other types of mesoscale structures also exist. In this paper, we examine core-periphery structures based on both density and transport. In such structures, core network components are well-connected both among themselves and to peripheral components, which are not well-connected to anything. We examine core-periphery structures in a wide range of examples of transportation, social, and financial networks—including road networks in large urban areas, a rabbit warren, a dolphin social network, a European interbank network, and a migration network between counties in the United States. We illustrate that a recently developed transport-based notion of node coreness is very useful for characterizing transportation networks. We also generalize this notion to examine core versus peripheral edges, and we show that the resulting diagnostic is also useful for transportation networks. To examine the properties of transportation networks further, we develop a family of generative models of roadlike networks. We illustrate the effect of the dimensionality of the embedding space on transportation networks, and we demonstrate that the correlations between different measures of coreness can be very different for different types of networks.

Figure 1

The dolphin social network, for which we color (a) the nodes using CS values and (b) the nodes and edges using, respectively, node and edge PS values. The same color bar in (b) applies to both node and edge PS values. We show the dolphins' names in (a). In both panels, we position the nodes using a Kamada-Kawai force-directed graph drawing algorithm [42], for which we used the “graphviz_layout” function in the networkx package for python [43].

Figure 2

The maximum relatedness subnetwork (MRS) [55] of a European interbank network. We color the nodes and edges based on (a) CS and (b) $ln(\text{PS}+{10}^{-6})$ computed using the original (much denser) network. (We use a logarithm for visualization because of the heterogeneity of the PS values.) In (a), we identify the directions of edges using thick stubs to indicate arrowheads [56]. We also give the banks' codes in (a). The corresponding bank identities are listed in Ref. [53]. Different font colors represent different countries. In both panels, we position the nodes using a Kamada-Kawai force-directed graph drawing algorithm [42], for which we used the “graphviz_layout” function in the networkx package for python [43].

Figure 3

Core values for (a,b) normalized flow $\mathbf{W}$ and (c,d) raw flow ${\mathbf{W}}^{\mathrm{raw}}$ for migration between US counties. We color the counties according to their (a,c) CS values and (b,d) $ln(\text{PS}+{10}^{-6})$. We use the logarithm because of the heterogeneity in the PS values. We also indicate the state boundaries.

Figure 4

Visualization of the rabbit-warren network. An edge's thickness is linearly proportional to the mean width of the tunnel segment that it represents. (It is difficult to discern the differences in width, as the widths are rather homogeneous.) An edge's length is linearly proportional to its real length. We color (a) the nodes according to CS values, (b) the nodes and edges according to geodesic PS values, and (c) the nodes and edges according to GSNP values. We project the three-dimensional positions of nodes into a plane using a bird's-eye view. The labels “primary hub” and “secondary hub” were applied by experts [71], and the secondary hub was populated later in time than the primary one. (The term “primary” is not being used to indicate relative importance.)

Figure 5

Taxonomy of the 100 road networks and the rabbit warren using mesoscopic response functions (MRFs) based on community structure [25]. The vertical axis gives a “distance” measured from the MRFs. (This is analogous to a distance when studying phylogeny, so it indicates when different sets of networks diverge from each other in this taxonomy.) We set the threshold for assigning different colors to networks to be $40\%$ of the maximum distance (see the dashed horizontal line) determined from the MRFs.

Figure 6

A square sample (2 km $\times$ 2 km) of the road network in London. We color (a) the nodes based on their CS values, (b) the nodes and edges based on their geodesic PS values, and (c) the nodes and edges based on their GSNP values.

Figure 7

Examples of 2D and 3D roadlike networks produced from generative models. For the 2D example, we show (a) its nodes colored according to their CS values and (b) its nodes and edges colored according to their geodesic PS values. We show the 3D example projected into a plane, and we color (c) its nodes by their CS values and (d) its nodes and edges by their PS values. For these 3D networks, we add shortcuts greedily to make the mean path length as small as possible, and we note that the total length limit is twice the length of the minimum spanning tree (MST) determined from the initial node locations [78]. The edges in panels (c) and (d) that appear to cross are, of course, artifacts of projecting the 3D road network into a plane. For comparison, we also present (e) the CS values and (f) the PS values for a modified 2D null model in which crossed edges are allowed. In this null model, we use the same initial locations of nodes as in panels (a) and (b).