MaxReach: Reducing network incompleteness through node probes

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

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

5 Citations (Scopus)

Abstract

Real-world network datasets are often incomplete. Subsequently, any analysis on such networks is likely to produce skewed results. We examine the following problem: given an incomplete network, which b nodes should be probed to bring as many new nodes as possible into the observed network? For instance, consider someone who has observed a portion (say 1%) of the Twitter network. How should she use a limited budget to reduce the incompleteness of the network? In this work, we propose a novel algorithm, called MAXREACH, which uses a budget b to increase the number of nodes in the observed network. Our experiments, across a range of datasets and conditions, demonstrate the efficacy of MAXREACH.

Original languageEnglish (US)
Title of host publicationProceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages152-157
Number of pages6
ISBN (Electronic)9781509028467
DOIs
StatePublished - Nov 21 2016
Event2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016 - San Francisco, United States
Duration: Aug 18 2016Aug 21 2016

Other

Other2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016
CountryUnited States
CitySan Francisco
Period8/18/168/21/16

Fingerprint

Experiments
budget
twitter
experiment

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Sociology and Political Science
  • Communication

Cite this

Soundarajan, S., Eliassi-Rad, T., Gallagher, B., & Pinar, A. (2016). MaxReach: Reducing network incompleteness through node probes. In Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016 (pp. 152-157). [7752227] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ASONAM.2016.7752227

MaxReach : Reducing network incompleteness through node probes. / Soundarajan, Sucheta; Eliassi-Rad, Tina; Gallagher, Brian; Pinar, Ali.

Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016. Institute of Electrical and Electronics Engineers Inc., 2016. p. 152-157 7752227.

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

Soundarajan, S, Eliassi-Rad, T, Gallagher, B & Pinar, A 2016, MaxReach: Reducing network incompleteness through node probes. in Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016., 7752227, Institute of Electrical and Electronics Engineers Inc., pp. 152-157, 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016, San Francisco, United States, 8/18/16. https://doi.org/10.1109/ASONAM.2016.7752227
Soundarajan S, Eliassi-Rad T, Gallagher B, Pinar A. MaxReach: Reducing network incompleteness through node probes. In Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016. Institute of Electrical and Electronics Engineers Inc. 2016. p. 152-157. 7752227 https://doi.org/10.1109/ASONAM.2016.7752227
Soundarajan, Sucheta ; Eliassi-Rad, Tina ; Gallagher, Brian ; Pinar, Ali. / MaxReach : Reducing network incompleteness through node probes. Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 152-157
@inproceedings{6ba2422104614bba85d42c565a1297d5,
title = "MaxReach: Reducing network incompleteness through node probes",
abstract = "Real-world network datasets are often incomplete. Subsequently, any analysis on such networks is likely to produce skewed results. We examine the following problem: given an incomplete network, which b nodes should be probed to bring as many new nodes as possible into the observed network? For instance, consider someone who has observed a portion (say 1{\%}) of the Twitter network. How should she use a limited budget to reduce the incompleteness of the network? In this work, we propose a novel algorithm, called MAXREACH, which uses a budget b to increase the number of nodes in the observed network. Our experiments, across a range of datasets and conditions, demonstrate the efficacy of MAXREACH.",
author = "Sucheta Soundarajan and Tina Eliassi-Rad and Brian Gallagher and Ali Pinar",
year = "2016",
month = "11",
day = "21",
doi = "10.1109/ASONAM.2016.7752227",
language = "English (US)",
pages = "152--157",
booktitle = "Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - GEN

T1 - MaxReach

T2 - Reducing network incompleteness through node probes

AU - Soundarajan, Sucheta

AU - Eliassi-Rad, Tina

AU - Gallagher, Brian

AU - Pinar, Ali

PY - 2016/11/21

Y1 - 2016/11/21

N2 - Real-world network datasets are often incomplete. Subsequently, any analysis on such networks is likely to produce skewed results. We examine the following problem: given an incomplete network, which b nodes should be probed to bring as many new nodes as possible into the observed network? For instance, consider someone who has observed a portion (say 1%) of the Twitter network. How should she use a limited budget to reduce the incompleteness of the network? In this work, we propose a novel algorithm, called MAXREACH, which uses a budget b to increase the number of nodes in the observed network. Our experiments, across a range of datasets and conditions, demonstrate the efficacy of MAXREACH.

AB - Real-world network datasets are often incomplete. Subsequently, any analysis on such networks is likely to produce skewed results. We examine the following problem: given an incomplete network, which b nodes should be probed to bring as many new nodes as possible into the observed network? For instance, consider someone who has observed a portion (say 1%) of the Twitter network. How should she use a limited budget to reduce the incompleteness of the network? In this work, we propose a novel algorithm, called MAXREACH, which uses a budget b to increase the number of nodes in the observed network. Our experiments, across a range of datasets and conditions, demonstrate the efficacy of MAXREACH.

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

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

U2 - 10.1109/ASONAM.2016.7752227

DO - 10.1109/ASONAM.2016.7752227

M3 - Conference contribution

AN - SCOPUS:85006791406

SP - 152

EP - 157

BT - Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016

PB - Institute of Electrical and Electronics Engineers Inc.

ER -