1 Search Results for "Verdugo, Victor"

Document

DOI: 10.4230/LIPIcs.DISC.2017.34

How Large Is Your Graph?

Authors: Varun Kanade, Frederik Mallmann-Trenn, and Victor Verdugo

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

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 pi uses O(1/||pi||_2 + d_avg) queries; we prove that this is tight. In addition, we establish this as a lower bound even when the algorithm is allowed to crawl the graph arbitrarily; the results of Katzir et al. give an upper bound that is worse by a multiplicative factor t_mix(1/n^4). The picture becomes significantly different in the case of directed graphs. We show that without strong assumptions on the graph structure, the number of nodes cannot be predicted to within a constant multiplicative factor without using a number of queries that are at least linear in the number of nodes; in particular, rapid mixing and small diameter, properties that most real-world networks exhibit, do not suffice. The question of interest is whether any algorithm can beat breadth-first search. We introduce a new parameter, generalising the well-studied conductance, such that if a suitable bound on it exists and is known to the algorithm, the number of queries required is sublinear in the number of edges; we show that this is tight.

Cite as

Varun Kanade, Frederik Mallmann-Trenn, and Victor Verdugo. How Large Is Your Graph?. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kanade_et_al:LIPIcs.DISC.2017.34,
  author =	{Kanade, Varun and Mallmann-Trenn, Frederik and Verdugo, Victor},
  title =	{{How Large Is Your Graph?}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{34:1--34:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.34},
  URN =		{urn:nbn:de:0030-drops-79767},
  doi =		{10.4230/LIPIcs.DISC.2017.34},
  annote =	{Keywords: Estimation, Random Walks, Social Networks}
}

Refine by Author
1 Kanade, Varun
1 Mallmann-Trenn, Frederik
1 Verdugo, Victor

Refine by Classification

Refine by Keyword
1 Estimation
1 Random Walks
1 Social Networks

Refine by Type
1 document

Refine by Publication Year
1 2017

1 Search Results for "Verdugo, Victor"

How Large Is Your Graph?

Abstract

Cite as

Thanks for your feedback!

Could not send message