On Source Dependency Models for Reliable Social Sensing: Algorithms and Fundamental Error Bounds

Shuochao Yao, Shaohan Hu, Shen Li, Yiran Zhao, Lu Su, Lance Kaplan, Aylin Yener, Tarek Abdelzaher

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

Abstract

This paper develops a simplified dependency model for sources on social networks that is shown to improve the quality of fact-finding - assessing veracity of observations shared on social media. Recent literature developed a mathematical approach for exploiting social networks, such as Twitter, as noisy sensor networks that report observations on the state of the physical world. It was shown that the quality of state estimation from such noisy data, known as fact-finding, was a function of assumptions made regarding the independence of sources or lack thereof. When sources propagate information they hear from others (without verification), correlated errors may arise that degrade fact-finding performance. This work advances the state of the art by developing a simplified model of dependencies between sources and designing an improved dependency-aware estimator to assess veracity of observations, taking into account the observed dependency structure. A fundamental error bound is derived for this estimator to understand the gap in its performance from optimal. It is shown that the new estimator outperforms state of the art fact-finders and, in some cases, yields an accuracy close to the fundamental error bound.

Original languageEnglish (US)
Title of host publicationProceedings - 2016 IEEE 36th International Conference on Distributed Computing Systems, ICDCS 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages467-476
Number of pages10
ISBN (Electronic)9781509014828
DOIs
StatePublished - Aug 8 2016
Event36th IEEE International Conference on Distributed Computing Systems, ICDCS 2016 - Nara, Japan
Duration: Jun 27 2016Jun 30 2016

Publication series

NameProceedings - International Conference on Distributed Computing Systems
Volume2016-August

Other

Other36th IEEE International Conference on Distributed Computing Systems, ICDCS 2016
CountryJapan
CityNara
Period6/27/166/30/16

    Fingerprint

Keywords

  • EM
  • Error Bound
  • Social Sensing
  • Source Dependency

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Software

Cite this

Yao, S., Hu, S., Li, S., Zhao, Y., Su, L., Kaplan, L., Yener, A., & Abdelzaher, T. (2016). On Source Dependency Models for Reliable Social Sensing: Algorithms and Fundamental Error Bounds. In Proceedings - 2016 IEEE 36th International Conference on Distributed Computing Systems, ICDCS 2016 (pp. 467-476). [7536545] (Proceedings - International Conference on Distributed Computing Systems; Vol. 2016-August). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICDCS.2016.75