Source-linked AI summary
Core-Periphery Structure in Networks
M. Puck Rombach, Mason A. Porter, James H. Fowler, Peter J. Mucha
TL;DR
Meso-scale network structures can reveal organization beyond local and global views, but research has focused predominantly on communities rather than core-periphery structure. The paper develops a flexible method that assigns continuous core scores or discrete core-periphery classifications while considering different possible cores. It shows that core-periphery analysis complements community detection and can reveal global infrastructure invisible to community-only analyses.
Problem
Research on meso-scale network structure has focused predominantly on communities, leaving core-periphery structure comparatively understudied despite its relevance across several fields.
Method
The paper develops a family of methods that evaluates different core possibilities and assigns either continuous core scores or discrete core-periphery classifications using flexible transition functions and core-quality measures.
Results
Core-periphery analysis reveals global infrastructure in network-scientist networks that remains invisible when searching only for community structure.
Takeaways & Limitations
Core-periphery and community structure can occur together, separately, or neither, making core-periphery analysis a complementary lens for meso-scale networks.
Takeaways & Limitations
The current implementation is slow because it uses simulated annealing, and two-parameter transition functions evaluate 10000 uniformly spaced parameter pairs.
Abstract
from arXiv · showhide
Intermediate-scale (or `meso-scale') structures in networks have received considerable attention, as the algorithmic detection of such structures makes it possible to discover network features that are not apparent either at the local scale of nodes and edges or at the global scale of summary statistics. Numerous types of meso-scale structures can occur in networks, but investigations of such features have focused predominantly on the identification and study of community structure. In this paper, we develop a new method to investigate the meso-scale feature known as core-periphery structure, which entails identifying densely-connected core nodes and sparsely-connected periphery nodes. In contrast to communities, the nodes in a core are also reasonably well-connected to those in the periphery. Our new method of computing core-periphery structure can identify multiple cores in a network and takes different possible cores into account. We illustrate the differences between our method and several existing methods for identifying which nodes belong to a core, and we use our technique to examine core-periphery structure in examples of friendship, collaboration, transportation, and voting networks.
1 Introduction
Network analysis uses meso-scale structures to reveal features that local node-and-edge views or global summary statistics may miss. This paper focuses on core-periphery structure, complementing the heavily studied community-structure perspective.
- Meso-scale structures provide an intermediate perspective for discovering network features not apparent at local or global scales.
- Community structure groups nodes densely internally while keeping connections between communities comparatively sparse.
- Compared with community structure, core-periphery structure has received fewer methods and less investigation despite longstanding use in sociology, international relations, and economics.
- Core-periphery structure identifies densely connected core nodes, sparsely connected peripheral nodes, and substantial core-periphery connections.
- Core-periphery and community structure can coexist or provide complementary views of meso-scale organization.
- High-degree hubs can complicate community detection because they may connect strongly to multiple communities and receive different assignments across heuristics.
2 Detecting Core-Periphery Structure
Existing approaches impose different notions of a network core, whereas the paper introduces a flexible method that evaluates multiple possible core sizes and shapes. The method uses transition functions and core-matrix choices to score candidate core assignments.
- Existing Methods: Existing approaches include block models, k-cores, connectivity and shortest-path measures, overlapping communities, knotty centrality, and random walkers.These methods capture different structural or centrality-based notions of core membership.
- Existing Methods: Borgatti and Everett’s continuous formulation assigns node coreness values and motivates the paper’s weighted, undirected-network method.Their MINRES heuristic can produce a vector resembling the adjacency matrix’s leading eigenvector.
- Existing Methods: A k-core is a maximal connected subgraph whose nodes each have degree at least k, but this imposes a strong restriction on what constitutes a core.The authors compare this restriction to requiring a community to be a clique.
- Our Method: The proposed method accounts for cores of different sizes and shapes, gives participating nodes credit weighted by associated core quality, and interpolates between core and periphery nodes.It defines core-matrix elements through a function of local core values and evaluates candidate core vectors by a core-quality objective.
- Our Method: The transition function controls how local core values vary across nodes: β controls core size, while α controls the score jump and can yield a discrete core-periphery classification.A one-parameter alternative can instead control core size, boundary sharpness, or both.
- Our Method: For each parameter setting, the method searches for a normalized shuffle of transition-generated core values that maximizes core quality, using simulated annealing in the examples.The examples sample α and β uniformly on a discretized unit square, while selective parameter choice is left for future work.
3 Synthetic Benchmark Networks
The paper benchmarks its core-periphery method on synthetic networks with imposed structure and on lattices without meaningful core-periphery structure. It compares aggregate core scores with several node-ranking methods and uses score distributions to assess whether apparent cores are meaningful.
- 3.1 Imposed Core-Periphery Structure: Synthetic CP(N,d,p,k) networks impose core-periphery structure with independently assigned edges and varying core-core, core-periphery, and periphery-periphery probabilities.The benchmark fixes N = 100, d = 1/2, and p = 1/4, averaging results over 100 instances for k = 1, 1.1, ..., 2.
- 3.1 Imposed Core-Periphery Structure: The benchmark compares aggregate core scores with closeness, degree, PageRank, geodesic node betweenness, and MINRES rankings.Each continuous ranking is evaluated by counting how many of the 50 constructed core nodes appear in the top 50.
- 3.2 Lattices: Lattices provide a negative-control network because their symmetry and equal degrees produce no meaningful core-periphery structure.Any node assignment to core or periphery is arbitrary under lattice symmetries.
- 3.1 Imposed Core-Periphery Structure: The method evaluates core-node recovery using aggregate core scores computed from core quality and a transition function.Figure 4 reports the fraction of core nodes correctly identified, averaged over 100 network realizations.
- 3.2 Lattices: Meaningful interpretation requires examining the distribution of core scores rather than their magnitude alone.The paper suggests visual inspection, variance, or centralization as ways to assess score concentration.
4 Real Networks
The paper applies its core-periphery method to friendship, transportation, collaboration, and voting networks, showing that networks can contain multiple, parameter-dependent cores alongside community structure.
- The Zachary Karate Club: The Zachary Karate Club network has different top-scoring cores for different α and β values.Node 34 is top about 74% of the time, whereas node 1 is top about 20%; node 1’s associated parameter settings have higher average core quality.
- The Zachary Karate Club: Role-equivalent karate-club nodes receive the same aggregate core score in the infinite-run limit.Nodes 15, 16, 19, 21, and 23 are automorphs whose labels can be swapped without changing network structure.
- The Zachary Karate Club: The core-quality landscape over α and β exposes multiple possible core-periphery structures in the karate-club network.The landscape can become complicated in larger networks, while the small karate-club network illustrates how the method operates.
- London Underground: The London Tube network separates into about 60 core stations and 257 peripheral stations based on a sharp aggregate-core-score jump.Core-periphery scores also distinguish peripheral stations that have the same degree centrality.
- Networks of Network Scientists: Network-scientist collaboration networks exhibit both community structure and core-periphery structure, with core nodes distributed across communities.In 2006, 12 of 19 communities contain a top-30 core node; in 2010, 9 of 25 do.
- Voting-Similarity Network: The Senate voting-similarity example shows that centrality measures capture different properties and that individual measures do not clearly separate political communities.Combinations of measures can sometimes distinguish mostly Republican and mostly Democratic communities, while aggregate core scores are relatively close together in this example.
5 Conclusions and Discussion
The paper introduces flexible methods for detecting core-periphery structure and argues that this analysis complements community detection. It also identifies implementation limitations and broader opportunities for studying meso-scale structure.
- The proposed method assigns nodes continuous core scores, while supporting both coreness centrality measures and discrete core-periphery divisions.It allows different transition functions and core-quality measures.
- Core-periphery analysis complements community detection because networks can contain either structure, both structures, or neither.In network-scientist collaboration networks, it reveals a global infrastructure invisible to community-only analysis.
- The current implementation is slow because it uses simulated annealing and evaluates 10000 uniformly spaced parameter pairs for two-parameter transition functions.The paper suggests fewer or more intelligently sampled parameter values and one-parameter functions as possible speed improvements.
- Further work should investigate how to choose core-matrix elements and alternative perspectives on core-periphery structure.
- The authors conclude that many networks contain meso-scale structures beyond community structure and that core-periphery structure merits further attention.
Simulated Annealing
The simulated-annealing implementation uses fixed temperature, cooling, rejection, trial, and success limits to search for core-periphery solutions.
- The implementation starts at temperature 1, ends at 10^-8, and cools by multiplying T by .8.The schedule uses T for the current temperature.
- The annealing procedure permits at most 1000 consecutive rejections, 300 tries at one temperature, and 20 successes at one temperature.
Network of Network Scientists
The network-scientist analysis reports aggregate core scores for the top nodes in 2006 and 2010 and compares alternative scoring specifications for 2010.
- Table 3 lists the 30 nodes with the highest aggregate core scores for the 2006 and 2010 network-scientist networks.The scores use core quality (10) and transition function (9).
Voting Similarities in the United States Senate
The Senate analysis reports senators’ aggregate core scores alongside the percentage of bills on which they voted with their political parties, using specified core-quality and transition functions.
- Table 5 lists senators in the 108th Congress with their aggregate core scores (11) and party-alignment voting percentages.
- The Senate core scores use core quality (10) and transition function (9).
- The supplied comparison materials also include alternative 2010 network-scientist computations using three transition-function and normalization specifications.