Ricerc@Sapienza

In this article, we study the completion time of the PUSH-PULL variant of rumor spreading, also known as randomized broadcast.We show that if a network has n nodes and conductance φ then, with high probability, PUSH-PULL will deliver themessage to all nodes in the graph within O(logn/φ) many communication rounds. This bound is best possible. We also give an alternative proof that the completion time of PUSH-PULL is bounded by a polynomial in logn/φ, based on graph sparsification.

We propose a multi-agent algorithm able to automatically discover relevant regularities in a given dataset, determining at the same time the set of con?gurations of the adopted parametric dissimilarity measure that yield compact and separated clusters. Each agent operates independently by performing a Markovian random walk on a weighted graph representation of the input dataset. Such a weighted graph representation is induced by a speci?c parameter con?guration of the dissimilarity measure adopted by an agent for the search.