ϵ-WGX: Adaptive edge probing for enhancing incomplete networks

Sucheta Soundarajan, Brian Gallagher, Tina Eliassi-Rad, Ali Pinar

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

5 Scopus citations

Abstract

No matter how meticulously constructed, network datasets are often partially observed and incomplete. For example, most of the publicly available data from online social networking services (such as Facebook and Twitter) are collected via apps, users who make their accounts public, and/or the resources available to the researcher/practitioner. Such incompleteness can lead to inaccurate findings. We introduce the Adaptive Edge Probing problem. Suppose that one has observed a networked phenomenon via some form of sampling and has a budget to enhance the incomplete network by asking for additional information about specific nodes, with the ultimate goal of obtaining the most valuable information about the network as a whole. Which nodes should be further explored? We present e-WGX, a network-based explore-exploit algorithm for identifying which nodes in the incomplete network to probe. Aggregated over multiple datasets and a wide range of probing budgets, we find that e-WGX outperforms other explore-exploit strategies and baseline probing strategies. For example, for the task of adding as many nodes as possible, over incomplete networks observed via four popular sampling methods, e-WGX outperforms the best comparison strategy by 12%-23% on average.

Original languageEnglish (US)
Title of host publicationWebSci 2017 - Proceedings of the 2017 ACM Web Science Conference
PublisherAssociation for Computing Machinery, Inc
Pages161-170
Number of pages10
ISBN (Electronic)9781450348966
DOIs
StatePublished - Jun 25 2017
Event9th ACM Web Science Conference, WebSci 2017 - Troy, United States
Duration: Jun 25 2017Jun 28 2017

Other

Other9th ACM Web Science Conference, WebSci 2017
CountryUnited States
CityTroy
Period6/25/176/28/17

Keywords

  • Adaptive probing
  • Graph exploration
  • Incomplete networks

ASJC Scopus subject areas

  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'ϵ-WGX: Adaptive edge probing for enhancing incomplete networks'. Together they form a unique fingerprint.

  • Cite this

    Soundarajan, S., Gallagher, B., Eliassi-Rad, T., & Pinar, A. (2017). ϵ-WGX: Adaptive edge probing for enhancing incomplete networks. In WebSci 2017 - Proceedings of the 2017 ACM Web Science Conference (pp. 161-170). Association for Computing Machinery, Inc. https://doi.org/10.1145/3091478.3091492