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

Katchaguy Areekijseree; Ricky Laishram; Sucheta Soundarajan

doi:10.1109/BigData.2016.7841070

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

Katchaguy Areekijseree, Ricky Laishram, Sucheta Soundarajan

Department of Electrical Engineering & Computer Science

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

1 Scopus citations

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 language	English (US)
Title of host publication	Proceedings - 2016 IEEE International Conference on Big Data, Big Data 2016
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	3944-3946
Number of pages	3
ISBN (Electronic)	9781467390040
DOIs	https://doi.org/10.1109/BigData.2016.7841070
State	Published - Feb 2 2017
Event	4th IEEE International Conference on Big Data, Big Data 2016 - Washington, United States Duration: Dec 5 2016 → Dec 8 2016

Other

Other	4th IEEE International Conference on Big Data, Big Data 2016
Country/Territory	United States
City	Washington
Period	12/5/16 → 12/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

Access to Document

10.1109/BigData.2016.7841070

Cite this

Max-node sampling: An expansion-densification algorithm for data collection. / Areekijseree, Katchaguy; Laishram, Ricky; Soundarajan, Sucheta.
Proceedings - 2016 IEEE International Conference on Big Data, Big Data 2016. Institute of Electrical and Electronics Engineers Inc., 2017. p. 3944-3946 7841070.

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

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., 7841070, Institute of Electrical and Electronics Engineers Inc., pp. 3944-3946, 4th IEEE International Conference on Big Data, Big Data 2016, Washington, United States, 12/5/16. https://doi.org/10.1109/BigData.2016.7841070

@inproceedings{80fa87a3ba97446d9d37b46f21a3a563,

title = "Max-node sampling: An expansion-densification algorithm for data collection",

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

keywords = "Algorithms, Complex Network, Data Collection, Data Crawling, Large Graph, Network Sampling",

author = "Katchaguy Areekijseree and Ricky Laishram and Sucheta Soundarajan",

year = "2017",

month = feb,

day = "2",

doi = "10.1109/BigData.2016.7841070",

language = "English (US)",

pages = "3944--3946",

booktitle = "Proceedings - 2016 IEEE International Conference on Big Data, Big Data 2016",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

note = "4th IEEE International Conference on Big Data, Big Data 2016 ; Conference date: 05-12-2016 Through 08-12-2016",

}

TY - GEN

T1 - Max-node sampling

T2 - 4th IEEE International Conference on Big Data, Big Data 2016

AU - Areekijseree, Katchaguy

AU - Laishram, Ricky

AU - Soundarajan, Sucheta

PY - 2017/2/2

Y1 - 2017/2/2

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

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

KW - Algorithms

KW - Complex Network

KW - Data Collection

KW - Data Crawling

KW - Large Graph

KW - Network Sampling

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

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

U2 - 10.1109/BigData.2016.7841070

DO - 10.1109/BigData.2016.7841070

M3 - Conference contribution

AN - SCOPUS:85015173935

SP - 3944

EP - 3946

BT - Proceedings - 2016 IEEE International Conference on Big Data, Big Data 2016

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 5 December 2016 through 8 December 2016

ER -

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

Abstract

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this