Stanford InfoLab Publication Server

Updating an Existing Social Network Snapshot via a Limited API

Vesdapunt, Norases and Garcia-Molina, Hector (2016) Updating an Existing Social Network Snapshot via a Limited API. Technical Report. Stanford InfoLab.


This is the latest version of this item.



We study the problem of graph tracking with limited information. In this paper, we focus on updating a social network snapshot. Say we have an existing partial snapshot of a network G1. Over time G1 becomes out of date. We want to update G1 through a public API, restricted by the number of API calls allowed. Periodically recrawling every node in the snapshot is prohibitively expensive. We propose a scheme where we exploit indegrees and outdegrees to discover changes to the graph. We probe the graph and verify edges when there is ambiguity. We propose a novel strategy designed for limited information that can be adapted to different levels of staleness. We evaluate our strategy against recrawling on real datasets and show that it saves an order of magnitude of API calls while introducing minimal errors.

Item Type:Techreport (Technical Report)
ID Code:1135
Deposited By:Norases Vesdapunt
Deposited On:05 Feb 2016 14:21
Last Modified:05 Feb 2016 14:21

Available Versions of this Item

Download statistics

Repository Staff Only: item control page