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 / M. Agostini, M. Bressan, S. Haddadan. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - 152:(2019). [10.1016/j.ipl.2019.105851]
Mixing time bounds for graphlet random walks
M. Bressan;
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 | |
|---|---|---|---|
|
2019-IPL.pdf
accesso aperto
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
248.19 kB
Formato
Adobe PDF
|
248.19 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
