Vesdapunt, Norases and Garcia-Molina, Hector (2016) Updating an Existing Social Network Snapshot via a Limited API. Technical Report. Stanford InfoLab.
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)|
|Deposited By:||Norases Vesdapunt|
|Deposited On:||27 Jan 2016 23:23|
|Last Modified:||29 Jan 2016 00:43|
Available Versions of this Item
- Updating an Existing Social Network Snapshot via a Limited API. (deposited 27 Jan 2016 23:23) [Currently Displayed]
Repository Staff Only: item control page