Max-node sampling: An expansion-densification algorithm for data collection

Katchaguy Areekijseree, Ricky Laishram, Sucheta Soundarajan

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

Abstract

In this work, we propose Max-Node sampling, a novel sampling algorithm for data collection. The goal of Max-Node is to maximize the number of nodes observed in the sample, given a budget constraint. Max-Node is based on the intuition that networks contain many densely connected regions (i.e., communities), that may be only weakly connected to another, and to maximize the number of nodes observed, it is critical to transition between communities. The two key phases of our algorithm are Expansion and Densification. The goal of the Expansion phase is to transition to unobserved regions, while the Densification phase aims to collect as many nodes in the current community. We conduct experiments on several real networks, and show an improvement of up to 40% vs. the baselines.

Original languageEnglish (US)
Title of host publicationProceedings - 2016 IEEE International Conference on Big Data, Big Data 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages3944-3946
Number of pages3
ISBN (Electronic)9781467390040
DOIs
StatePublished - Feb 2 2017
Event4th IEEE International Conference on Big Data, Big Data 2016 - Washington, United States
Duration: Dec 5 2016Dec 8 2016

Other

Other4th IEEE International Conference on Big Data, Big Data 2016
CountryUnited States
CityWashington
Period12/5/1612/8/16

Keywords

  • Algorithms
  • Complex Network
  • Data Collection
  • Data Crawling
  • Large Graph
  • Network Sampling

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Max-node sampling: An expansion-densification algorithm for data collection'. Together they form a unique fingerprint.

  • Cite this

    Areekijseree, K., Laishram, R., & Soundarajan, S. (2017). Max-node sampling: An expansion-densification algorithm for data collection. In Proceedings - 2016 IEEE International Conference on Big Data, Big Data 2016 (pp. 3944-3946). [7841070] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/BigData.2016.7841070