ϵ-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 Citations (Scopus)

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

Fingerprint

Sampling
Application programs

Keywords

  • Adaptive probing
  • Graph exploration
  • Incomplete networks

ASJC Scopus subject areas

  • Computer Networks and Communications

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

ϵ-WGX : Adaptive edge probing for enhancing incomplete networks. / Soundarajan, Sucheta; Gallagher, Brian; Eliassi-Rad, Tina; Pinar, Ali.

WebSci 2017 - Proceedings of the 2017 ACM Web Science Conference. Association for Computing Machinery, Inc, 2017. p. 161-170.

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

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. Association for Computing Machinery, Inc, pp. 161-170, 9th ACM Web Science Conference, WebSci 2017, Troy, United States, 6/25/17. https://doi.org/10.1145/3091478.3091492
Soundarajan S, Gallagher B, Eliassi-Rad T, Pinar A. ϵ-WGX: Adaptive edge probing for enhancing incomplete networks. In WebSci 2017 - Proceedings of the 2017 ACM Web Science Conference. Association for Computing Machinery, Inc. 2017. p. 161-170 https://doi.org/10.1145/3091478.3091492
Soundarajan, Sucheta ; Gallagher, Brian ; Eliassi-Rad, Tina ; Pinar, Ali. / ϵ-WGX : Adaptive edge probing for enhancing incomplete networks. WebSci 2017 - Proceedings of the 2017 ACM Web Science Conference. Association for Computing Machinery, Inc, 2017. pp. 161-170
@inproceedings{9080c1581dd54aab9b33395aef6c7b7f,
title = "ϵ-WGX: Adaptive edge probing for enhancing incomplete networks",
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.",
keywords = "Adaptive probing, Graph exploration, Incomplete networks",
author = "Sucheta Soundarajan and Brian Gallagher and Tina Eliassi-Rad and Ali Pinar",
year = "2017",
month = "6",
day = "25",
doi = "10.1145/3091478.3091492",
language = "English (US)",
pages = "161--170",
booktitle = "WebSci 2017 - Proceedings of the 2017 ACM Web Science Conference",
publisher = "Association for Computing Machinery, Inc",

}

TY - GEN

T1 - ϵ-WGX

T2 - Adaptive edge probing for enhancing incomplete networks

AU - Soundarajan, Sucheta

AU - Gallagher, Brian

AU - Eliassi-Rad, Tina

AU - Pinar, Ali

PY - 2017/6/25

Y1 - 2017/6/25

N2 - 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.

AB - 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.

KW - Adaptive probing

KW - Graph exploration

KW - Incomplete networks

UR - http://www.scopus.com/inward/record.url?scp=85026781099&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85026781099&partnerID=8YFLogxK

U2 - 10.1145/3091478.3091492

DO - 10.1145/3091478.3091492

M3 - Conference contribution

AN - SCOPUS:85026781099

SP - 161

EP - 170

BT - WebSci 2017 - Proceedings of the 2017 ACM Web Science Conference

PB - Association for Computing Machinery, Inc

ER -