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.| 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.
