NDLI: Walking on a graph with a magnifying glass: stratified sampling via weighted random walks

Please wait, while we are loading the content...

Modeling program resource demand using inherent program characteristics

Stability analysis of QCN: the averaging principle

Soft error benchmarking of L2 caches with PARMA

On the power of (even a little) centralization in distributed processing

Structure-aware sampling on data streams

Optimal power cost management using stored energy in data centers

Slick packets

Walking on a graph with a magnifying glass: stratified sampling via weighted random walks

Characterizing and modeling internet traffic dynamics of cellular devices

Storage technologies, management and troubleshooting in virtualized datacenters

An FPGA-based experimental evaluation of microprocessor core error detection with Argus-2

METE: meeting end-to-end QoS in multicores through system-wide resource management

Stochastic networks with multipath flow control: impact of resource pools on flow-level performance and network congestion

Network architecture for joint failure recovery and traffic engineering

Weighted proportional allocation

Gossip PCA

Greening geographical load balancing

Geographic routing in d-dimensional spaces with guaranteed delivery and low stretch

Topology discovery of sparse random graphs with few participants

Cellular data network infrastructure characterization and implication on mobile content placement

Cloud data center networks: technologies, trends, and challenges

The role of KL divergence in anomaly detection

Studying inter-core data reuse in multicores

Analysis of DCTCP: stability, convergence, and fairness

Record and transplay: partial checkpointing for replay debugging across heterogeneous systems

On the optimal trade-off between SRPT and opportunistic scheduling

Model-driven optimization of opportunistic routing

Fine-grained latency and loss measurements in the presence of reordering

Building accurate workload models using Markovian arrival processes

Applying idealized lower-bound runtime models to understand inefficiencies in data-intensive computing

Studying the impact of hardware prefetching and bandwidth partitioning in chip-multiprocessors

On the stability and optimality of universal swarms

Non-asymptotic capacity and delay analysis of mobile wireless networks

How prevalent is content bundling in BitTorrent

Self-adaptive provisioning of virtualized resources in cloud computing

Characterizing and analyzing renewable energy driven data centers

Tight moments-based bounds for queueing systems

Scalable monitoring via threshold compression in a large operational 3G network

How do you 'Tube'

A control scheme for batching DRAM requests to improve power efficiency

Optimal neighbor selection in BitTorrent-like peer-to-peer networks

Towards understanding modern web traffic

De-ossifying internet routing through intrinsic support for end-network and ISP selfishness

Dynamic server provisioning to minimize cost in an IaaS cloud

HeteroScouts: hardware assist for OS scheduling in heterogeneous CMPs

Characterizing continuous-time random walks on dynamic networks

Autocorrelation analysis: a new and improved method for measuring branch predictability

IP geolocation in metropolitan areas

TCP behavior in sub packet regimes

Network link tomography and compressive sensing

Walking on a graph with a magnifying glass: stratified sampling via weighted random walks

Content Provider	ACM Digital Library
Author	Gjoka, Minas Butts, Carter T. Kurant, Maciej Markopoulou, Athina
Abstract	Our objective is to sample the node set of a large unknown graph via crawling, to accurately estimate a given metric of interest. We design a random walk on an appropriately defined weighted graph that achieves high efficiency by preferentially crawling those nodes and edges that convey greater information regarding the target metric. Our approach begins by employing the theory of stratification to find optimal node weights, for a given estimation problem, under an independence sampler. While optimal under independence sampling, these weights may be impractical under graph crawling due to constraints arising from the structure of the graph. Therefore, the edge weights for our random walk should be chosen so as to lead to an equilibrium distribution that strikes a balance between approximating the optimal weights under an independence sampler and achieving fast convergence. We propose a heuristic approach (stratified weighted random walk, or S-WRW) that achieves this goal, while using only limited information about the graph structure and the node properties. We evaluate our technique in simulation, and experimentally, by collecting a sample of Facebook college users. We show that S-WRW requires 13-15 times fewer samples than the simple re-weighted random walk (RW) to achieve the same estimation accuracy for a range of metrics.
Starting Page	281
Ending Page	292
Page Count	12
File Format	PDF MP4
ISBN	9781450308144
DOI	10.1145/1993744.1993773
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-06-07
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Stratified sampling Weighted graphs Weighted random walks Random walks Graph sampling Online social networks
Content Type	Audio Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Walking on a graph with a magnifying glass:stratified sampling via weighted random walks

Walking on a graph with a magnifying glass: stratified sampling via weighted random walks

Walking on a Graph with a Magnifying Glass: Stratified Sampling via Weighted Random Walks

Walking on a Graph with a Magnifying Glass: Stratified Sampling via Weighted Random Walks (2011)

A fast algorithm to find all high degree vertices in power law graphs

PageRank on an evolving graph

Unbiased Sampling of Bipartite Graph

Faster Random Walks by Rewiring Online Social Networks On-the-Fly

Coalescing Random Walks and Voting on Connected Graphs

Walking on a graph with a magnifying glass: stratified sampling via weighted random walks

Similar Documents

Walking on a graph with a magnifying glass:stratified sampling via weighted random walks

Walking on a graph with a magnifying glass: stratified sampling via weighted random walks

Walking on a Graph with a Magnifying Glass: Stratified Sampling via Weighted Random Walks

Walking on a Graph with a Magnifying Glass: Stratified Sampling via Weighted Random Walks (2011)

A fast algorithm to find all high degree vertices in power law graphs

PageRank on an evolving graph

Unbiased Sampling of Bipartite Graph

Faster Random Walks by Rewiring Online Social Networks On-the-Fly

Coalescing Random Walks and Voting on Connected Graphs

Walking on a graph with a magnifying glass: stratified sampling via weighted random walks