We consider information diffusion on Web-like networks and how random walks can simulate it. A well-studied problem in this domain is Partial Cover Time, i.e., the calculation of the expected number of steps a random walker needs to visit a given fraction of the nodes of the network. We notice that some of the fastest solutions in fact require that nodes have perfect knowledge of the degree distribution of their neighbors, which in many practical cases is not obtainable, e.g., for privacy reasons. We thus introduce a version of the Cover problem that considers such limitations: Partial Cover Time with Budget. The budget is a limit on the number of neighbors that can be inspected for their degree; we have adapted optimal random walks strategies from the literature to operate under such budget. Our solution is called Min-degree (MD) and, essentially, it biases random walkers towards visiting peripheral areas of the network first. Extensive benchmarking on six real datasets proves that the - perhaps counter-intuitive strategy - MD strategy is in fact highly competitive wrt. state-of-the-art algorithms for cover.
Exploring Low-degree nodes first accelerates Network Exploration / S. Costantini, P. De Meo, A. Giorgianni, V. Migliorato, A. Provetti, F. Salvia - In: WebSci '20[s.l] : ACM, 2020. - ISBN 9781450379892. - pp. 241-249 (( Intervento presentato al 12. convegno Conference on Web Science tenutosi a Southampton nel 2020 [10.1145/3394231.3397914].
Exploring Low-degree nodes first accelerates Network Exploration
A. Provetti;
2020
Abstract
We consider information diffusion on Web-like networks and how random walks can simulate it. A well-studied problem in this domain is Partial Cover Time, i.e., the calculation of the expected number of steps a random walker needs to visit a given fraction of the nodes of the network. We notice that some of the fastest solutions in fact require that nodes have perfect knowledge of the degree distribution of their neighbors, which in many practical cases is not obtainable, e.g., for privacy reasons. We thus introduce a version of the Cover problem that considers such limitations: Partial Cover Time with Budget. The budget is a limit on the number of neighbors that can be inspected for their degree; we have adapted optimal random walks strategies from the literature to operate under such budget. Our solution is called Min-degree (MD) and, essentially, it biases random walkers towards visiting peripheral areas of the network first. Extensive benchmarking on six real datasets proves that the - perhaps counter-intuitive strategy - MD strategy is in fact highly competitive wrt. state-of-the-art algorithms for cover.File | Dimensione | Formato | |
---|---|---|---|
2005.08050.pdf
accesso aperto
Tipologia:
Pre-print (manoscritto inviato all'editore)
Dimensione
3.61 MB
Formato
Adobe PDF
|
3.61 MB | Adobe PDF | Visualizza/Apri |
3394231.3397914.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
3.59 MB
Formato
Adobe PDF
|
3.59 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.