NDLI: Inference in OSNs via Lightweight Partial Crawls

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

Delay, Memory, and Messaging Tradeoffs in Distributed Service Systems

Generalized Threshold-Based Epidemics in Random Graphs: The Power of Extreme Values

A Better Model for Task Assignment in Server Farms: How Replication can Help

Costly Circuits, Submodular Schedules and Approximate Carathéodory Theorems

Optimizing TTL Caches under Heavy-Tailed Demands

Breathing Mankind Thoughts

Unsupervised Clustering Under Temporal Feature Volatility in Network Stack Fingerprinting

Rumor Source Obfuscation on Irregular Trees

Using Predictions in Online Optimization: Looking Forward with an Eye on the Past

On the Viability of a Cloud Virtual Service Provider

Instability in Distributed Mobility Management: Revisiting Configuration Management in 3G/4G Mobile Networks

On the Approximation Error of Mean-Field Models

Understanding Latency Variation in Modern DRAM Chips: Experimental Characterization, Analysis, and Optimization

A Service System with Randomly Behaving On-demand Agents

Optimal Heavy-Traffic Queue Length Scaling in an Incompletely Saturated Switch

Reverse Ranking by Graph Structure: Model and Scalable Algorithms

Reducing Latency Through Page-aware Management of Web Objects by Content Delivery Networks

Adaptive Caching Networks with Optimality Guarantees

Noisy Bloom Filters for Multi-Set Membership Testing

Inference in OSNs via Lightweight Partial Crawls

Collaborative Filtering with Low Regret

The Value of Privacy: Strategic Data Subjects, Incentive Mechanisms and Fundamental Limits

Transiently Secure Network Updates

On the Duration and Intensity of Competitions in Nonlinear Pólya Urn Processes with Fitness

Hash, Don't Cache (the Page Table)

An Analysis of Load Imbalance in Scale-out Data Serving

A Necessary and Sufficient Condition for Throughput Scalability of Fork and Join Networks with Blocking

Improved Achievability and Converse Bounds for Erdos-Renyi Graph Matching

Social Clicks: What and Who Gets Read on Twitter?

Achieving Low-Delay and Fast-Convergence in Stochastic Network Optimization: A Nesterovian Approach

Asymptotics of Insensitive Load Balancing and Blocking Phases

Exploiting Core Criticality for Enhanced GPU Performance

Analyzing the Power Consumption of the Mobile Page Load

Automated Test Location Selection For Cellular Network Upgrades

CAR: A Compression-Aware Refresh Approach to Improve Memory Performance and Energy Efficiency

Contrasting Effects of Replication in Parallel Systems: From Overload to Underload and Back

Explicit Back-off Rates for Achieving Target Throughputs in CSMA/CA Networks

Freestyle Dancing: Randomized Algorithms for Dynamic Storage Load-Balancing

Joint Data Purchasing and Data Placement in a Geo-Distributed Data Market

Majority Rule Based Opinion Dynamics with Biased and Stubborn Agents

Mean Field Equilibria of Pricing Games in Internet Marketplaces

Modeling SMR Drive Performance

Multipath Streaming: Fundamental Limits and Efficient Algorithms

Network Calculus Analysis of a Feedback System with Random Service

QoE Analysis of a Large-Scale Live Video Streaming Event

Safe Randomized Load-Balanced Switching by Diffusing Extra Loads

Searching For A Single Community in a Graph

Shoot for the Moon and You Will Never Miss: Characterizing and Detecting Aimbots in Online Games

Spatial Multi-LRU Caching for Wireless Networks with Coverage Overlaps

SSD Failures in Datacenters: What, When and Why?

The Power of d Choices for Redundancy

Time-Based Bandwidth Allocation for Heterogeneous Storage

Towards Multi-Resource Fair Allocation with Placement Constraints

Trading Discount for Reputation?: On the Design and Analysis of E-Commerce Discount Mechanisms

Inference in OSNs via Lightweight Partial Crawls

Content Provider	ACM Digital Library
Author	Ribeiro, Bruno Avrachenkov, Konstantin Sreedharan, Jithin K.
Abstract	Are Online Social Network (OSN) A users more likely to form friendships with those with similar attributes? Do users at an OSN B score content more favorably than OSN C users? Such questions frequently arise in the context of Social Network Analysis (SNA) but often crawling an OSN network via its Application Programming Interface (API) is the only way to gather data from a third party. To date, these partial API crawls are the majority of public datasets and the synonym of lack of statistical guarantees in incomplete-data comparisons, severely limiting SNA research progress. Using regenerative properties of the random walks, we propose estimation techniques based on short crawls that have proven statistical guarantees. Moreover, our short crawls can be implemented in massively distributed algorithms. We also provide an adaptive crawler that makes our method parameter-free, significantly improving our statistical guarantees. We then derive the Bayesian approximation of the posterior of the estimates, and in addition, obtain an estimator for the expected value of node and edge statistics in an equivalent configuration model or Chung-Lu random graph model of the given network (where nodes are connected randomly) and use it as a basis for testing null hypotheses. The theoretical results are supported with simulations on a variety of real-world networks.
Starting Page	165
Ending Page	177
Page Count	13
File Format	PDF
ISBN	9781450342667
DOI	10.1145/2896377.2901477
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-06-14
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Social network analysis Graph sampling Random walk on graphs Bayesian inference
Content Type	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

Inference in OSNs via Lightweight Partial Crawls

Bi-graph random walk sampling of directed online social networks

Bayesian Inference of Online Social Network Statistics via Lightweight Random Walk Crawls

Random walk-based graphical sampling in unbalanced heterogeneous bipartite social graphs

Analysis of Relaxation Time in Random Walk with Jumps

Analysis of Relaxation Time in Random Walk with Jumps

Walking in Facebook: A Case Study of Unbiased Sampling of OSNs (2010)

Walking in Facebook: A Case Study of Unbiased Sampling of OSNs (2010)

On random walk based graph sampling

Inference in OSNs via Lightweight Partial Crawls

Similar Documents

Inference in OSNs via Lightweight Partial Crawls

Bi-graph random walk sampling of directed online social networks

Bayesian Inference of Online Social Network Statistics via Lightweight Random Walk Crawls

Random walk-based graphical sampling in unbalanced heterogeneous bipartite social graphs

Analysis of Relaxation Time in Random Walk with Jumps

Analysis of Relaxation Time in Random Walk with Jumps

Walking in Facebook: A Case Study of Unbiased Sampling of OSNs (2010)

Walking in Facebook: A Case Study of Unbiased Sampling of OSNs (2010)

On random walk based graph sampling

Inference in OSNs via Lightweight Partial Crawls