Efficient Polling Algorithms using Friendship Paradox and Blackwell Dominance

摘要

This paper develops efficient polling algorithms that take into account the influence structure of the social network and can track a time-varying fraction of the population having a particular attribute. The proposed algorithms belong to the class of Neighborhood Expectation Polling (NEP) algorithms with two key differences in the sampling mechanism: (i) Friendship Paradox based sampling, (ii) Blackwell Dominance based sampling. NEP algorithm based on Friendship Paradox is provably more efficient, in terms of smaller mean square error, compared to the well known intent polling algorithm. NEP algorithm with Blackwell dominance is developed using a partially observed Markov decision process (POMDP) framework, and is provably (computationally) inexpensive to implement. The proposed methods can be viewed as a form of adaptive information fusion from querying nodes in a large graph.