Detection of core–periphery structure in networks using spectral methods and geodesic paths

2014/10/31 by MIHAI CUCURINGU, Mihai Cucuringu, PUCK ROMBACH +5 · 66 citations
Computer Science · Mathematics · Physics and Astronomy · #Adjacency list #Adjacency matrix #Combinatorics #Complex Network Analysis Techniques #Computer science #Core (optical fiber) #Data Visualization and Analytics #Eigenvalues and eigenvectors #Geodesic #Geometry #Graph #Mathematics #Physics #Topological and Geometric Data Analysis #Topology (electrical circuits) #Vertex (graph theory) #cond-mat.dis-nn #cs.DM #cs.SI #math.CO #physics.soc-ph

paper · pdf · doi:10.1017/s095679251600022x

published in European Journal of Applied Mathematics 27(6), 846-887 (Cambridge University Press (CUP)) · This article is part of EJAM's December 2016 special issue on "Network Analysis and Modelling" (available at https://www.cambridge.org/core/journals/european-journal-of-applied-mathematics/issue/journal-ejm-volume-27-issue-6/D245C89CABF55DBF573BB412F7651ADB)

crossref issued 2016/08/03 · crossref published 2016/08/03 · crossref published-online 2016/08/03 · openalex publication_date 2016/08/03 · crossref created 2016/08/03 · arxiv created 2016/11/06 · arxiv updated 2016/11/08 · crossref published-print 2016/12/01 · crossref deposited 2024/06/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05 · crossref indexed 2026/08/07

Abstract

We introduce several novel and computationally efficient methods for detecting “core–periphery structure” in networks. Core–periphery structure is a type of mesoscale structure that consists of densely connected core vertices and sparsely connected peripheral vertices. Core vertices tend to be well-connected both among themselves and to peripheral vertices, which tend not to be well-connected to other vertices. Our first method, which is based on transportation in networks, aggregates information from many geodesic paths in a network and yields a score for each vertex that reflects the likelihood that that vertex is a core vertex. Our second method is based on a low-rank approximation of a network's adjacency matrix, which we express as a perturbation of a tensor-product matrix. Our third approach uses the bottom eigenvector of the random-walk Laplacian to infer a coreness score and a classification into core and peripheral vertices. We also design an objective function to (1) help classify vertices into core or peripheral vertices and (2) provide a goodness-of-fit criterion for classifications into core versus peripheral vertices. To examine the performance of our methods, we apply our algorithms to both synthetically generated networks and a variety of networks constructed from real-world data sets.

Citations

• Spectral graph theory [CBMS Conference on Recent Advances in Spectral Graph Theory held at California State University at Fresno, June 6 - 10. 1994]
• Community structure in social and biological networks
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Nonlinear Dimensionality Reduction by Locally Linear Embedding
• Performance of modularity maximization in practical contexts
• Models of core/periphery structures
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• Synchronization Reveals Topological Scales in Complex Networks
• Community detection in graphs
• Identification of influential spreaders in complex networks
• Dynamic reconfiguration of human brain networks during learning
• Uncovering the overlapping community structure of complex networks in nature and society
• Maps of random walks on complex networks reveal community structure
• The nested assembly of plant–animal mutualistic networks
• A faster algorithm for betweenness centrality*
• Temporal networks
• Diffusion maps
• Random Graphs
• Matrix Analysis
• On random graphs. I.

Cited by

• 子どものこころ・子どもの遊び(16)入所施設における虐待を受けた子どもの遊戯療法