Thesis (MSc)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: We study random walks on nite graphs. The reader is introduced to general Markov chains before we move on more specifically to random walks on graphs. A random walk on a graph is just a Markov chain that is time-reversible. The main parameters we study are the hitting time, commute time and cover time. We nd novel formulas for the cover time of the subdivided star graph and broom graph before looking at the trees with extremal cover times. Lastly we look at a connection between random walks on graphs and electrical networks, where the hitting time between two vertices of a graph is expressed in terms of a weighted sum of e ective resistances. This expression in turn proves useful when we study the cover cost, a parameter related to the cover time. / AFRIKAANSE OPSOMMING: Ons bestudeer toevallige wandelings op eindige gra eke in hierdie tesis. Eers word algemene Markov kettings beskou voordat ons meer spesi ek aanbeweeg na toevallige wandelings op gra eke. 'n Toevallige wandeling is net 'n Markov ketting wat tyd herleibaar is. Die hoof paramaters wat ons bestudeer is die treftyd, pendeltyd en dektyd. Ons vind oorspronklike formules vir die dektyd van die verdeelde stergra ek sowel as die besemgra ek en kyk daarna na die twee bome met uiterste dektye. Laastens kyk ons na 'n verband tussen toevallige wandelings op gra eke en elektriese netwerke, waar die treftyd tussen twee punte op 'n gra ek uitgedruk word in terme van 'n geweegde som van e ektiewe weerstande. Hierdie uitdrukking is op sy beurt weer nuttig wanneer ons die dekkoste bestudeer, waar die dekkoste 'n paramater is wat verwant is aan die dektyd.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-05-31T12:29:07Z No. of bitstreams: 1 abraaoguimaraesflores.pdf: 5791600 bytes, checksum: 384ace33f746857745754f651589590f (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-05-31T12:42:46Z (GMT) No. of bitstreams: 1 abraaoguimaraesflores.pdf: 5791600 bytes, checksum: 384ace33f746857745754f651589590f (MD5) / Made available in DSpace on 2017-05-31T12:42:46Z (GMT). No. of bitstreams: 1 abraaoguimaraesflores.pdf: 5791600 bytes, checksum: 384ace33f746857745754f651589590f (MD5) Previous issue date: 2013-08-26 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A dinamicidade é uma característica presente em diversos sistemas reais, tais como redes de comunicação, sociais, biológicas e tecnológicas. Processos de difusão em redes complexas podem surgir, por exemplo, em busca de dados, roteamento de dados e propa gação de doenças. Desta forma, a compreensão do tempo necessário para difusão é um tema de estudo importante em redes complexas dinâmicas. Nesta dissertação é realizado um estudo de como medidas de centralidade podem ajudar na diminuição do tempo de difusão de informação em redes complexas dinâmicas. Usando dados de sistemas reais e sintéticos é mostrado que, se a dinamicidade é desconsiderada, o tempo necessário para difundir uma informação na rede é subestimado. Foram propostos algoritmos de difusão que consideram métricas de centralidade em grafos. Estes algoritmos aceleram o processo de difusão, quando comparados com algoritmos de difusão mais simples, como o Random Walk. Por fim, foi analisado o impacto de um modelo simples de predição de arestas nos algoritmos de difusão baseados em centralidade que foram propostos nesta dissertação. / The dynamics is a characteristic present in many real systems, such as communication networks, social, biological and technological. Diffusion processes in complex networks may arise, for example, search data, routing data and the spread of diseases. Thus, understanding the time required for diffusion is an important topic of study in dynamic complex networks. This dissertation is a study of how centrality measures can help in reducing the time information dissemination in dynamic complex networks. Using data from synthetic and real systems is shown that if the dynamics is disregarded, the time needed for spreading an information network is underestimated. Diffusion algorithms have been proposed that consider metrics of centrality in graphs. Finally, we analyze the impact of a simple model for predicting edge algorithms in diffusion based on centrality that have been proposed in this dissertation.

Menschliche Systeme werden seit einiger Zeit modelliert und analysiert auf der Basis der Theorie komplexer Netzwerke. Dies erlaubt es quantitativ zu untersuchen, welche strukturellen und zeitlichen Merkmale eines Systems Ausbreitungsprozesse beeinflussen, z.B. von Informationen oder von Infektionskrankheiten. Im ersten Teil der Arbeit wird untersucht, wie eine modular-hierarchische Struktur von statischen Netzwerken eine schnelle Verbreitung von Signalen ermöglicht. Es werden neue Heuristiken entwickelt um die Random-Walk-Observablen “First Passage Time” und “Cover Time” auf lokal geclusterten Netzwerken zu ermitteln. Vergleiche mit der Approximation eines gemittelten Mediums zeigen, dass das Auftreten der beobachteten Minima der Observablen ein reiner Netzwerkeffekt ist. Es wird weiterhin dargelegt, dass nicht alle modular-hierarchischen Netzwerkmodelle dieses Phänomen aufweisen. Im zweiten Teil werden zeitlich veränderliche face-to-face Kontaktnetzwerke auf ihre Anfälligkeit für Infektionskrankheiten untersucht. Mehrere Studien belegen, dass Menschen vornehmlich Zeit in Isolation oder kleinen, stark verbundenen Gruppen verbringen, und dass ihre Kontaktaktivität einem zirkadianen Rhythmus folgt. Inwieweit diese beiden Merkmale die Ausbreitung von Krankheiten beeinflussen, ist noch unklar. Basierend auf einem neuen Modell wird erstmals gezeigt, dass zirkadian variierende Netzwerke Trajektorien folgen in einem Zustandsraum mit einer strukturellen und einer zeitlichen Dimension. Weiterhin wird dargelegt, dass mit zunehmender Annäherung der zeitlichen Dimension von System und Krankheit die systemische Infektionsanfälligkeit sinkt. Dies steht in direktem Widerspruch zu Ergebnissen anderer Studien, die eine zunehmende Anfälligkeit vorhersagen, eine Diskrepanz, die auf die Ungültigkeit einer weit verbreiteten Approximation zurückzuführen ist. Die hier vorgestellten Ergebnisse implizieren, dass auf dem Gebiet die Entwicklung neuer theoretischer Methoden notwendig ist. / Human systems have been modeled and analyzed on the basis of complex networks theory in recent time. This abstraction allows for thorough quantitative analyses to investigate which structural and temporal features of a system influence the evolution of spreading processes, such as the passage of information or of infectious diseases. The first part of this work investigates how the ubiquitous modular hierarchical structure of static real-world networks allows for fast delivery of messages. New heuristics are developed to evaluate random walk mean first passage times and cover times on locally clustered networks. A comparison to average medium approximations shows that the emergence of these minima are pure network phenomena. It is further found that not all modular hierarchical network models provide optimal message delivery structure. In the second part, temporally varying face-to-face contact networks are investigated for their susceptibility to infection. Several studies have shown that people tend to spend time in small, densely-connected groups or in isolation, and that their connection behavior follows a circadian rhythm. To what extent both of these features influence the spread of diseases is as yet unclear. Therefore, a new temporal network model is devised here. Based on this model, circadially varying networks can for the first time be interpreted as following trajectories through a newly defined systemic state space. It is further revealed that in many temporally varying networks the system becomes less susceptible to infection when the time-scale of the disease approaches the time-scale of the network variation. This is in direct conflict with findings of other studies that predict increasing susceptibility of temporal networks, a discrepancy which is attributed to the invalidity of a widely applied approximation. The results presented here imply that new theoretical advances are necessary to study the spread of diseases in temporally varying networks.