MaxReach: Reducing network incompleteness through node probes

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

doi:10.1109/ASONAM.2016.7752227

MaxReach: Reducing network incompleteness through node probes

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

Department of Electrical Engineering & Computer Science

Research output: Chapter in Book/Entry/Poem › Conference contribution

12 Scopus citations

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 language	English (US)
Title of host publication	Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016
Editors	Ravi Kumar, James Caverlee, Hanghang Tong
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	152-157
Number of pages	6
ISBN (Electronic)	9781509028467
DOIs	https://doi.org/10.1109/ASONAM.2016.7752227
State	Published - Nov 21 2016
Event	2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016 - San Francisco, United States Duration: Aug 18 2016 → Aug 21 2016

Publication series

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

Other

Other	2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016
Country/Territory	United States
City	San Francisco
Period	8/18/16 → 8/21/16

ASJC Scopus subject areas

Computer Networks and Communications
Sociology and Political Science
Communication

Access to Document

10.1109/ASONAM.2016.7752227

Cite this

Soundarajan, S., Eliassi-Rad, T., Gallagher, B., & Pinar, A. (2016). MaxReach: Reducing network incompleteness through node probes. In R. Kumar, J. Caverlee, & H. Tong (Eds.), Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016 (pp. 152-157). Article 7752227 (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.. https://doi.org/10.1109/ASONAM.2016.7752227

MaxReach: Reducing network incompleteness through node probes. / Soundarajan, Sucheta; Eliassi-Rad, Tina; Gallagher, Brian et al.
Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016. ed. / Ravi Kumar; James Caverlee; Hanghang Tong. Institute of Electrical and Electronics Engineers Inc., 2016. p. 152-157 7752227 (Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016).

Research output: Chapter in Book/Entry/Poem › Conference contribution

Soundarajan, S, Eliassi-Rad, T, Gallagher, B & Pinar, A 2016, MaxReach: Reducing network incompleteness through node probes. in R Kumar, J Caverlee & H Tong (eds), Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016., 7752227, 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., 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 Kumar R, Caverlee J, Tong H, editors, 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. (Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016). doi: 10.1109/ASONAM.2016.7752227

Soundarajan, Sucheta ; Eliassi-Rad, Tina ; Gallagher, Brian et al. / 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. editor / Ravi Kumar ; James Caverlee ; Hanghang Tong. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 152-157 (Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016).

@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",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016 ; Conference date: 18-08-2016 Through 21-08-2016",

year = "2016",

month = nov,

day = "21",

doi = "10.1109/ASONAM.2016.7752227",

language = "English (US)",

series = "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.",

pages = "152--157",

editor = "Ravi Kumar and James Caverlee and Hanghang Tong",

booktitle = "Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016",

}

TY - GEN

T1 - MaxReach

T2 - 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016

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

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

SP - 152

EP - 157

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

A2 - Kumar, Ravi

A2 - Caverlee, James

A2 - Tong, Hanghang

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 18 August 2016 through 21 August 2016

ER -

MaxReach: Reducing network incompleteness through node probes

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this