A popular technique to sample fixed-size connected induced subgraphs of a graph, also known as graphlets, is based on running a certain random walk designed over the space of all graphlets in the graph. This technique requires knowledge of the mixing time of the walk but, unfortunately, no satisfying bounds are known. In this paper we provide upper and lower bounds on such a mixing time, showing how it is intimately tied to the mixing time of the original graph, and to its maximum and minimum degree.

Mixing time bounds for graphlet random walks / Agostini, M.; Bressan, M.; Haddadan, S.. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - 152:(2019). [10.1016/j.ipl.2019.105851]

Mixing time bounds for graphlet random walks

Bressan M.
;
Haddadan S.
2019

Abstract

A popular technique to sample fixed-size connected induced subgraphs of a graph, also known as graphlets, is based on running a certain random walk designed over the space of all graphlets in the graph. This technique requires knowledge of the mixing time of the walk but, unfortunately, no satisfying bounds are known. In this paper we provide upper and lower bounds on such a mixing time, showing how it is intimately tied to the mixing time of the original graph, and to its maximum and minimum degree.
2019
graph algorithms; MCMC; motif mining; random walks
01 Pubblicazione su rivista::01a Articolo in rivista
Mixing time bounds for graphlet random walks / Agostini, M.; Bressan, M.; Haddadan, S.. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - 152:(2019). [10.1016/j.ipl.2019.105851]
File allegati a questo prodotto
File Dimensione Formato  
Agostini_Mixing_2019.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 248.26 kB
Formato Adobe PDF
248.26 kB Adobe PDF   Contatta l'autore

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/1313413
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 4
social impact