This dissertation consists of two parts, with the common theme "Exploration on and of Networks". In Part I we investigate the theme "exploration on networks" by studying random walks on dynamic... Show moreThis dissertation consists of two parts, with the common theme "Exploration on and of Networks". In Part I we investigate the theme "exploration on networks" by studying random walks on dynamic random graphs. Random walks can be seen as a model for exploration on networks. In particular, we study the "mixing times" of random walks which is a measure of how fast the random walk explores the graph. In Part II we investigate the theme "exploration of networks" by studying the problem of union-complexity of random disk regions. This problem is related to the frequency assignment on wireless networks. In particular, we study average-case behaviour of union-complexity of random disk regions, which can be seen as a measure of complexity of a 'typical' wireless network. Show less
Avena, L.; Güldas, H.; Hofstad, R. van der; Hollander, W.T.F. den 2018
The mixing time of a random walk, with or without backtracking, on a random graph generated according to the configuration model on n n vertices, is known to be of order logn logn . In this paper,... Show moreThe mixing time of a random walk, with or without backtracking, on a random graph generated according to the configuration model on n n vertices, is known to be of order logn logn . In this paper, we investigate what happens when the random graph becomes dynamic, namely, at each unit of time a fraction α n αn of the edges is randomly rewired. Under mild conditions on the degree sequence, guaranteeing that the graph is locally tree-like, we show that for every ε∈(0,1) ε∈(0,1) the ε ε -mixing time of random walk without backtracking grows like 2log(1/ε)/log(1/(1−α n )) − − − − − − − − − − − − − − − − − − − − − √ 2log(1/ε)/log(1/(1−αn)) as n→∞ n→∞ , provided that lim n→∞ α n (logn) 2 =∞ limn→∞αn(logn)2=∞ . The latter condition corresponds to a regime of fast enough graph dynamics. Our proof is based on a randomised stopping time argument, in combination with coupling techniques and combinatorial estimates. The stopping time of interest is the first time that the walk moves along an edge that was rewired before, which turns out to be close to a strong stationary time. Show less
