Finding multiple core-periphery pairs in networks

With a core-periphery structure of networks, core nodes are densely interconnected, peripheral nodes are connected to core nodes to different extents, and peripheral nodes are sparsely interconnected. Core-periphery structure composed of a single core and periphery has been identified for various networks. However, analogous to the observation that many empirical networks are composed of densely interconnected groups of nodes, i.e., communities, a network may be better regarded as a collection of multiple cores and peripheries. We propose a scalable algorithm to detect multiple nonoverlapping groups of core-periphery structure in a network. We illustrate our algorithm using synthesized and empirical networks. For example, we find distinct core-periphery pairs with different political leanings in a network of political blogs and separation between international and domestic subnetworks of airports in some single countries in a worldwide airport network.

Figure 1

Schematic illustrations of the adjacency matrices of the networks generated by stochastic block models. The filled blocks correspond to the entries that are equal to 1 with probability ${\theta }_1$ and zero otherwise. The empty blocks correspond to the entries that are equal to 1 with probability ${\theta }_2$ (${\theta }_2<{\theta }_1$) and zero otherwise. The diagonal entries are always set to zero and shown as empty entries in the figure for the sake of simplicity. The dashed lines indicate the borders separating different blocks. The labels $(\mathit{c},\mathit{x})$ are also indicated at the top and left of the adjacency matrices. Label R represents a block of residual nodes. The networks are composed of (a) a single core-periphery pair, (b) two core-periphery pairs, (c) a single core-periphery pair and residual nodes, and (d) two core-periphery pairs and residual nodes. In all cases, we set $N=400$.

Figure 2

The VI values between the true and inferred core-periphery structure for the three algorithms. Rows S1, S2, S3, and S4 correspond to the networks with planted core-periphery structure shown in Figs. 1, 1, 1, and 1, respectively. The color of each cell indicates the VI value. The white cells are those for which we did not calculate the VI values, i.e., we only computed them for ${\theta }_1>{\theta }_2$.

Figure 3

Core-periphery structure of the karate club network detected by (a) the BE-KL algorithm, (b) the two-step algorithm, and (c) our algorithm. The filled and blank cells indicate $A_{ij}=1$ and $A_{ij}=0$, respectively. The solid lines indicate the partition into core-periphery pairs. The dashed lines indicate the partition into the core and periphery within a core-periphery pair. The color indicates the leaning of the members. The instructor (i.e., node 1) and president (i.e., node 34) are indicated by the arrows.

Figure 4

Density of edges of different types within core-periphery pairs detected in (a) the karate club network, (b) blog network, and (c) airport network. The dashed line indicates the edge density for the entire network, $p$.

Figure 5

Core-periphery structure of the blog network detected by (a) the BE-KL algorithm, (b) the two-step algorithm, and (c) our algorithm. The red and blue indicate the conservative and liberal blogs, respectively.

Figure 6

Core-periphery structure of the airport network detected by (a) the BE-KL algorithm, (b) the two-step algorithm, and (c) our algorithm. The color indicates the geographical region.

Figure 7

Location of the airports. The large and small filled circles represent the core and peripheral airports, respectively. Each color represents a core-periphery pair. The open squares represent residual airports.

Figure 8

Location of the airports in (a) Europe, (b) East Asia, and (c) the contiguous United States and their surrounding areas. The large and small filled circles represent the core and the peripheral airports, respectively. Each color represents a core-periphery pair. The open squares represent residual airports. The inverted triangles indicate the location of metropolises, i.e., the capital cities of all countries, the provincial capitals of China and the state capitals of the United States.

Figure 9

Airport network within (a) the Philippines and (b) Thailand. The line color indicates the core-periphery pair to which the two airports belong. The edges connecting two airports in different core-periphery pairs are shown in gray. The numbers attached to some airports indicate the IDs of the airports listed in Tables 2 and 3. We only show the IDs of all core airports, some peripheral airports and all residual airports.

Figure 10

The VI values between the true and inferred core-periphery structure obtained by the maximisation of $Q_{\text{config}}^{\text{cp}}$.

Figure 11

The VI values between the true and inferred core-periphery structure for the five algorithms. Panels (a) and (b) correspond to the networks whose structure is shown in Figs. 1 and 1, respectively. The error bars indicate the $\pm 1$ standard deviation.

Figure 12

The VI values between the true and inferred core-periphery structure for the divisive algorithm. Panels (a), (b), (c), and (d) show the VI values for the synthetic networks shown in Figs. 1, 1, 1, and 1, respectively.

Figure 13

Core-periphery structure identified by the divisive algorithm in (a) the karate club network, (b) blog network, and (c) airport network.

Figure 14

Airport network within (a) Iran, (b) Nigeria, (c) core-periphery pair 6 based in Alaska, (d) Ecuador, and (e) Russia. The line color indicates the core-periphery pair to which the two airports belong. The edges connecting two airports in different core-periphery pairs are shown in gray. The numbers attached to some airports indicate the IDs of the airports listed in Tables 5–9. We only show the IDs of the core airports, some peripheral airports and some residual airports.