02/02/2021

Estimating the Number of Induced Subgraphs from Incomplete Data and Neighborhood Queries

Dimitris Fotakis, Thanasis Pittas, Stratis Skoulakis

Keywords:

Abstract Paper Similar Papers

Abstract: We consider a natural setting where network parameters are estimated from noisy and incomplete information about the network. More specifically, we investigate how we can efficiently estimate the number of small subgraphs (e.g., edges, triangles, etc.) based on full access to one or two noisy and incomplete samples of a large underlying network and on few queries revealing the neighborhood of carefully selected vertices. After specifying a random generator which removes edges from the underlying graph, we present estimators with strong provable performance guarantees, which exploit information from the noisy network samples and query a constant number of the most important vertices for the estimation. Our experimental evaluation shows that, in practice, a single noisy network sample and a couple of hundreds neighborhood queries suffice for accurately estimating the number of triangles in networks with millions of vertices and edges.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38949292
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 3:13 
 0
 0
 0
 0
 3:20 
 0
 0
 0
 0
 3:16 
 0
 0
 0
 0
 13:08 
 0
 0
 0
 0
 4:59 
 0
 0
 0
 0
 3:05 
 0
 0
 0
 0
 5:18 
 0
 0
 0
 0
 9:02 
 0
 0
 0
 0
 3:20 
 0
 0
 0
 0
 5:19 
 0
 0
 0
 0
 8:49 
 0
 0
 0
 0
 3:23 
 0
 0
 0
 0
 3:16 
 0
 0
 0
 0
 14:28 
 0
 0
 0
 0
 5:39 
 0
 0
 0
 0
 9:57 
 0
 0
 0
 0
 15:27 
 0
 0
 0
 0
 14:25 
 0
 0
 0
 0
 4:53 
 0
 0
 0
 0
 14:03 
 0
 0
 0
 0
 14:52 
 0
 0
 0
 0
 13:33 
 0
 0
 0
 0
 5:39 
 0
 0
 0
 0
 8:11 
 0
 0
 0
 0
 13:09 
 0
 0
 0
 0
 3:22 
 0
 0
 0
 0
 14:18 
 0
 0
 0
 0
 10:29 
 0
 0
 0
 0
 13:27 
 0
 0
 0
 0
 14:12 
 0
 0
 0
 0
 3:11 
 0
 0
 0
 0
 18:45 
 0
 0
 0
 0
 2:56 
 0
 0
 0
 0
 12:13 
 0
 0
 0
 0
 3:18 
 0
 0
 0
 0
 6:05 
 0
 0
 0
 0
 3:02 
 0
 0
 0
 0
 15:07 
 0
 0
 0
 1
 3:03 
 0
 0
 0
 0
 12:26