Random walk is an important tool in many graph mining applications including estimating graph parameters, sampling portions of the graph, and extracting dense communities. In this paper we consider the problem of sampling nodes from a large graph according to a prescribed distribution by using random walk as the basic primitive. Our goal is to obtain algorithms that make a small number of queries to the graph but output a node that is sampled according to the prescribed distribution. Focusing on the uniform distribution case, we study the query complexity of three algorithms and show a near-tight bound expressed in terms of the parameters of the graph such as average degree and the mixing time. Both theoretically and empirically, we show that some algorithms are preferable in practice than the others. We also extend our study to the problem of sampling nodes according to some polynomial function of their degrees; this has implications for designing efficient algorithms for applications such as triangle counting.

On sampling nodes in a network / Dasgupta, Anirban; Kumar, Ravi; Lattanzi, Silvio; Sarlós, Tamás; Chierichetti, Flavio. - ELETTRONICO. - (2016). (Intervento presentato al convegno 25th International Conference on World Wide Web (WWW) tenutosi a Montreal, Canada) [10.1145/2872427.2883045].

On sampling nodes in a network

CHIERICHETTI, FLAVIO
2016

Abstract

Random walk is an important tool in many graph mining applications including estimating graph parameters, sampling portions of the graph, and extracting dense communities. In this paper we consider the problem of sampling nodes from a large graph according to a prescribed distribution by using random walk as the basic primitive. Our goal is to obtain algorithms that make a small number of queries to the graph but output a node that is sampled according to the prescribed distribution. Focusing on the uniform distribution case, we study the query complexity of three algorithms and show a near-tight bound expressed in terms of the parameters of the graph such as average degree and the mixing time. Both theoretically and empirically, we show that some algorithms are preferable in practice than the others. We also extend our study to the problem of sampling nodes according to some polynomial function of their degrees; this has implications for designing efficient algorithms for applications such as triangle counting.
2016
25th International Conference on World Wide Web (WWW)
Graph parameters; sampling node; network
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
On sampling nodes in a network / Dasgupta, Anirban; Kumar, Ravi; Lattanzi, Silvio; Sarlós, Tamás; Chierichetti, Flavio. - ELETTRONICO. - (2016). (Intervento presentato al convegno 25th International Conference on World Wide Web (WWW) tenutosi a Montreal, Canada) [10.1145/2872427.2883045].
File allegati a questo prodotto
File Dimensione Formato  
Chierichetti_Sampling-nodes.pdf

accesso aperto

Note: Paper
Tipologia: Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza: Creative commons
Dimensione 1.05 MB
Formato Adobe PDF
1.05 MB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/864747
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 49
  • ???jsp.display-item.citation.isi??? 45
social impact