Optimizing Source Selection in Social Sensing in the Presence of Influence Graphs

Huajie Shao, Shiguang Wang, Shen Li, Shuochao Yao, Yiran Zhao, Tanvir Amin, Tarek Abdelzaher, Lance Kaplan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper addresses the problem of choosing the right sources to solicit data from in sensing applications involving broadcast channels, such as those crowdsensing applications where sources share their observations on social media. The goal is to select sources such that expected fusion error is minimized. We assume that soliciting data from a source incurs a cost and that the cost budget is limited. Contrary to other formulations of this problem, we focus on the case where some sources influence others. Hence, asking a source to make a claim affects the behavior of other sources as well, according to an influence model. The paper makes two contributions. First, we develop an analytic model for estimating expected fusion error, given a particular influence graph and solution to the source selection problem. Second, we use that model to search for a solution that minimizes expected fusion error, formulating it as a zero-one integer non-linear programming (INLP) problem. To scale the approach, the paper further proposes a novel reliability-based pruning heuristic (RPH) and a similarity-based lossy estimation (SLE) algorithm that significantly reduce the complexity of the INLP algorithm at the cost of a modest approximation. The analytically computed expected fusion error is validated using both simulations and real-world data from Twitter, demonstrating a good match between analytic predictions and empirical measurements. It is also shown that our method outperforms baselines in terms of resulting fusion error.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE 37th International Conference on Distributed Computing Systems, ICDCS 2017
EditorsKisung Lee, Ling Liu
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1157-1167
Number of pages11
ISBN (Electronic)9781538617915
DOIs
StatePublished - Jul 13 2017
Event37th IEEE International Conference on Distributed Computing Systems, ICDCS 2017 - Atlanta, United States
Duration: Jun 5 2017Jun 8 2017

Publication series

NameProceedings - International Conference on Distributed Computing Systems

Other

Other37th IEEE International Conference on Distributed Computing Systems, ICDCS 2017
CountryUnited States
CityAtlanta
Period6/5/176/8/17

    Fingerprint

Keywords

  • Crowdsourcing
  • Expected fusion error
  • Similarity based lossy estimation (SLE) algorithm
  • Social sensing
  • Zero-one integer non-linear programming (INLP)

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

Shao, H., Wang, S., Li, S., Yao, S., Zhao, Y., Amin, T., Abdelzaher, T., & Kaplan, L. (2017). Optimizing Source Selection in Social Sensing in the Presence of Influence Graphs. In K. Lee, & L. Liu (Eds.), Proceedings - IEEE 37th International Conference on Distributed Computing Systems, ICDCS 2017 (pp. 1157-1167). [7980056] (Proceedings - International Conference on Distributed Computing Systems). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICDCS.2017.275