Centrality in Normalized Stochastic Networks

Abstract

In many applications, network effects are normalized: in opinion dynamics, agents take a weighted average of their friends’ beliefs, or in social media models, users’ adoption decisions depends on the fraction of their peers who also adopt. The outcome of these processes share a common network property: a weighted Katz–Bonacich centrality but one defined over the network’s row-normalized adjacency matrix, which measures relative spillovers. This row-normalized centrality measure is well-understood in deterministic settings in which the full network structure is known, but in many instances, only probabilistic information about the network is available. We show that, under mild regularity conditions, the realized values of row-normalized centralities concentrate around their expectations, and this greatly simplifies the analysis of these stochastic networks. We use this result to further show that optimizing an objective over a stochastic network can be reduced to an optimization problem over an appropriately defined deterministic network. Together, these results yield a general and tractable approach for analyzing network processes and targeting problems in stochastic networks when spillovers are determined by normalized rather than raw connections. We demonstrate the usefulness of these techniques in applications to pricing, network games, and social dynamics.