B1300
Title: Centrality measures for graphons
Authors: Marco Avella Medina - MIT (United States) [presenting]
Francesca Parise - MIT (United States)
Michael Schaub - MIT (United States)
Santiago Segarra - MIT (United States)
Abstract: Networks and graphs have become prevalent tools to represent systems across various scientific domains, as they provide a natural way to model and explain systems with pairwise interactions. In particular, node centrality measures have become of foremost importance in graph analysis for their ability to identify the most relevant agents and topological features in a network. The size of the networks under analysis has constantly increased in the last years and, consequently, graphons have been introduced as the natural limiting objects for graphs of increasing size. Formal definitions of centrality measures for graphons are introduced and their connections to centrality measures defined on finite graphs are established. In particular, we build on the theory of linear integral operators to define degree, eigenvector, and Katz centrality functions for graphons. We then establish concentration inequalities showing that these centrality functions are natural limits of their analogous counterparts defined on a sequence of random graphs of increasing size. We discuss how to compute our centrality measures as well as their stability towards noise. Our findings are illustrated through a set of detailed numerical examples.
