Updating an Existing Social Network Snapshot via a Limited API

Abstract

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.

Available Versions of this Item

• Updating an Existing Social Network Snapshot via a Limited API. (deposited 27 Jan 2016 23:23)
  • Updating an Existing Social Network Snapshot via a Limited API. (deposited 29 Jan 2016 00:43) [Currently Displayed]
    • Updating an Existing Social Network Snapshot via a Limited API. (deposited 05 Feb 2016 14:21)