On the friendship paradox and inversity: A network property with applications to privacy-sensitive network...

We provide the mathematical and empirical foundations of the friendship paradox in networks, often stated as "Your friends have more friends than you." We prove a set of network properties on friends of friends and characterize the concepts of ego-based and alter-based means. We propose a network property called inversity that quantifies the imbalance in degrees across edges and prove that the sign of inversity determines the ordering between ego-based or alter-based means for any network, with implications for interventions. Network intervention problems like immunization benefit from using highly connected nodes. We characterize two intervention strategies based on the friendship paradox to obtain such nodes, with the alter-based and ego-based strategy. Both strategies provide provably guaranteed improvements for any network structure with variation in node degrees. We demonstrate that the proposed strategies obtain several-fold improvement (100-fold in some networks) in node degree relative to a random benchmark, for both generated and real networks. We evaluate how inversity informs which strategy works better based on network topology and show how network aggregation can alter inversity. We illustrate how the strategies can be used to control contagion of an epidemic spreading across a set of village networks, finding that these strategies require far fewer nodes to be immunized (less than 50%, relative to random). The interventions do not require knowledge of network structure, are privacy-sensitive, are flexible for time-sensitive action, and only require selected nodes to nominate network neighbors.