Core-periphery structure of networks

Core-periphery structure is a mesoscale structure of networks, where a core is a group of densely interconnected nodes, and a periphery is a group of sparsely interconnected nodes. Core-periphery structure has been found in various empirical networks such as social networks, biological networks and transportation networks [1, 2]. Many studies have assumed that networks consist of one core and one periphery. However, networks may contain multiple core-periphery pairs.

We developed an algorithm to find multiple core-periphery pairs in networks [3]. In the political blog network [4] shown in Fig. 1, the algorithm found two core-periphery pairs, each of which consists of the blogs sharing the same political agenda. We applied this algorithm or its variant to an inter-bank trade network [5], a maritime transportation network [6] and a short-text classification task [7].

We also showed that heterogeneous degree distributions alone explain single core-periphery structure [8]. In other words, when one says that a network is composed of a single core and a single periphery, hubs (i.e. nodes with large degrees, or the number of edges) are core nodes and nodes with small degrees are peripheral nodes. We proved that a core-periphery structure that is not merely explained by heterogeneous degree distributions necessarily involves at least three blocks of nodes. An example is a combination of a single core, a single periphery and a community, which yields three blocks. Another example is two core-periphery pairs, which yields four blocks in total. Based on this result, we extended our first algorithm [7] to find multiple core-periphery pairs in networks that are not merely explained by heterogeneous degree distributions [8]. The extended algorithm allows one to find small-degree core nodes and large-degree peripheral nodes.


Figure 1: Two core-periphery pairs in the political blog network detected by our algorithm. The filled or open circles indicate core nodes or peripheral nodes, respectively. The colour of each circle indicates the core-periphery pair to which the node belongs. The open circles with a grey border indicate nodes that do not belong to any core-periphery pair.