2014/10/31 by Mihai Cucuringu, Puck Rombach, Sang Hoon Lee +1
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 as European Journal of Applied Mathematics, Volume 27, Issue 6 (Network Analysis and Modelling) December 2016, pp. 846-887 · 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)
openalex publication_date 2016/08/03 · arxiv created 2016/11/06 · arxiv updated 2016/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.