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

Buddhika Nettasinghe; Vikram Krishnamurthy

doi:10.1109/TKDE.2019.2940914

Back

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

Journal article

Open access

Peer reviewed

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

Buddhika Nettasinghe and Vikram Krishnamurthy

IEEE transactions on knowledge and data engineering, Vol.33(3), pp.1291-1305

03/01/2021

DOI: 10.1109/TKDE.2019.2940914

Files and links (1)

url

https://doi.org/10.1109/TKDE.2019.2940914View

Published (Version of record) Open Access

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 two 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, and (ii) the social network graph is unknown but, uniformly sampled nodes from the network are available. For both cases, 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.

Color

degree distribution

election forecasting

expectation polling

Forecasting

friendship paradox

graph sampling

Indexes

Opinion polling

Sampling methods

Simulation

Social networking (online)

social networks

social sampling

stochastic ordering

variance reduction

Voting

Details

Title: Subtitle: "What Do Your Friends Think?": Efficient Polling Methods for Networks Using Friendship Paradox
Creators: Buddhika Nettasinghe - Cornell University
Vikram Krishnamurthy - Cornell University
Resource Type: Journal article
Publication Details: IEEE transactions on knowledge and data engineering, Vol.33(3), pp.1291-1305
Publisher: IEEE
DOI: 10.1109/TKDE.2019.2940914
ISSN: 1041-4347
eISSN: 1558-2191
Grant note: 12346080; W911NF-19-1-0365 / Army Research Office (10.13039/100000183) 1714180 / National Science Foundation (10.13039/100000001) Army Research Laboratory (10.13039/100006754)
Language: English
Date published: 03/01/2021
Academic Unit: Business Analytics
Record Identifier: 9984422858302771

Metrics

22 Record Views

8 Times Cited - Web of Science

See more details