Random walk-based algorithms on networks

Abstract

The present thesis studies some important random walk-based algorithms, which are randomized rumor spreading and balanced allocation protocols on networks. In the first part of the thesis, we study the {\sf Push} and the {\sf Push-Pull} protocols introduced by \cite{DGH+87}, which are basic randomized protocols for information dissemination on networks. In Chapter \ref{multiple-call},we propose a new model where the number of calls of each node in every round is chosen independently according to a probability distribution $R$ with bounded mean determined at the beginning of the process. In addition to the model being a natural extension of the standard protocols, it also serves as a more realistic model for rumor spreading in a network whose entities are not completely uniform and may have different levels of power. We provide both lower and upper bounds on the rumor spreading time depending on statistical properties of $R$ such as the mean or the variance. While it is well-known that the standard protocols need $\Theta(\log n)$ rounds to spread a rumor on a complete network with $n$ nodes, % we are interested by how much we can speed up the spread of the rumor by enabling nodes to make more than one call in each round. we show that, if $R$ follows a power law distribution with exponent $\beta\in (2,3)$, then the {\sf Push-Pull} protocol spreads a rumor in $\Theta(\log \log n)$ rounds. Moreover, when $\beta=3$, we show a runtime of $\Theta\left(\frac{\log n}{\log\log n}\right)$. In Chapter \ref{poor}, we analyze the behavior of the standard {\sf Push-Pull} protocol on a class of random graphs, called random $k$-trees for every integer $k\ge 2$, that are suitable to model poorly connected, small-world and scale free networks. Here, we show that the {\sf Push-Pull} protocol propagates a rumor from a randomly chosen informed node to almost all nodes of a random $k$-tree with $n$ nodes in $\Oh((\log n)^{1+c_k})$ rounds with high probability, where 0 < c_k\le 1 is a decreasing function in $k$. We also derive a lower bound of $n^{\Omega(1)}$ for the runtime of the protocol to inform all nodes of the graph. Our technique for proving the upper bound is successfully carried over to a closely related class of random graphs called random $k$-Apollonian networks. We devote the rest of the thesis to the study of random walks on graphs, covering both practical and theoretical aspects. In Chapter \ref{kneser}, we show the existence of a \emph{cutoff} phenomenon for simple random walks on Kneser graphs. A {cutoff} phenomenon for a given sequence of ergodic Markov chains describes a sharp transition in the convergence of the chains to its stationary distribution over a negligible period of time, known as the {\it cutoff window}. In order to establish the cutoff phenomenon, we combine the spectral information of the transition matrix and a probabilistic technique, known as Wilson's method \cite{wilson}. And finally in Chapter \ref{non-back}, by using \emph{non-backtracking} random walks introduced by Alon et al. \cite{AL07}, we propose a new algorithm for sequentially allocating $n$ balls into $n$ bins that are organized as a $d$-regular graph with $n$ nodes, say $G$, where $d\ge3$ can be any integer. Let $l$ be a given positive integer. In each round $t$, $1\le t\le n$, ball $t$ picks a node of $G$ uniformly at random and performs a non-backtracking random walk of length $l$ from the chosen node. Then it deterministically selects a subset of the visited nodes as the potential choices and allocates itself on one of the choices with minimum load (ties are broken uniformly at random). Provided $G$ has a sufficiently large girth, we establish an upper bound for the maximum number of balls at any bin after allocating $n$ balls by the algorithm. We also show that the upper bound is tight up to a $\Oh(\log\log n)$ factor. In particular, we show that if we set $l=\lfloor(\log n)^{\frac{1+\epsilon}{2}}\rfloor $, for any constant $\epsilon\in(0,1]$, and $G$ has girth at least $\omega(l)$, then the maximum load is bounded by $\Oh(1/\epsilon)$ with high probability.

Die vorliegende Arbeit untersucht einige wichtige Zufallspfad-basierte Algorithmen, insbesondere Protokolle zur randomisierte Verbreitung von Gerüchten und Zufallspfade in Netzwerken. Im ersten Teil der Arbeit betrachten wir die von \cite{DGH+87} eingeführten {\sf Push} und {\sf Push-Pull} Protokolle, die grundlegende randomisierte Protokolle zur Informationsverbreitung in Netzwerken darstellen. In Kapitel 2 beschreiben wir ein neues Modell, in dem die Anzahl an Aufrufen jedes Knotens in jeder Runde unabhängig von einer Zufallsverteilung $R$ mit beschränktem Erwartungswert gezogen wird, die zu Beginn des Prozesses festgelegt wird. Das Modell ist nicht nur eine natürliche Erweiterung der Standardprotokolle, sondern dient auch als realistischeres Modell der Verbreitung von Gerüchten in Netzwerken deren Entitäten nicht uniform sind und unterschiedlich großen Einfluss haben können. Wir geben untere und obere Schranken für die benötigte Zeit zur Verbreitung der Gerüchte an, in Abhängigkeit von statistischen Eigenschaften von $R$ wie Erwartungswert und Varianz. Während bekannt ist, dass die Standardprotokolle $\Theta(\log n)$ Runden benötigen, um ein Gerücht in einem vollständigen Netzwerk mit $n$ Knoten zu verbreiten, zeigen wir, dass das Push-Pull-Protokoll ein Gerücht in $\Theta(\log\log n)$ Runden verbreitet, wenn $R$ einer Potenzgesetz-Verteilung mit Exponent $\beta \in (2,3)$ folgt. Darüberhinaus zeigen wir, im Falle $\beta=3$, eine Laufzeit von $\Theta\left(\frac{\log n}{\log\log n}\right)$. In Kapitel 3 analysieren wir das Verhalten des Standard-Push-Pull-Protokolls auf einer Klasse von Zufallsgraphen, den sogenannten Zufalls-$k$-Bäumen für jede natürliche Zahl $k\ge 2$, die sich dafür eignen, schwach zusammenhängende Netzwerke, Small-World-Netzwerke und skalenfreie Netzwerke zu modellieren. Hierbei zeigen wir, dass das {\sf Push-Pull}-Protokoll ein Gerücht von einem zufällig gewählten informierten Knoten zu fast allen Knoten eines Zufalls-$k$-Baums mit $n$ Knoten in $O\left(\left(\log n\right)^{1+c_k}\right)$ Runden mit hoher Wahrscheinlichkeit verbreiten kann, wobei $0 < c_k \le 1$ eine fallende Funktion in $k$ ist. Wir leiten auch eine untere Schranke von $n^{\Omega(1)}$ für die Laufzeit des Protokolls ab, um alle Knoten des Graphen zu informieren. Unsere Technik zum Beweis der oberen Schranke wird erfolgreich auf eine eng verwandte Klasse von Zufallsgraphen, der sogenannten $k$-Apollonischen Graphen, übertragen. Den Rest der Dissertation widmen wir der Untersuchung sowohl praktischer als auch theoretischer Aspekte von Zufallspfaden in Graphen. In Kapitel 3 zeigen wir die Existenz eines Cutoff-Phänomens für einfache Zufallspfade in Kneser-Graphen. Ein Cutoff-Phänomen für eine gegebene Sequenz von ergodischen Markovketten beschreibt einen abrupten Übergang bei der Konvergenz der Ketten gegen ihre stationäre Verteilung über einen vernachlässigbaren Zeitraum, bekannt als \textit{Cutoff-Fenster}. Um das Cutoff-Phänomen nachzuweisen kombinieren wir die spektrale Information der Transitionsmatrix und eine probabilistische Technik, bekannt als Wilson's Methode \cite{wilson}. Und schließlich präsentieren wir in Kapitel 5 unter Einbeziehung von nicht-zurücksetzenden Zufallspfaden, eingeführt von Alon et al. \cite{AL07}, einen neuen Algorithmus um sequenziell $n$ Bälle $n$ Körben zuzuweisen, die als $d$-regulärer Graph $G$ mit $n$ Knoten organisiert sind, wobei $d \ge 3$ eine beliebige ganze Zahl sein kann. Sei $l$ eine gegebene positive ganze Zahl. In jeder Runde $t$, $1 \le t \le n$, wählt Ball $t$ einen Knoten von $G$ zufällig mit gleicher Wahrscheinlichkeit und folgt einem nicht-zurücksetzenden Zufallspfad der Länge $l$ ab diesem gewählten Knoten. Dann wählt der Ball deterministisch eine Teilmenge der besuchten Knoten als potenzielle Kandidaten aus, und weist sich selbst demjenigen Kandidaten mit minimaler Last zu (Gleichstände werden beliebig gelöst). Wenn $G$ hinreichend große Taillenweite hat, können wir eine obere Schranke für die maximale Anzahl an Bällen in jedem Bin nach der Zuweisung von $n$ Bällen durch den Algorithmus angeben. Wir zeigen auch, dass diese obere Schranke bis auf einen $O\left(\log\log n\right)$-Faktor scharf ist. Insbesondere zeigen wir, dass die maximale Last mit hoher Wahrscheinlichkeit durch $O(1/\epsilon)$ beschränkt ist, wenn wir $l=\left\lfloor\left(\log n\right)^{\frac{1+\epsilon}{2}}\right\rfloor$ setzen, f\"{u}r eine beliebige Konstante $\epsilon \in (0,1]$, und $G$ Taillenweite mindestens $\omega(l)$ hat. \smallskip\noindent. Diese Arbeit ist in englischer Sprache verfasst.