Blind Inference of Centrality Rankings from Graph Signals

We study the blind centrality ranking problem, where our goal is to infer the eigenvector centrality ranking of nodes solely from nodal observations, i.e., without information about the topology of the network. We formalize these nodal observations as graph signals and model them as the outputs of a network process on the underlying (unobserved) network. A simple spectral algorithm is proposed to estimate the leading eigenvector of the associated adjacency matrix, thus serving as a proxy for the centrality ranking. A finite rate performance analysis of the algorithm is provided, where we find a lower bound on the number of graph signals needed to correctly rank (with high probability) two nodes of interest. We then specialize our general analysis for the particular case of dense Erdös-Rényi graphs, where existing graph-theoretical results can be leveraged. Finally, we illustrate the proposed algorithm via numerical experiments on synthetic and real-world networks, with special emphasis on how the network features influence the performance.

1. INTRODUCTION

As the prevalence of complex, structured data has exploded in recent years, so has the analysis of such data using graph-based representations [1]–[3]. Indeed, abstracting relational structures as graphs has become an ever-increasing paradigm in science and engineering. In this context, network science aims to understand such structures, often via analysis of their algebraic properties when represented as matrices.