Abstract
In this paper we consider dynamic networks that can change over time. Often, such networks have a repetitive pattern despite constant and otherwise unpredictable changes. Based on this observation, we introduce the notion of a ρ-recurring family of a dynamic network, which has the property that the dynamic network frequently contains a graph in the family, where frequently means at a rate 0<ρ ≤ 1. Using this concept, we reduce the analysis of max-degree random walks on dynamic networks to the case for static networks. Given a dynamic network with a ρ-recurring family \(\mathcal{F}\), we prove an upper bound of on the hitting and cover times, and an upper bound of \(O\left( \rho^{-1}(1- \hat\lambda(\mathcal{F}))^{-1} \log n \right) \) on the mixing time of random walks, where n is the number of nodes, \(\hat t_{hit}(\mathcal{F})\) is upper bound on the hitting time of graphs in \(\mathcal{F}\), and \(\hat\lambda(\mathcal{F})\) is upper bound on the second largest eigenvalue of the transition matrices of graphs in \(\mathcal{F}\). These results have two implications. First, they yield a general bound of \(O\left( \rho^{-1} n^3 \log n \right) \) on the hitting time and cover time of a dynamic network (ρ is the rate at which the network is connected); this result improves on the previous bound of \(O\left( \rho^{-1} n^5 \log^2 n \right) \),[3]. Second, the results imply that dynamic networks with recurring families preserve the properties of random walks in their static counterparts. This result allows importing the extensive catalogue of results for static graphs (cliques, expanders, regular graphs, etc.) into the dynamic setting.
This work was partially supported by Fundação para a Ciência e Tecnologia (FCT) via the project PEPITA (PTDC/EEI-SCR/2776/2012) and via the INESC-ID multi-annual funding through the PIDDAC Program fund grant, under project PEst-OE/EEI/LA0021/2013.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aldous, D., Fill, J.A.: Reversible Markov Chains and Random Walks on Graphs. Unpublished (1995)
Aleliunas, R., Karp, R.M., Lipton, R.J., Lovász, L., Rackoff, C.: Random walks, universal traversal sequences, and the complexity of maze problems. In: 20th Annual Symposium on Foundations of Computer Science, FOCS 1979, pp. 218–223 (1979)
Avin, C., Koucký, M., Lotker, Z.: How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 121–132. Springer, Heidelberg (2008)
Bar-Yossef, Z., Friedman, R., Kliot, G.: Rawms - random walk based lightweight membership service for wireless ad hoc networks. ACM Trans. Comput. Syst. 26(2), 1–66 (2008)
Brightwell, G., Winkler, P.: Extremal cover times for random walks on trees. Journal of Graph Theory 14(5), 547–554 (1990)
Broder, A.Z., Karlin, A.R.: Bounds on the cover time. J. Theoretical Probab. 2, 101–120 (1988)
Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems 27(5), 387–408 (2012)
Clementi, A.E.F., Pasquale, F., Monti, A., Silvestri, R.: Communication in dynamic radio networks. In: Proceedings of the Twenty-sixth Annual ACM Symposium on Principles of Distributed Computing, PODC 2007, pp. 205–214. ACM, New York (2007)
Clementi, A.E.F., Macci, C., Monti, A., Pasquale, F., Silvestri, R.: Flooding time in edge-markovian dynamic graphs. In: PODC 2008, pp. 213–222. ACM, New York (2008)
Cooper, C., Frieze, A.: Crawling on simple models of web graphs. Internet Mathematics 1, 57–90 (2003)
Das Sarma, A., Molla, A.R., Pandurangan, G.: Fast distributed computation in dynamic networks via random walks. In: Aguilera, M.K. (ed.) DISC 2012. LNCS, vol. 7611, pp. 136–150. Springer, Heidelberg (2012)
Dembo, A., Peres, Y., Rosen, J., Zeitouni, O.: Cover times for brownian motion and random walks in two dimensions. Annals of Mathematics 160(2), 433–464 (2004)
Dolev, S., Schiller, E., Welch, J.L.: Random walk for self-stabilizing group communication in ad hoc networks. IEEE Transactions on Mobile Computing 5, 893–905 (2006)
Feige, U.: A tight lower bound on the cover time for random walks on graphs. Random Struct. Algorithms 6, 433–438 (1995)
Gkantsidis, C., Mihail, M., Saberi, A.: Random walks in peer-to-peer networks: algorithms and evaluation. Perform. Eval. 63, 241–263 (2006)
Haeupler, B.: Analyzing network coding gossip made easy. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC 2011, pp. 293–302. ACM, New York (2011)
Haeupler, B., Karger, D.: Faster information dissemination in dynamic networks via network coding. In: Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2011, pp. 381–390. ACM, New York (2011)
Haeupler, B., Kuhn, F.: Lower bounds on information dissemination in dynamic networks. In: Aguilera, M.K. (ed.) DISC 2012. LNCS, vol. 7611, pp. 166–180. Springer, Heidelberg (2012)
Horn, R.A., Johnson, C.R.: Matrix analysis. Cambridge University Press, New York (1986)
Ikeda, S., Kubo, I., Okumoto, N., Yamashita, M.: Fair circulation of a token. IEEE Transactions on Parallel and Distributed Systems 13(4), 367–372 (2002)
Jonasson, J.: On the cover time for random walks on random graphs. Comb. Probab. Comput. 7(3), 265–279 (1998)
Kahn, J.D., Linial, N., Nisan, N., Saks, M.E.: On the cover time of random walks on graphs. Journal of Theoretical Probability 2(1), 121–128 (1989)
Kirkland, S.: Nonhomogeneous matrix products. World Scientific, River Edge (2002)
Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, pp. 513–522. ACM, New York (2010)
Kuhn, F., Oshman, R.: Dynamic networks: Models and algorithms. SIGACT News 42(1), 82–96 (2011)
Kuhn, F., Oshman, R., Moses, Y.: Coordinated consensus in dynamic networks. In: Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2011, pp. 1–10. ACM, New York (2011)
Law, C., Siu, K.-Y.: Distributed construction of random expander networks. In: Twenty-Second Annual Joint Conference of the IEEE Computer and Communications, INFOCOM 2003, vol. 3, pp. 2133–2143. IEEE Societies (2003)
Leitao, J., Pereira, J., Rodrigues, L.: Hyparview: A membership protocol for reliable gossip-based broadcast. In: In IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2007, pp. 419–428. IEEE Computer Society (2007)
Lovász, L.: Random walks on graphs: A survey (1993)
Massoulié, L., Le Merrer, E., Kermarrec, A.-M., Ganesh, A.: Peer counting and sampling in overlay networks: random walk methods. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing, PODC 2006, pp. 123–132. ACM, New York (2006)
Perkins, C.E., Royer, E.M.: Ad-hoc on-demand distance vector routing. In: Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, WMCSA 1999, pp. 90–100. IEEE Computer Society, Washington, DC (1999)
Stoica, I., Morris, R., Karger, D., Frans Kaashoek, M., Balakrishnan, H.: Chord: A scalable peer-to-peer lookup service for internet applications. In: Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, SIGCOMM 2001, pp. 149–160. ACM, New York (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Denysyuk, O., Rodrigues, L. (2014). Random Walks on Evolving Graphs with Recurring Topologies. In: Kuhn, F. (eds) Distributed Computing. DISC 2014. Lecture Notes in Computer Science, vol 8784. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-45174-8_23
Download citation
DOI: https://doi.org/10.1007/978-3-662-45174-8_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-45173-1
Online ISBN: 978-3-662-45174-8
eBook Packages: Computer ScienceComputer Science (R0)