Centrality measures for graphons: Accounting for uncertainty in networks

Abstract

As relational datasets modeled as graphs keep increasing in size and their data-acquisition is permeated by uncertainty, graph-based analysis techniques can become computationally and conceptually challenging. In particular, node centrality measures rely on the assumption that the graph is perfectly known -- a premise not necessarily fulfilled for large, uncertain networks. Accordingly, centrality measures may fail to faithfully extract the importance of nodes in the presence of uncertainty. To mitigate these problems, we suggest a statistical approach based on graphon theory: we introduce formal definitions of centrality measures for graphons and establish their connections to classical graph centrality measures. A key advantage of this approach is that centrality measures defined at the modeling level of graphons are inherently robust to stochastic variations of specific graph realizations. Using the theory of linear integral operators, we define degree, eigenvector, Katz and PageRank centrality functions for graphons and establish concentration inequalities demonstrating that graphon centrality functions arise naturally as limits of their counterparts defined on sequences of graphs of increasing size. The same concentration inequalities also provide high-probability bounds between the graphon centrality functions and the centrality measures on any sampled graph, thereby establishing a measure of uncertainty of the measured centrality score. The same concentration inequalities also provide high-probability bounds between the graphon centrality functions and the centrality measures on any sampled graph, thereby establishing a measure of uncertainty of the measured centrality score.

Authors ordered alphabetically, all authors contributed equally. 21 pages, 7 figures

References in corpus (4)

• Path lengths, correlations, and centrality in temporal networks
• Worldwide spreading of economic crisis
• The method of moments and degree distributions for network models
• Reducing Crowdsourcing to Graphon Estimation, Statistically

Cited by in corpus (14)

• Graphon Control of Large-scale Networks of Linear Systems
• Graphon Signal Processing
• Graphon Filters: Graph Signal Processing in the Limit
• Algebraic Neural Networks: Stability to Deformations
• Blind identification of stochastic block models from dynamical observations
• Blind Inference of Eigenvector Centrality Rankings
• Ergodicity in Stationary Graph Processes: A Weak Law of Large Numbers
• On Local Distributions in Graph Signal Processing
• Joint Network Topology Inference via a Shared Graphon Model
• EM-Based Smooth Graphon Estimation Using Bayesian and Spline-Based Approaches
• Individual based SIS models on (not so) dense large random networks
• Simulating systematic bias in attributed social networks and its effect on rankings of minority nodes
• Spectral Representations of Graphons in Very Large Network Systems Control
• The Shortest-Path distance on graphons