Conference item icon

Conference item

Brief Announcement: How large is your graph?

Abstract:

We consider the problem of estimating the graph size, where one is given only local access to the graph. We formally define a query model in which one starts with a seed node and is allowed to make queries about neighbours of nodes that have already been seen. In the case of undirected graphs, an estimator of Katzir et al. (2014) based on a sample from the stationary distribution π uses O 1 kπk2 +davg queries; we prove that this is tight. In addition, we establish this as a lower bound even ...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted Manuscript

Actions


Access Document


Files:
Publisher copy:
10.1145/3087801.3087855

Authors


More by this author
Department:
Oxford, MPLS, Computer Science
Mallmann-Trenn, F More by this author
Verdugo, V More by this author
Publisher:
Association for Computing Machinery Publisher's website
Pages:
195-197
Publication date:
2017-07-25
Acceptance date:
2017-04-30
DOI:
Pubs id:
pubs:694269
URN:
uri:ffee6c86-4202-4e66-b0c8-bb22470eb71b
UUID:
uuid:ffee6c86-4202-4e66-b0c8-bb22470eb71b
Local pid:
pubs:694269
ISBN:
978-1-4503-4992-5

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP