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

Author: 

Cucuringu, M
Rombach, P
Lee, S
Porter, M

Publication Date: 

December 2016

Journal: 

EUROPEAN JOURNAL OF APPLIED MATHEMATICS

Last Updated: 

2019-08-18T22:24:35.153+01:00

Issue: 

6

Volume: 

27

DOI: 

10.1017/S095679251600022X

page: 

846-887

abstract: 

© 2016 Cambridge University Press. 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.

Symplectic id: 

619110

Download URL: 

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article