What Do Your Friends Think? Efficient Polling Methods for Networks Using Friendship Paradox

Abstract

This paper deals with randomized polling of a social network. In the case of forecasting the outcome of an election between two candidates A and B, classical intent polling asks randomly sampled individuals: who will you vote for? Expectation polling asks: who do you think will win? In this paper, we propose a novel neighborhood expectation polling (NEP) strategy that asks randomly sampled individuals: what is your estimate of the fraction of votes for A? Therefore, in NEP, sampled individuals will naturally look at their neighbors (defined by the underlying social network graph) when answering this question. Hence, the mean squared error (MSE) of NEP methods rely on selecting the optimal set of samples from the network. To this end, we propose three NEP algorithms for the following cases: (i) the social network graph is not known but, random walks (sequential exploration) can be performed on the graph (ii) the social network graph is unknown. For case (i) and (ii), two algorithms based on a graph theoretic consequence called friendship paradox are proposed. Theoretical results on the dependence of the MSE of the algorithms on the properties of the network are established. Numerical results on real and synthetic data sets are provided to illustrate the performance of the algorithms.

Final version - accepted to IEEE Transactions on Knowledge and Data Engineering

References in corpus (7)

• The Majority Illusion in Social Networks
• Social Network Sensors for Early Detection of Contagious Outbreaks
• Tail-scope: Using friends to estimate heavy tails of degree distributions in large-scale complex networks
• Qualities and Inequalities in Online Social Networks through the Lens of the Generalized Friendship Paradox
• GEMSEC: Graph Embedding with Self Clustering
• Impact of perception models on friendship paradox and opinion formation
• Evaluating stochastic seeding strategies in networks

Cited by in corpus (2)

• Friendship Paradox Biases Perceptions in Directed Networks
• Echo Chambers and Segregation in Social Networks: Markov Bridge Models and Estimation