  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.
