Dissertations / Theses on the topic 'Random walks on network'
To see the other types of publications on this topic, follow the link: Random walks on network.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Random walks on network.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
De, Bacco Caterina. "Decentralized network control, optimization and random walks on networks." Thesis, Paris 11, 2015. http://www.theses.fr/2015PA112164/document.
Full textAbstract:
Dans les dernières années, plusieurs problèmes ont été étudiés à l'interface entre la physique statistique et l'informatique. La raison étant que, souvent, ces problèmes peuvent être réinterprétés dans le langage de la physique des systèmes désordonnés, où un grand nombre de variables interagit à travers champs locales qui dépendent de l'état du quartier environnant. Parmi les nombreuses applications de l'optimisation combinatoire le routage optimal sur les réseaux de communication est l'objet de la première partie de la thèse. Nous allons exploiter la méthode de la cavité pour formuler des algorithmes efficaces de type ‘’message-passing’’ et donc résoudre plusieurs variantes du problème grâce à sa mise en œuvre numérique. Dans un deuxième temps, nous allons décrire un modèle pour approcher la version dynamique de la méthode de la cavité, ce qui permet de diminuer la complexité du problème de l'exponentielle de polynôme dans le temps. Ceci sera obtenu en utilisant le formalisme de ‘’Matrix Product State’’ de la mécanique quantique.Un autre sujet qui a suscité beaucoup d'intérêt en physique statistique de processus dynamiques est la marche aléatoire sur les réseaux. La théorie a été développée depuis de nombreuses années dans le cas que la topologie dessous est un réseau de dimension d. Au contraire le cas des réseaux aléatoires a été abordé que dans la dernière décennie, laissant de nombreuses questions encore ouvertes pour obtenir des réponses. Démêler plusieurs aspects de ce thème fera l'objet de la deuxième partie de la thèse. En particulier, nous allons étudier le nombre moyen de sites distincts visités au cours d'une marche aléatoire et caractériser son comportement en fonction de la topologie du graphe. Enfin, nous allons aborder les événements rares statistiques associées aux marches aléatoires sur les réseaux en utilisant le ‘’Large deviations formalism’’. Deux types de transitions de phase dynamiques vont se poser à partir de simulations numériques. Nous allons conclure décrivant les principaux résultats d'une œuvre indépendante développée dans le cadre de la physique hors de l'équilibre. Un système résoluble en deux particules browniens entouré par un bain thermique sera étudiée fournissant des détails sur une interaction à médiation par du bain résultant de la présence du bainIn the last years several problems been studied at the interface between statistical physics and computer science. The reason being that often these problems can be reinterpreted in the language of physics of disordered systems, where a big number of variables interacts through local fields dependent on the state of the surrounding neighborhood. Among the numerous applications of combinatorial optimisation the optimal routing on communication networks is the subject of the first part of the thesis. We will exploit the cavity method to formulate efficient algorithms of type message-passing and thus solve several variants of the problem through its numerical implementation. At a second stage, we will describe a model to approximate the dynamic version of the cavity method, which allows to decrease the complexity of the problem from exponential to polynomial in time. This will be obtained by using the Matrix Product State formalism of quantum mechanics. Another topic that has attracted much interest in statistical physics of dynamic processes is the random walk on networks. The theory has been developed since many years in the case the underneath topology is a d-dimensional lattice. On the contrary the case of random networks has been tackled only in the past decade, leaving many questions still open for answers. Unravelling several aspects of this topic will be the subject of the second part of the thesis. In particular we will study the average number of distinct sites visited during a random walk and characterize its behaviour as a function of the graph topology. Finally, we will address the rare events statistics associated to random walks on networks by using the large-deviations formalism. Two types of dynamic phase transitions will arise from numerical simulations, unveiling important aspects of these problems. We will conclude outlining the main results of an independent work developed in the context of out-of-equilibrium physics. A solvable system made of two Brownian particles surrounded by a thermal bath will be studied providing details about a bath-mediated interaction arising for the presence of the bath
2
Maddalena, Daniela. "Stationary states in random walks on networks." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2016. http://amslaurea.unibo.it/10170/.
Full textAbstract:
In this thesis we dealt with the problem of describing a transportation network in which the objects in movement were subject to both finite transportation capacity and finite accomodation capacity. The movements across such a system are realistically of a simultaneous nature which poses some challenges when formulating a mathematical description. We tried to derive such a general modellization from one posed on a simplified problem based on asyncronicity in particle transitions. We did so considering one-step processes based on the assumption that the system could be describable through discrete time Markov processes with finite state space. After describing the pre-established dynamics in terms of master equations we determined stationary states for the considered processes. Numerical simulations then led to the conclusion that a general system naturally evolves toward a congestion state when its particle transition simultaneously and we consider one single constraint in the form of network node capacity. Moreover the congested nodes of a system tend to be located in adjacent spots in the network, thus forming local clusters of congested nodes.
3
Zimmermann, Jochen [Verfasser], and Andreas [Akademischer Betreuer] Buchleitner. "Random walks with nonlinear interactions on heterogeneous networks = Random Walk mit nichtlinearen Wechselwirkungen auf heterogenen Netzwerken." Freiburg : Universität, 2015. http://d-nb.info/1123482381/34.
Full text
4
Kolgushev, Oleg. "Influence of Underlying Random Walk Types in Population Models on Resulting Social Network Types and Epidemiological Dynamics." Thesis, University of North Texas, 2016. https://digital.library.unt.edu/ark:/67531/metadc955128/.
Full textAbstract:
Epidemiologists rely on human interaction networks for determining states and dynamics of disease propagations in populations. However, such networks are empirical snapshots of the past. It will greatly benefit if human interaction networks are statistically predicted and dynamically created while an epidemic is in progress. We develop an application framework for the generation of human interaction networks and running epidemiological processes utilizing research on human mobility patterns and agent-based modeling. The interaction networks are dynamically constructed by incorporating different types of Random Walks and human rules of engagements. We explore the characteristics of the created network and compare them with the known theoretical and empirical graphs. The dependencies of epidemic dynamics and their outcomes on patterns and parameters of human motion and motives are encountered and presented through this research. This work specifically describes how the types and parameters of random walks define properties of generated graphs. We show that some configurations of the system of agents in random walk can produce network topologies with properties similar to small-world networks. Our goal is to find sets of mobility patterns that lead to empirical-like networks. The possibility of phase transitions in the graphs due to changes in the parameterization of agent walks is the focus of this research as this knowledge can lead to the possibility of disruptions to disease diffusions in populations. This research shall facilitate work of public health researchers to predict the magnitude of an epidemic and estimate resources required for mitigation.
5
Linn, Hanna. "Detecting quantum speedup for random walks with artificial neural networks." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-289347.
Full textAbstract:
Random walks on graphs are an essential base for crucial algorithms for solving problems, like the boolean satisfiability problem. A speedup of random walks could improve these algorithms. The quantum version of the random walk, quantum walk, is faster than random walks in specific cases, e.g., on some linear graphs. An analysis of when the quantum walk is faster than the random walk can be accomplished analytically or by simulating both the walks on the graph. The problem arises when the graphs grow in size and connectivity. There are no known general rules for what an arbitrary graph not having explicit symmetries should exhibit to promote the quantum walk. Simulations will only answer the question for one single case, and will not provide any general rules for properties the graph should have. Using artificial neural networks (ANNs) as an aid for detecting when the quantum walk is faster on average than random walk on graphs, going from an initial node to a target node, has been done before. The quantum speedup may not be more than polynomial if the initial state of the quantum walk is purely in the initial node of the graph. We investigate starting the quantum walk in various superposition states, with an additional auxiliary node, to maybe achieve a larger quantum speedup. We suggest different ways to add the auxiliary node and select one of these schemes for use in this thesis. The superposition states examined are two stabiliser states and two magic states, inspired by the Gottesman-Knill theorem. According to this theorem, starting a quantum algorithm in a magic state may give an exponential speedup, but starting in a stabilizer state cannot give an exponential speedup, given that only gates from the Clifford group are used in the algorithm, as well as measurements are performed in the Pauli basis. We show that it is possible to train an ANN to classify graphs into what quantum walk was the fastest for various initial states of the quantum walk. The ANN classifies linear graphs and random graphs better than a random guess. We also show that a convolutional neural network (CNN) with a deeper architecture than earlier proposed for the task, is better at classifying the graphs than before. Our findings pave the way for automated research in novel quantum walk-based algorithms.Slumpvandringar på grafer är essensiella i viktiga algoritmer för att lösa olika problem, till exempel SAT, booleska uppfyllningsproblem (the satisfiability problem). Genom att göra slumpvandringar snabbare går det att förbättra dessa algoritmer. Kvantversionen av slumpvandringar, kvantvandringar, har visats vara snabbare än klassiska slumpvandringar i specifika fall, till exempel på vissa linjära grafer. Det går att analysera, analytiskt eller genom att simulera vandringarna på grafer, när kvantvandringen är snabbare än slumpvandingen. Problem uppstår dock när graferna blir större, har fler noder samt fler kanter. Det finns inga kända generella regler för vad en godtycklig graf, som inte har några explicita symmetrier, borde uppfylla för att främja kvantvandringen. Simuleringar kommer bara besvara frågan för ett enda fall. De kommer inte att ge några generella regler för vilka egenskaper grafer borde ha. Artificiella neuronnät (ANN) har tidigare används som hjälpmedel för att upptäcka när kvantvandringen är snabbare än slumpvandingen på grafer. Då jämförs tiden det tar i genomsnitt att ta sig från startnoden till slutnoden. Dock är det inte säkert att få kvantacceleration för vandringen om initialtillståndet för kvantvandringen är helt i startnoden. I det här projektet undersöker vi om det går att få en större kvantacceleration hos kvantvandringen genom att starta den i superposition med en extra nod. Vi föreslår olika sätt att lägga till den extra noden till grafen och sen väljer vi en för att använda i resen av projektet. De superpositionstillstånd som undersöks är två av stabilisatortillstånden och två magiska tillstång. Valen av dessa tillstånd är inspirerat av Gottesmann- Knill satsen. Enligt satsen så kan en algoritm som startar i ett magiskt tillstånd ha en exponetiell uppsnabbning, men att starta i någon stabilisatortillstånden inte kan ha det. Detta givet att grindarna som används i algoritmen är från Cliffordgruppen samt att alla mätningar är i Paulibasen. I projektet visar vi att det är möjligt att träna en ANN så att den kan klassificera grafer utifrån vilken kvantvandring, med olika initialtillstånd, som var snabbast. Artificiella neuronnätet kan klassificera linjära grafer och slumpmässiga grafer bättre än slumpen. Vi visar också att faltningsnätverk med en djupare arkitektur än tidigare föreslaget för uppgiften är bättre på att klassificera grafer än innan. Våra resultat banar vägen för en automatiserad forskning i nya kvantvandringsbaserade algoritmer.
6
Lau, Hon Wai. "Random walk in networks : first passage time and speed analysis /." View abstract or full-text, 2009. http://library.ust.hk/cgi/db/thesis.pl?PHYS%202009%20LAU.
Full text
7
Malmros, Jens. "Studies in respondent-driven sampling : Directed networks, epidemics, and random walks." Doctoral thesis, Stockholms universitet, Matematiska institutionen, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:su:diva-129287.
Full textAbstract:
Respondent-driven sampling (RDS) is a link-tracing sampling methodology especially suitable for sampling hidden populations. A clever sampling mechanism and inferential procedures that facilitate asymptotically unbiased population estimates has contributed to the rising popularity of the method. The papers in this thesis extend RDS estimation theory to some population structures to which the classical RDS estimation framework is not applicable and analyse the behaviour of the RDS recruitment process.At the time of the doctoral defense, the following papers were unpublished and had a status as follows: Paper 2: In press. Paper 3: Accepted. Paper 4: Manuscript.
8
Russo, Elena Tea. "Fluctuation properties in random walks on networks and simple integrate and fire models." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2015. http://amslaurea.unibo.it/9565/.
Full textAbstract:
In questa tesi si è studiato l’insorgere di eventi critici in un semplice modello neurale del tipo Integrate and Fire, basato su processi dinamici stocastici markoviani definiti su una rete. Il segnale neurale elettrico è stato modellato da un flusso di particelle. Si è concentrata l’attenzione sulla fase transiente del sistema, cercando di identificare fenomeni simili alla sincronizzazione neurale, la quale può essere considerata un evento critico. Sono state studiate reti particolarmente semplici, trovando che il modello proposto ha la capacità di produrre effetti "a cascata" nell’attività neurale, dovuti a Self Organized Criticality (auto organizzazione del sistema in stati instabili); questi effetti non vengono invece osservati in Random Walks sulle stesse reti. Si è visto che un piccolo stimolo random è capace di generare nell’attività della rete delle fluttuazioni notevoli, in particolar modo se il sistema si trova in una fase al limite dell’equilibrio. I picchi di attività così rilevati sono stati interpretati come valanghe di segnale neurale, fenomeno riconducibile alla sincronizzazione.
9
Xu, Keyulu. "Graph structures, random walks, and all that : learning graphs with jumping knowledge networks." Thesis, Massachusetts Institute of Technology, 2019. https://hdl.handle.net/1721.1/121660.
Full textAbstract:
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2019
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 51-54).
Graph representation learning aims to extract high-level features from the graph structures and node features, in order to make predictions about the nodes and the graphs. Applications include predicting chemical properties of drugs, community detection in social networks, and modeling interactions in physical systems. Recent deep learning approaches for graph representation learning, namely Graph Neural Networks (GNNs), follow a neighborhood aggregation procedure, where the representation vector of a node is computed by recursively aggregating and transforming feature vectors of its neighboring nodes. We analyze some important properties of these models, and propose a strategy to overcome the limitations. In particular, the range of neighboring nodes that a node's representation draws from strongly depends on the graph structure, analogous to the spread of a random walk. To adapt to local neighborhood properties and tasks, we explore an architecture - jumping knowledge (JK) networks that flexibly leverages, for each node, different neighborhood ranges to enable better structure-aware representation. In a number of experiments on social, bioinformatics and citation networks, we demonstrate that our model achieves state-of-the-art performance. Furthermore, combining the JK framework with models like Graph Convolutional Networks, GraphSAGE and Graph Attention Networks consistently improves those models' performance.
by Keyulu Xu.
S.M.
S.M. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science
10
Uguccioni, Marco. "Introduzione alla meccanica statistica dei random walk su network." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2020. http://amslaurea.unibo.it/21027/.
Full textAbstract:
Lo scopo della tesi è quello di studiare la dinamica stocastica di particelle che realizzano un random walk su network, focalizzandosi in particolare sulle proprietà dello stato stazionario del processo.
Dopo aver introdotto i concetti fondamentali di network e random walk per singola particella, si generalizza la trattazione a N particelle non interagenti su network a capacità di trasporto e storage infinita (ISTC) e si ricava il relativo stato stazionario con una trattazione meccano-statistica, applicando il principio di massima entropia.
Successivamente, per avvicinarsi a modelli di trasporto reali, si introducono nel sistema dei vincoli sulla capacità di trasporto e di storage (1-FTC+q-FSC) e si derivano le relazioni reciproche di Onsager, mostrando ancora una volta di poter trattare il sistema in termini termodinamici.
Durante la trattazione si realizzano numerose simulazioni numeriche utilizzando codici sviluppati in C++ e ROOT, volte a confermare l'andamento analitico atteso dei sistemi studiati.
11
Ratner, Michael. "Quantum Walks and Structured Searches on Free Groups and Networks." Diss., Temple University Libraries, 2017. http://cdm16002.contentdm.oclc.org/cdm/ref/collection/p245801coll10/id/442825.
Full textAbstract:
MathematicsPh.D.
Quantum walks have been utilized by many quantum algorithms which provide improved performance over their classical counterparts. Quantum search algorithms, the quantum analogues of spatial search algorithms, have been studied on a wide variety of structures. We study quantum walks and searches on the Cayley graphs of finitely-generated free groups. Return properties are analyzed via Green’s functions, and quantum searches are examined. Additionally, the stopping times and success rates of quantum searches on random networks are experimentally estimated.
Temple University--Theses
12
Yuan, Yuchen. "Advanced Visual Computing for Image Saliency Detection." Thesis, The University of Sydney, 2017. http://hdl.handle.net/2123/17039.
Full textAbstract:
Saliency detection is a category of computer vision algorithms that aims to filter out the most salient object in a given image. Existing saliency detection methods can generally be categorized as bottom-up methods and top-down methods, and the prevalent deep neural network (DNN) has begun to show its applications in saliency detection in recent years. However, the challenges in existing methods, such as problematic pre-assumption, inefficient feature integration and absence of high-level feature learning, prevent them from superior performances. In this thesis, to address the limitations above, we have proposed multiple novel models with favorable performances. Specifically, we first systematically reviewed the developments of saliency detection and its related works, and then proposed four new methods, with two based on low-level image features, and two based on DNNs. The regularized random walks ranking method (RR) and its reversion-correction-improved version (RCRR) are based on conventional low-level image features, which exhibit higher accuracy and robustness in extracting the image boundary based foreground / background queries; while the background search and foreground estimation (BSFE) and dense and sparse labeling (DSL) methods are based on DNNs, which have shown their dominant advantages in high-level image feature extraction, as well as the combined strength of multi-dimensional features. Each of the proposed methods is evaluated by extensive experiments, and all of them behave favorably against the state-of-the-art, especially the DSL method, which achieves remarkably higher performance against sixteen state-of-the-art methods (including ten conventional methods and six learning based methods) on six well-recognized public datasets. The successes of our proposed methods reveal more potential and meaningful applications of saliency detection in real-life computer vision tasks.
13
Erten, Mehmet Sinan. "Network Based Prioritization of Disease Genes." Cleveland, Ohio : Case Western Reserve University, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=case1258743578.
Full textAbstract:
Thesis(M.S.)--Case Western Reserve University, 2009Title from PDF (viewed on 2010-01-28) Department of Electrical Engineering and Computer Science -- Computer and Information Sciences Includes abstract Includes bibliographical references and appendices Available online via the OhioLINK ETD Center
14
Battistoni, Luigi. "Sistemi dinamici stocastici su network." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2015. http://amslaurea.unibo.it/8950/.
Full textAbstract:
L'obiettivo della tesi è studiare la dinamica di un random walk su network. Essa è inoltre
suddivisa in due parti: la prima è prettamente teorica, mentre la seconda analizza
i risultati ottenuti mediante simulazioni.
La parte teorica è caratterizzata dall'introduzione di concetti chiave per comprendere
i random walk, come i processi di Markov e la Master Equation. Dopo aver fornito un
esempio intuitivo di random walk nel caso unidimensionale, tale concetto viene generalizzato.
Così può essere introdotta la Master Equation che determina l'evoluzione del
sistema. Successivamente si illustrano i concetti di linearità e non linearità, fondamentali
per la parte di simulazione.
Nella seconda parte si studia il comportamento di un random walk su network nel
caso lineare e non lineare, studiando le caratteristiche della soluzione stazionaria. La
non linearità introdotta simula un comportamento egoista da parte di popolazioni in
interazioni. In particolare si dimostra l'esistenza di una Biforcazione di Hopf.
15
Nanongkai, Danupon. "Graph and geometric algorithms on distributed networks and databases." Diss., Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/41056.
Full textAbstract:
In this thesis, we study the power and limit of algorithms on various models, aiming at applications in distributed networks and databases.
In distributed networks, graph algorithms are fundamental to many applications. We focus on computing random walks which are an important
primitive employed in a wide range of applications but has always been computed naively. We show that a faster solution exists and subsequently
develop faster algorithms by exploiting random walk properties leading to two immediate applications. We also show that this algorithm is optimal.
Our technique in proving a lower bound show the first non-trivial connection between communication complexity and lower bounds of distributed
graph algorithms. We show that this technique has a wide range of applications by proving new lower bounds of many problems. Some of these lower
bounds show that the existing algorithms are tight.
In database searching, we think of the database as a large set of multi-dimensional points stored in a disk and want to help the users to quickly find the most desired point. In this thesis, we develop an algorithm that is significantly faster than previous algorithms both theoretically and experimentally.
The insight is to solve the problem on the streaming model which helps emphasize the benefits of sequential access over random disk access. We also
introduced the randomization technique to the area. The results were complemented with a lower bound. We also initiat a new direction as an attempt to get a better query. We are the first to quantify the output quality using "user satisfaction" which is made possible by borrowing the idea of modeling users by utility functions from game theory and justify our approach through a geometric analysis.
16
Bagnato, Guilherme de Guzzi. "Análise estrutural de redes complexas modulares por meio de caminhadas auto-excludentes." Universidade de São Paulo, 2018. http://www.teses.usp.br/teses/disponiveis/76/76132/tde-21062018-152327/.
Full textAbstract:
O avanço das pesquisas em redes complexas proporcionou desenvolvimentos significativos para a compreensão de sistemas complexos. Uma rede complexa é modelada matematicamente por meio de um grafo, onde cada vértice representa uma unidade dinâmica e suas interações são simbolizadas por um conjunto de arestas. Para se determinar propriedades estruturais desse sistema, caminhadas aleatórias tem-se mostrado muito úteis pois dependem apenas de informações locais (vértices vizinhos). Entre elas, destaca-se o passeio auto-excludente (SAW) que possui a restrição de não visitar um vértice que já foi alcançado, ou seja, apresenta memória do caminho percorrido. Por este motivo o SAW tem apresentado melhores resultados do que caminhantes sem restrição, na exploração da rede. Entretanto, por não se tratar de um processo Markoviano ele apresenta grande complexidade analítica, tornando indispensável o uso de simulações computacionais para melhor compreensão de sua dinâmica em diferentes topologias. Mesmo com as dificuldades analíticas, o SAW se tornou uma ferramenta promissora na identificação de estruturas de comunidades. Apesar de sua importância, detecção de comunidades permanece um problema em aberto devido à alta complexidade computacional associada ao problema de optimização, além da falta de uma definição formal do significado de comunidade. Neste trabalho, propomos um método de detecção de comunidades baseado em SAW para extrair uma estrutura de comunidades da rede otimizando o parâmetro modularidade. Combinamos características extraídas desta dinâmica com a análise de componentes principais para posteriormente classificar os vértices em grupos por meio da clusterização hierárquica aglomerativa. Para avaliar a performance deste novo algoritmo, comparamos os resultados com outras quatro técnicas populares: Girvan-Newman, Fastgreedy, Walktrap e Infomap, aplicados em dois tipos de redes sintéticas e nove redes reais diversificadas e bem conhecidas. Para os benchmarks, esta nova técnica produziu resultados satisfatórios em diferentes combinações de parâmetros, como tamanho de rede, distribuição de grau e número de comunidades. Já para as redes reais, obtivemos valores de modularidade superior aos métodos tradicionais, indicando uma distribuição de grupos mais adequada à realidade. Feito isso, generalizamos o algoritmo para redes ponderadas e digrafos, além de incorporar metadados à estrutura topológica a fim de melhorar a classificação em grupos.The progress in complex networks research has provided significant understanding of complex systems. A complex network is mathematically modeled by a graph, where each vertex represents a dynamic unit and its interactions are symbolized by groups of edges. To determine the system structural properties, random walks have shown to be a useful tool since they depend only on local information (neighboring vertices). Among them, the selfavoiding walk (SAW) stands out for not visiting vertices that have already been reached, meaning it can record the path that has been travelled. For this reason, SAW has shown better results when compared to non-restricted walkers network exploration methods. However, as SAW is not a Markovian process, it has a great analytical complexity and needs computational simulations to improve its dynamics in different topologies. Even with the analytical complexity, SAW has become a promising tool to identify the community structure. Despite its significance, detecting communities remains an unsolved problem due to its high computational complexity associated to optimization issues and the lack of a formal definition of communities. In this work, we propose a method to identify communities based on SAW to extract community structure of a network through optimization of the modularity score. Combining technical features of this dynamic with principal components analyses, we classify the vertices in groups by using hierarchical agglomerative clustering. To evaluate the performance of this new algorithm, we compare the results with four other popular techniques: Girvan-Newman, Fastgreedy, Walktrap and Infomap, applying the algorithm in two types of synthetic networks and nine different and well known real ones. For the benchmarks, this new technique shows satisfactory results for different combination of parameters as network size, degree distribution and number of communities. As for real networks, our data shows better modularity values when compared to traditional methods, indicating a group distribution most suitable to reality. Furthermore, the algorithm was adapted for general weighted networks and digraphs in addition to metadata incorporated to topological structure, in order to improve the results of groups classifications.
17
Yorgancioglu, Kaan. "Using Anchor Nodes for Link Prediction." Case Western Reserve University School of Graduate Studies / OhioLINK, 2020. http://rave.ohiolink.edu/etdc/view?acc_num=case1578499802599777.
Full text
18
Pettinari, Tommaso. "Analisi della dinamica su network." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2021. http://amslaurea.unibo.it/24679/.
Full textAbstract:
Questa tesi si occupa di analizzare attraverso un approccio algebrico la dinamica di sistemi complessi descrivibili da network. Dopo aver definito concetti fondamentali per lo studio di un grafo, come la matrice di adiacenza e la matrice Laplaciana (e il relativo spettro), si mettono in relazione questi ultimi con le caratteristiche della dinamica degli elementi del sistema, in particolare per un tipo di dinamica diffusiva detto random walk. Di tale processo, considerato di rilevante importanza per via della sua applicabilità a numerosi fenomeni, se ne studiano l'esistenza e l'unicità delle soluzioni stazionarie e la risposta a perturbazioni dell'equilibrio.
I tipi di perturbazioni studiate sono di due categorie: perturbazioni della dinamica degli elementi del sistema rispetto allo stato stazionario, in cui viene tuttavia mantenuta fissa la struttura del network, oppure perturbazioni strutturali del network stesso, in cui sono gli stessi collegamenti tra i nodi a subire una modifica.
Attraverso alcune simulazioni numeriche vengono confermati sperimentalmente i principali risultati e, infine, si implementa un sistema di controllo basato su un algoritmo di adaptive learning capace di reagire a perturbazioni strutturali e riportare il sistema all'equilibrio originario.
19
Sinatra, Roberta. "High-order markov chains in complex networks: models and applications." Doctoral thesis, Università di Catania, 2012. http://hdl.handle.net/10761/935.
Full textAbstract:
Various complex systems such as the Internet and the World WideWeb, neural networks, the human society, chemical and biological systems are composed of highly interconnected dynamical units. Such systems can all be described as complex networks where the nodes represent the dynamic units, and two nodes are connected by an edge if the two units interact with each other. For most networks, the complexity arises from the fact that the structure is highly irregular, complex and dynamically evolving in time and that the observed patterns of interactions highly influence the behaviour of the entire system. However, despite this complexity, a large number of networks from diverse fields such as biology, sociology, economics or technology has been found to exhibit similar topological and dynamical features.
In this thesis we study different aspects of the structure and dynamics of complex networks by using approaches based on Markov and high-order Markov models. Regarding the structure of complex networks, we address the problem of the presence of three-body correlations between the node degrees in networks. Namely, we introduce measures to evaluate three-body correlations by using a third-order Markov model, and we study them in a wide range of real datasets. Then, we investigate how these correlations influence various dynamical processes. Specifically, we focus on Biased Random Walks (BRW), a class of Markovian stochastic processes which can be treated analytically and which extend the well-known concept of Random Walk on a network. In a BRW, the motion of walkers is biased accordingly to a generic topogical or dynamical node property. In particular, we investigate the connection between node-correlations in a network and the entropy rate that can be associated to the BRWs on the network. We also show how it is possible to rephrase a BRW process on a network as a plain RW on another network having the same topology but different weights associated to the edges, and we propose a number of applications where this conversion proves to be useful. In the final part of the thesis we apply the theory of complex networks and high-order Markov models to analyze and model data sets in three different contexts. First, we introduce a method to convert ensembles of sequences into networks. We apply this method to the study of the human proteome database, to detect hot topics from online social dialogs, and to characterize trajectories of dynamical systems. Second, we study mobility data of human agents moving on a network of a virtual world. We show that their trajectories have long-time memory, and how this influences the diffusion properties of the agents on the network. Finally, we study the topological properties of networks derived by EEG recordings on humans that interact by playing the prisoner's dilemma game.
20
Dionigi, Pierfrancesco. "A random matrix theory approach to complex networks." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2019. http://amslaurea.unibo.it/18513/.
Full textAbstract:
Si presenta un approccio matematico formale ai complex networks tramite l'uso della Random Matrix Theory (RMT). La legge del semicerchio di Wigner viene presentata come una generalizzazione del Teorema del Limite Centrale per determinati ensemble di matrici random. Sono presentati inoltre i principali metodi per calcolare la distribuzione spettrale delle matrici random e se ne sottolineano le differenze. Si è poi studiato come la RMT sia collegata alla Free Probability. Si è studiato come due tipi di grafi random apparentemente uguali, posseggono proprietà spettrali differenti analizzando le loro matrici di adiacenza. Da questa analisi si deducono alcune proprietà geometriche e topologiche dei grafi e si può analizzare la correlazione statistica tra i vertici. Si è poi costruito sul grafo un passeggiata aleatoria tramite catene di Markov, definendo la matrice di transizione del processo tramite la matrice di adiacenza del network opportunamente normalizzata. Infine si è mostrato come il comportamento dinamico della passeggiata aleatoria sia profondamente connesso con gli autovalori della matrice di transizione, e le principali relazioni sono mostrate.
21
Poirel, Christopher L. "Bridging Methodological Gaps in Network-Based Systems Biology." Diss., Virginia Tech, 2013. http://hdl.handle.net/10919/23899.
Full textAbstract:
Functioning of the living cell is controlled by a complex network of interactions among genes, proteins, and other molecules. A major goal of systems biology is to understand and explain the mechanisms by which these interactions govern the cell's response to various conditions. Molecular interaction networks have proven to be a powerful representation for studying cellular behavior. Numerous algorithms have been developed to unravel the complexity of these networks. Our work addresses the drawbacks of existing techniques. This thesis includes three related research efforts that introduce network-based approaches to bridge current methodological gaps in systems biology.
i. Functional enrichment methods provide a summary of biological functions that are overrepresented in an interesting collection of genes (e.g., highly differentially expressed genes between a diseased cell and a healthy cell). Standard functional enrichment algorithms ignore the known interactions among proteins. We propose a novel network-based approach to functional enrichment that explicitly accounts for these underlying molecular interactions. Through this work, we close the gap between set-based functional enrichment and topological analysis of molecular interaction networks.
ii. Many techniques have been developed to compute the response network of a cell. A recent trend in this area is to compute response networks of small size, with the rationale that only part of a pathway is often changed by disease and that interpreting small subnetworks is easier than interpreting larger ones. However, these methods may not uncover the spectrum of pathways perturbed in a particular experiment or disease. To avoid these difficulties, we propose to use algorithms that reconcile case-control DNA microarray data with a molecular interaction network by modifying per-gene differential expression p-values such that two genes connected by an interaction show similar changes in their gene expression values.
iii. Top-down analyses in systems biology can automatically find correlations among genes and proteins in large-scale datasets. However, it is often difficult to design experiments from these results. In contrast, bottom-up approaches painstakingly craft detailed models of cellular processes. However, developing the models is a manual process that can take many years. These approaches have largely been developed independently. We present Linker, an efficient and automated data-driven method that analyzes molecular interactomes. Linker combines teleporting random walks and k-shortest path computations to discover connections from a set of source proteins to a set of target proteins. We demonstrate the efficacy of Linker through two applications: proposing extensions to an existing model of cell cycle regulation in budding yeast and automated reconstruction of human signaling pathways. Linker achieves superior precision and recall compared to state-of-the-art algorithms from the literature.Ph. D.
22
Daines, Kyle. "Fall Risk Classification for People with Lower Extremity Amputations Using Machine Learning and Smartphone Sensor Features from a 6-Minute Walk Test." Thesis, Université d'Ottawa / University of Ottawa, 2020. http://hdl.handle.net/10393/40948.
Full textAbstract:
Falls are a leading cause of injury and accidental injury death worldwide. Fall-risk prevention techniques exist but fall-risk identification can be difficult. While clinical assessment tools are the standard for identifying fall risk, wearable-sensors and machine learning could improve outcomes with automated and efficient techniques. Machine learning research has focused on older adults. Since people with lower limb amputations have greater falling and injury risk than the elderly, research is needed to evaluate these approaches with the amputee population.
In this thesis, random forest and fully connected feedforward artificial neural network (ANN) machine learning models were developed and optimized for fall-risk identification in amputee populations, using smartphone sensor data (phone at posterior pelvis) from 89 people with various levels of lower-limb amputation who completed a 6-minute walk test (6MWT). The best model was a random forest with 500 trees, using turn data and a feature set selected using correlation-based feature selection (81.3% accuracy, 57.2% sensitivity, 94.9% specificity, 0.59 Matthews correlation coefficient, 0.83 F1 score). After extensive ANN optimization with the best ranked 50 features from an Extra Trees Classifier, the best ANN model achieved 69.7% accuracy, 53.1% sensitivity, 78.9% specificity, 0.33 Matthews correlation coefficient, and 0.62 F1 score.
Features from a single smartphone during a 6MWT can be used with random forest machine learning for fall-risk classification in lower limb amputees. Model performance was similarly effective or better than the Timed Up and Go and Four Square Step Test. This model could be used clinically to identify fall-risk individuals during a 6MWT, thereby finding people who were not intended for fall screening. Since model specificity was very high, the risk of accidentally misclassifying people who are a no fall-risk individual is quite low, and few people would incorrectly be entered into fall mitigation programs based on the test outcomes.
23
Pettarin, Alberto. "Graph Models of Information Spreading in Wireless Networks." Doctoral thesis, Università degli studi di Padova, 2012. http://hdl.handle.net/11577/3422448.
Full textAbstract:
This thesis investigates the structural properties of graph models of wireless networks, where autonomous agents communicate using radios in order to accomplish a predefined task. Ad hoc, sensor, and vehicle networks are perhaps the most familiar examples. The goal of this thesis is the analytical characterization of information spreading in graph models of wireless networks, since this fundamental process is a primitive needed to accomplish more complex tasks.
The well-established graph-based approaches adopted when analyzing
the behavior of “classical” distributed systems (e.g., P2P networks, computing clusters, etc.) fail to generalize to wireless networks, due to several causes, including the stricter physical constraints governing the operation of these systems (e.g., interference on the physical channel or scarce energy/computational resources) and the fact that the topology of the network might be unknown at design time or it might evolve over time.
This thesis shows how to tackle these problems by suitably defining
and rigorously analyzing graph models and graph processes capturing
the structure, evolution and operation of these networks. We present two
reference scenarios.
In the first one we study a family of random graphs known as Bluetooth Topology, which closely model the connectivity of a network built by
the device discovery phase of Bluetooth-like protocols, largely employed
in wireless networks. Formally, the Bluetooth Topology generalizes the
well-known Random Geometric Graph model, introducing a distributed
pruning of the edge set. We investigate the expansion and the diameter of
these graphs, as they quantify the bandwidth and the latency of a wireless
network. We give tight bounds on the expansion and, leveraging on these,
we prove nearly-tight bounds on the diameter. Our results show that the
Bluetooth Topology features the same global level of connectivity of the Random Geometric Graph but requires maintaining much fewer communication links.
Motivated by the recent and rapidly growing interest in mobile systems,
in the second part of the thesis we turn our attention to the dynamics of
information dissemination between agents performing random walks on
a planar grid and communicating over short distances. This setting can
also be employed to study phenomena like the spreading of a disease,
where infections are the result of local interactions between agents. We
prove that, for a sufficiently sparse system, the broadcast time of a message
is independent from the transmission radius; indeed, we show that the
broadcast time is dominated by the time needed for many agents to meet.
Our findings nicely complements previous results that dealt with dense
systems, where there is dependency from the transmission radius. Moreover,
our analysis techniques extend to similar mobility-communication models,
suggesting some interesting further research directions.Questa tesi studia le proprieta' strutturali di alcuni modelli a grafo di reti di agenti autonomi che comunicano via radio per completare un prefissato compito. Reti ad hoc, di sensori e veicolari sono forse gli esempi piu' immediati. Lo scopo di questa tesi e caratterizzare la diffusione dell’infor- mazione in questi modelli a grafo di reti wireless, considerata l’importanza di questo processo come primitiva fondamentale per realizzare protocolli piu' complessi. Gli approcci basati su tecniche combinatorie adottati per l’analisi di sistemi distribuiti “classici”, come le reti P2P o i cluster di calcolo, non possono essere estesi alle reti wireless, per varie ragioni: ad esempio a causa dei vincoli fisici che governano il funzionamento di questi sistemi (interferenza sul canale radio, scarse risorse energetiche/computazionali, ecc.) e per il fatto che la topologia della rete puo' essere ignota in fase di progettazione o puo' evolvere nel tempo. Questa tesi suggerisce come sia possibile affrontare tali problemi tramite l’opportuna definizione e l’analisi rigorosa di modelli a grafo (o processi su grafi) che catturino l’evoluzione e il funzionamento delle reti wireless. Mostriamo come sia possibile applicare quest’approccio a due scenari di riferimento. Innanzitutto studiamo una famiglia di grafi random nota come Bluetooth Topology, che ben rappresenta la connettivita' della rete creata dalla fase di device discovery in protocolli simili al Bluetooth, largamente utilizzati nelle reti wireless. Dal punto di vista formale, la Bluetooth Topology generalizza il ben noto modello Random Geometric Graph, introducendovi una selezione distribuita degli archi. Studiamo l’espansione e il diametro di questi grafi, poiche' quantificano la banda e la latenza della rete. Dimostriamo limiti stretti all’espansione e, sfruttando questa caratterizzazione, diamo dei limiti quasi stretti al diametro. I nostri risultati provano che la Bluetooth Topology presenta lo stesso livello globale di connettivita' del Random Geometric Graph, pur richiedendo molti meno link di comunicazione. Graph, pur richiedendo molti meno link di comunicazione. Motivati dal recente crescente interesse verso i sistemi mobili, nella seconda parte della tesi concentriamo la nostra attenzione sulle dinamiche di disseminazione dell’informazione tra agenti che effettuano random walk su una griglia planare e che comunicano su brevi distanze. Questo scenario puo' essere utilizzato per studiare fenomeni come la diffusione di malattie, dove le infezioni sono il risultato di interazioni locali tra gli agenti. Proviamo che, per un sistema sufficientemente sparso, il tempo di broadcast di un messaggio e indipendente dal raggio di trasmissione, dimostrando che esso e' dominato dal tempo necessario affinche' molti agenti si incontrino. I nostri risultati completano l’analisi, apparsa in lavori precedenti, di sistemi densi, dove viceversa vi e' dipendenza del tempo di broadcast dal raggio di trasmissione. Inoltre le nostre tecniche di analisi possono essere estese a modelli di mobilita'-comunicazione simili, suggerendo alcune interessanti linee di ulteriore ricerca.
24
Matteuzzi, Tommaso. "Network diffusion methods for omics big bio data analytics and interpretation with application to cancer datasets." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2017. http://amslaurea.unibo.it/13660/.
Full textAbstract:
Nella attuale ricerca biomedica un passo fondamentale verso una comprensione dei meccanismi alla radice di una malattia è costituito dalla identificazione dei disease modules, cioè quei sottonetwork dell'interattoma, il network delle interazioni tra proteine, con un alto numero di alterazioni geniche.
Tuttavia, l'incompletezza del network e l'elevata variabilità dei geni alterati rendono la soluzione di questo problema non banale.
I metodi fisici che sfruttano le proprietà dei processi diffusivi su network, dei quali mi sono occupato in questo lavoro di tesi, sono quelli che consentono di ottenere le migliori prestazioni.
Nella prima parte del mio lavoro, ho indagato la teoria relativa alla diffusione ed ai random walk su network, trovando interessanti relazioni con le tecniche di clustering e con altri modelli fisici la cui dinamica è descritta dalla matrice laplaciana.
Ho poi implementato un tecnica basata sulla diffusione su rete applicandola a dati di espressione genica e mutazioni somatiche di tre diverse tipologie di cancro.
Il metodo è organizzato in due parti. Dopo aver selezionato un sottoinsieme dei nodi dell'interattoma, associamo ad ognuno di essi un'informazione iniziale che riflette il "grado" di alterazione del gene. L'algoritmo di diffusione propaga l'informazione iniziale nel network raggiungendo, dopo un transiente, lo stato stazionario. A questo punto, la quantità di fluido in ciascun nodo è utilizzata per costruire un ranking dei geni. Nella seconda parte, i disease modules sono identificati mediante una procedura di network resampling.
L'analisi condotta ci ha permesso di identificare un numero consistente di geni già noti nella letteratura relativa ai tipi di cancro studiati, nonché un insieme di altri geni correlati a questi che potrebbero essere interessanti candidati per ulteriori approfondimenti.Attraverso una procedura di Gene Set Enrichment abbiamo infine testato la correlazione dei moduli identificati con pathway biologici noti.
25
Dejby, Jesper. "Capturing continuous human movement on a linear network with mobile phone towers." Thesis, Umeå universitet, Institutionen för matematik och matematisk statistik, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-136388.
Full textAbstract:
Anonymous Call Detail Records (CDR’s) from mobile phone towers provide a unique opportunity to aggregate individual location data to overall human mobility patterns. Flowminder uses this data to improve the welfare of low- and middle-income countries. The movement patterns are studied through key measurements of mobility. This thesis seeks to evaluate the estimates of key measurements obtained with mobile phone towers through simulation of continuous human movement on a linear network. Simulation is made with an agent based approach. Spatial point processes are used to distribute continuous start points of the agents on the linear network. The start point is then equipped with a mark, a path with an end point dependent on the start point. A path from the start point to the end point of an agent is modeled with a Markov Decision Process. The simulated human movement can then be captured with different types of mobile phone tower distributions realized from spatial point processes. The thesis will initially consider homogeneous Poisson and Simple Sequential Inhibition (SSI) processes on a plane and then introduce local clusters (heterogeneity) with Matérn Cluster and SSI processes. The goal of the thesis is to investigate the effects of change in mobile phone tower distribution and call frequency on the estimates of key measurements of mobility. The effects of call frequency are unclear and invite more detailed study. The results suggest that a decrease in the total number of towers generally worsens the estimates and that introducing local clusters also has a negative effect on the estimates. The presented methodology provides a flexible and new way to model continuous human movement along a linear network.
26
Coskun, Mustafa Coskun. "ALGEBRAIC METHODS FOR LINK PREDICTIONIN VERY LARGE NETWORKS." Case Western Reserve University School of Graduate Studies / OhioLINK, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=case1499436242956926.
Full text
27
Nykvist, Gustav. "Implementation of a Manycast Protocol in a Partitionable Mobile Ad hoc Network." Thesis, Linköping University, Department of Computer and Information Science, 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-20846.
Full textAbstract:
Wireless communication has grown very popular, and communication is the key
to success in many situations. However, most of the common technologies today
rely on infrastructure and in disaster situations infrastructure might be lost or
get severely overloaded. This master thesis concerns intermittently connected
mobile ad hoc networks. A network in which the devices may move freely in any
direction and still be able to communicate. To be able to demonstrate a network
protocol called random-walk gossip-based manycast (RWG) my assignment has been
to implement this protocol using off-the-shelf hardware and software.
RWG is a multi-hop and partition-tolerant mobile ad hoc manycast network
protocol. Multi-hop refers to information being able to hop between more than
two nodes in a network and partition-tolerant means that the protocol works even
though a network is partitioned. Manycast means that the information should
be successfully delivered to K of all the potential nodes in the area. The RWG
protocol makes use of four different packet types, request to forward (REQF), ac-
knowledgement (ACK), ok to forward (OKTF) and be silent (BS). The actual data
being sent is carried by REQFs, and is referred to as messages. When a message
is sent it takes what could be described as a random walk among the nodes in the
network, hence the name.
The implementation of the RWG protocol resides in user-space and depends on
the IEEE 802.11b standard and the raw socket that is specified in the BSD socket
API. It is written in C and was developed on a machine running Ubuntu. It runs
on systems that use Linux 2.6 kernels and it supports cross-compiling for ARM
based devices such as the Nokia N810 internet tablet and the Android dev phone
1. To be able to demonstrate the protocol I developed my own client application.
Moreover, an already existing application for Android, Portable Open Search and
Identification Tool (POSIT), was successfully extended to run on top of the RWG
implementation. The extension was developed by people in the POSIT project
and tested in a physical experiment covering five devices.
The report covers the RWG protocol, the system choice, the implementation
and the testing of the implementation.
28
Forghani, Behrang. "Transformed Random Walks." Thesis, Université d'Ottawa / University of Ottawa, 2015. http://hdl.handle.net/10393/32538.
Full textAbstract:
We consider transformations of a given random walk on a countable group determined by Markov stopping times. We prove that these transformations preserve the Poisson boundary. Moreover, under some mild conditions, the asymptotic entropy (resp., rate of escape) of the transformed random walks is equal to the asymptotic entropy (resp., rate of escape) of the original random walk multiplied by the expectation of the corresponding stopping time. This is an analogue of the well-known Abramov's formula from ergodic theory.
29
Gnacik, Michal. "Quantum random walks." Thesis, Lancaster University, 2014. http://eprints.lancs.ac.uk/69946/.
Full textAbstract:
In this thesis we investigate the convergence of various quantum random walks to quantum stochastic cocycles defined on a Bosonic Fock space. We prove a quantum analogue of the Donsker invariance principle by invoking the so-called semigroup representation of quantum stochastic cocycles. In contrast to similar results by other authors our proof is relatively elementary. We also show convergence of products of ampliated random walks with different system algebras; in particular, we give a sufficient condition to obtain a cocycle via products of cocycles. The CCR algebra, its quasifree representations and the corresponding quasifree stochastic calculus are also described. In particular, we study in detail gauge-invariant and squeezed quasifree states. We describe repeated quantum interactions between a `small' quantum system and an environment consisting of an infinite chain of particles. We study different cases of interaction, in particular those which occur in weak coupling limits and low density limits. Under different choices of scaling of the interaction part we show that random walks, which are generated by the associated unitary evolutions of a repeated interaction system, strongly converge to unitary quantum stochastic cocycles. We provide necessary and sufficient conditions for such convergence. Furthermore, under repeated quantum interactions, we consider the situation of an infinite chain of identical particles where each particle is in an arbitrary faithful normal state. This includes the case of thermal Gibbs states. We show that the corresponding random walks converge strongly to unitary cocycles for which the driving noises depend on the state of the incoming particles. We also use conditional expectations to obtain a simple condition, at the level of generators, which suffices for the convergence of the associated random walks. Limit cocycles, for which noises depend on the state of the incoming particles, are also obtained by investigating what we refer to as `compressed' random walks. Lastly, we show that the cocycles obtained via the procedure of repeated quantum interactions are quasifree, thus the driving noises form a representation of the relevant CCR algebra. Both gauge-invariant and squeezed representations are shown to occur.
30
Ramiro-Cid, Victor. "Caractérisation et applications de marches aléatoires temporelles dans les réseaux opportunistes." Thesis, Toulouse, ISAE, 2015. http://www.theses.fr/2015ESAE0023/document.
Full textAbstract:
L’Internet a complètement révolutionné la façon dont nous communiquons. En parallèle, la croissance importante des réseaux mobiles s'est accompagnée d'une explosion du nombre d’usagers et d'une augmentation exponentielle de la demande. Cependant, l’Internet n'est pas encore, voire n'est pas toujours, universellement accessible. Par exemple, c'est le cas en ce qui concerne l’accès dans les économies émergentes ou dans les régions éloignées, les obstacles physiques empêchant le déploiement de réseaux mobiles et les désastres naturels. C'est dans ce contexte que les réseaux tolérants au délai ont été introduits pour faire face aux environnements caractérisés par des interruptions et des délais de transmission élevés. Ces réseaux, manquent souvent de routes pré-déterminées ou même de toute infrastructure pour permettre une communication de bout-en-bout. Dans ce contexte, tous les nœuds de ces réseaux peuvent interagir en utilisant leurs contacts comme une opportunité de communication. Le paradigme stockage/transport permet à ces nœuds d’exploiter des chemins spatio-temporels créés par ces possibilités de contact afin de livrer des messages au fil du temps. Dans ce travail, nous soulevons ici une question générique : pouvons-nous concevoir une infrastructure mobile et opportuniste qui pourrait aider à transmettre ces messages ? Afin de fournir une telle infrastructure, nous étudions l’application des marches aléatoires temporelles (TRWs) dans réseaux opportunistes. Nous explorons l’application et l’impact de la TRW pour fournir une infrastructure minimale et non-invasive à partir de deux points de vue : le stockage des données et leur transmissionThe Internet has entirely reshaped the way we communicate and interact with one another. The rapid development of the wireless infrastructure by network providers has being accompanied by an exponential growth in the number of mobile users. However, global Internet access and connectivity still face several challenges: scarce or poor quality connectivity in developing countries or places with limited accessibility, physical obstacles limiting the deployment of wireless networks and natural or man-made disasters. Delay tolerant networks (DTNs) were introduced to deal with environments where interruptions or disruptions of service were expected. Such networks usually lack of end-to-end paths or any infrastructure to help communications. In these networks, mobile nodes may interact using their contacts as a communication opportunity. The store-carry-forward paradigm allows nodes to exploit spatio-temporal paths created by contact opportunities in order to deliver messages over time. Instead we raise the question: can we design a mobile and opportunistic infrastructure that could help deliver messages? In the quest to provide such infrastructure, we study the application of temporal random walks (TRW) over the opportunistic networks. We explore the application and impact of TRW as a minimal and non invasive infrastructure from two points of view: data forwarding and data recollection/transmission
31
Windisch, David. "Random walks, disconnection and random interlacements /." [S.l.] : [s.n.], 2009. http://e-collection.ethbib.ethz.ch/show?type=diss&nr=18343.
Full text
32
Phetpradap, Parkpoom. "Intersections of random walks." Thesis, University of Bath, 2011. https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.548100.
Full textAbstract:
We study the large deviation behaviour of simple random walks in dimension three or more in this thesis. The first part of the thesis concerns the number of lattice sites visited by the random walk. We call this the range of the random walk. We derive a large deviation principle for the probability that the range of simple random walk deviates from its mean. Our result describes the behaviour for deviation below the typical value. This is a result analogous to that obtained by van den Berg, Bolthausen, and den Hollander for the volume of the Wiener sausage. In the second part of the thesis, we are interested in the number of lattice sites visited by two independent simple random walks starting at the origin. We call this the intersection of ranges. We derive a large deviation principle for the probability that the intersection of ranges by time n exceeds a multiple of n. This is also an analogous result of the intersection volume of two independent Wiener sausages.
33
Oosthuizen, Joubert. "Random walks on graphs." Thesis, Stellenbosch : Stellenbosch University, 2014. http://hdl.handle.net/10019.1/86244.
Full textAbstract:
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.
34
Montgomery, Aaron. "Topics in Random Walks." Thesis, University of Oregon, 2013. http://hdl.handle.net/1794/13335.
Full textAbstract:
We study a family of random walks defined on certain Euclidean lattices that are related to incidence matrices of balanced incomplete block designs. We estimate the return probability of these random walks and use it to determine the asymptotics of the number of balanced incomplete block design matrices. We also consider the problem of collisions of independent simple random walks on graphs. We prove some new results in the collision problem, improve some existing ones, and provide counterexamples to illustrate the complexity of the problem.
35
Touray, Barra. "Energy-efficient routing algorithms for wireless sensor networks." Thesis, Liverpool John Moores University, 2013. http://researchonline.ljmu.ac.uk/4352/.
Full textAbstract:
A wireless sensor network (WSN) is made of tiny sensor nodes usually deployed in high density within a targeted area to monitor a phenomenon of interest such as temperature, vibration or humidity. The WSNs can be employed in various applications (e.g., Structural monitoring, agriculture, environment monitoring, machine health monitoring, military, and health). For each application area there are different technical issues and remedies. Various challenges need to be considered while setting up a WSN, including limited computing, memory and energy resources, wireless channel errors and network scalability. One way of addressing these problems is by implementing a routing protocol that efficiently uses these limited resources and hence reduces errors, improves scalability and increases the network lifetime. The topology of any network is important and wireless sensor networks (WSNs) are no exception. In order to effectively model an energy-efficient routing algorithm, the topology of the WSN must be factored in. However, little work has been done on routing for WSNs with regular patterned topologies, except for the shortest path first (SPF) routing algorithms. The issue with the SPF algorithm is that it requires global location information of the nodes from the sensor network, which proves to be a drain on the network resources. In this thesis a novel algorithm namely, BRALB (Biased Random Algorithm for Load Balancing) is proposed to overcome the issues faced in routing data within WSNs with regular topologies such as square-base topology and triangle-based topology. It is based on random walk and probability. The proposed algorithm uses probability theory to build a repository of information containing the estimate of energy resources in each node, in order to route packets based on the energy resources in each node and thus does not require any global information from the network. It is shown in this thesis by statistical analysis and simulations that BRALB uses the same energy as the shortest path first routing as long as the data packets are comparable in size to the inquiry packets used between neighbours. It is also shown to balance the load (i.e. the packets to be sent) efficiently among the nodes in the network. In most of the WSN applications the messages sent to the base station are very small in size. Therefore BRALB is viable and can be used in sensor networks employed in such applications. However, one of the constraints of BRALB is that it is not very scalable; this is a genuine concern as most WSNs deployment is large scale. In order to remedy this problem, C-BRALB (Clustered Biased Random Algorithm for Load Balancing) has been proposed as an extension of BRALB with clustering mechanism. The same clustering technique used in Improved Directed Diffusion (IDD) has been adopted for C-BRALB. The routing mechanism in C-BRALB is based on energy biased random walk. This algorithm also does not require any global information apart from the initial flooding initiated by the sink to create the clusters. It uses probability theory to acquire all the information it needs to route packets based on energy resources in each cluster head node. It is shown in this thesis by using both simulations and statistical analysis that C-BRALB is an efficient routing algorithm in applications where the message to be sent is comparable to the inquiry message among the neighbours. It is also shown to balance the load (i.e. the packets to be sent) among the neighbouring cluster head nodes.
36
Powell, Sean K. "A quantitative study of diffusion in quasi-periodic fibre networks and complex porous media." Thesis, Queensland University of Technology, 2016. https://eprints.qut.edu.au/92506/12/92506%28thesis%29.pdf.
Full textAbstract:
Diffusion is the fundamental process behind many molecular phenomena such as the mixing of substances. Its physical basis is the random motion of particles in a fluid. In complex porous media, diffusion is restricted by interactions with internal structures. In this work, we present studies of restricted diffusion that aim to efficiently produce quantitative models for obtaining detailed information about the morphology of biological porous media from diffusion tensor imaging experiments. We achieved this by developing a Langevin dynamics algorithm to provide physically realistic modelling of water/barrier interactions and the Lattice-Path Count algorithm to enumerate all available particle trajectories to evaluate molecular transport properties. We also performed diffusion tensor imaging experiments of the fibre networks of tissue engineering scaffolds. The findings of this thesis provide further insight into the physics underlying restricted diffusion.
37
Buckley, Stephen Philip. "Problems in random walks in random environments." Thesis, University of Oxford, 2011. http://ora.ox.ac.uk/objects/uuid:06a12be2-b831-4c2a-87b1-f0abccfb9b8b.
Full textAbstract:
Recent years have seen progress in the analysis of the heat kernel for certain reversible random walks in random environments. In particular the work of Barlow(2004) showed that the heat kernel for the random walk on the infinite component of supercritical bond percolation behaves in a Gaussian fashion. This heat kernel control was then used to prove a quenched functional central limit theorem. Following this work several examples have been analysed with anomalous heat kernel behaviour and, in some cases, anomalous scaling limits. We begin by generalizing the first result - looking for sufficient conditions on the geometry of the environment that ensure standard heat kernel upper bounds hold. We prove that these conditions are satisfied with probability one in the case of the random walk on continuum percolation and use the heat kernel bounds to prove an invariance principle. The random walk on dynamic environment is then considered. It is proven that if the environment evolves ergodically and is, in a certain sense, geometrically d-dimensional then standard on diagonal heat kernel bounds hold. Anomalous lower bounds on the heat kernel are also proven - in particular the random conductance model is shown to be "more anomalous" in the dynamic case than the static. Finally, the reflected random walk amongst random conductances is considered. It is shown in one dimension that under the usual scaling, this walk converges to reflected Brownian motion.
38
Bowditch, Adam. "Biased randomly trapped random walks and applications to random walks on Galton-Watson trees." Thesis, University of Warwick, 2017. http://wrap.warwick.ac.uk/97359/.
Full textAbstract:
In this thesis we study biased randomly trapped random walks. As our main motivation, we apply these results to biased walks on subcritical Galton-Watson trees conditioned to survive. This application was initially considered model in its own right. We prove conditions under which the biased randomly trapped random walk is ballistic, satisfies an annealed invariance principle and a quenched central limit theorem with environment dependent centring. We also study the regime in which the walk is sub-ballistic; in this case we prove convergence to a stable subordinator. Furthermore, we study the fluctuations of the walk in the ballistic but sub-diffusive regime. In this setting we show that the walk can be properly centred and rescaled so that it converges to a stable process. The biased random walk on the subcritical GW-tree conditioned to survive fits suitably into the randomly trapped random walk model; however, due to a lattice effect, we cannot obtain such strong limiting results. We prove conditions under which the walk is ballistic, satisfies an annealed invariance principle and a quenched central limit theorem with environment dependent centring. In these cases the trapping is weak enough that the lattice effect does not have an influence; however, in the sub-ballistic regime it is only possible to obtain converge along specific subsequences. We also study biased random walks on infinite supercritical GW-trees with leaves. In this setting we determine critical upper and lower bounds on the bias such that the walk satisfies a quenched invariance principle.
39
Ngoc, Anh Do Hoang. "Anomalous diffusion and random walks on random fractals." Doctoral thesis, Universitätsbibliothek Chemnitz, 2010. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-201000205.
Full textAbstract:
The purpose of this research is to investigate properties of diffusion processes
in porous media. Porous media are modelled by random Sierpinski carpets,
each carpet is constructed by mixing two different generators with the same
linear size. Diffusion on porous media is studied by performing random
walks on random Sierpinski carpets and is characterized by the random walk
dimension $d_w$.
In the first part of this work we study $d_w$ as a function of the ratio of constituents
in a mixture. The simulation results show that the resulting $d_w$ can
be the same as, higher or lower than $d_w$ of carpets made by a single constituent
generator. In the second part, we discuss the influence of static external
fields on the behavior of diffusion. The biased random walk is used to model
these phenomena and we report on many simulations with different field
strengths and field directions. The results show that one structural feature
of Sierpinski carpets called traps can have a strong influence on the observed
diffusion properties. In the third part, we investigate the effect of diffusion
under the influence of external fields which change direction back and forth
after a certain duration. The results show a strong dependence on the period
of oscillation, the field strength and structural properties of the carpet.
40
Gabucci, Ilenia. "Random walks classici e quantistici." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2019. http://amslaurea.unibo.it/17759/.
Full textAbstract:
Questa tesi si propone di fornire uno studio sul random walk. Partendo da un approfondimento sulla teoria della probabilita` alla base di tale processo ed in particolare le distribuzioni Binomiale e Gaussiana, si `e potuto studiare il caso del random walk classico, sia nel caso del reticolo monodimensionale che per reticoli a piu` dimensioni. Sempre nell’ambito classico si sono analizzati anche i processi stocastici dipendenti dal tempo, detti Processi di Markov, e il moto browniano, per cui si sono ricavate le equazioni del moto della particella browniana, ovvero le equazioni di Langevin. Si sono in seguito definiti i quattro postulati della meccanica quantistica, introducendo il concetto di quantum bit, per cui si `e fornito un confronto con il bit classico. Si `e inoltre trattato il calcolo quantistico, definendo il concetto di porta logica e affrontando l’esempio importante del gate di Hadamard, utile nel caso del random walk quantistico. Quest’ultimo `e stato introdotto separando il caso nel discreto e nel continuo, cercando di sottolineare le differenze che presenta con il caso classico.
41
Codling, Edward Alexander. "Biased random walks in biology." Thesis, University of Leeds, 2003. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.275673.
Full text
42
Janse, van Rensburg Esaias Johannes. "Field theory and random walks." Thesis, University of Cambridge, 1987. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.328723.
Full text
43
Kazhuthuveettil, Sreedharan Jithin. "Échantillonnage et inférence dans réseaux complexes." Thesis, Université Côte d'Azur (ComUE), 2016. http://www.theses.fr/2016AZUR4121/document.
Full textAbstract:
L’émergence récente de grands réseaux, surtout réseaux sociaux en ligne (OSN), a révélé la difficulté de crawler le réseau complet et a déclenché le développement de nouvelles techniques distribuées. Dans cette thèse, nous concevons et analysons des algorithmes basés sur les marches aléatoires et la diffusion pour l'échantillonnage, l'estimation et l'inférence des fonctions des réseaux. La thèse commence par le problème classique de trouver les valeurs propres dominants et leurs vecteurs propres de matrices de graphe symétriques, comme la matrice Laplacienne de graphes non orientés. En utilisant le fait que le spectre est associé à une équation de type différentiel Schrödinger, nous développons des techniques évolutives à l’aide de la diffusion sur le graphe. Ensuite, nous considérons l’échantillonnage des fonctions de réseau (comme somme et moyenne) en utilisant les marches aléatoires sur le graphe. Afin d'éviter le temps «burn-in» de marche aléatoire, avec l'idée de régénération à un nœud fixe, nous développons un estimateur de la fonction de somme qui est non asymptotiquement non-biaisé et dérivons une approximation à la postérieure Bayésienne. La dernière partie de la thèse étudie l'application de la théorie des valeurs extrêmes pour faire une inférence sur les événements extrêmes à partir des échantillons stationnaires des différentes marches aléatoires pour l’échantillonnage de réseauThe recent emergence of large networks, mainly due to the rise of online social networks, brought out the difficulty to gather a complete picture of a network and it prompted the development of new distributed techniques. In this thesis, we design and analyze algorithms based on random walks and diffusion for sampling, estimation and inference of the network functions, and for approximating the spectrum of graph matrices. The thesis starts with the classical problem of finding the dominant eigenvalues and the eigenvectors of symmetric graph matrices like Laplacian of undirected graphs. Using the fact that the eigenspectrum is associated with a Schrödinger-type differential equation, we develop scalable techniques with diffusion over the graph and with gossiping algorithms. They are also adaptable to a simple algorithm based on quantum computing. Next, we consider sampling and estimation of network functions (sum and average) using random walks on graph. In order to avoid the burn-in time of random walks, with the idea of regeneration at its revisits to a fixed node, we develop an estimator for the aggregate function which is non-asymptotically unbiased and derive an approximation to its Bayesian posterior. An estimator based on reinforcement learning is also developed making use of regeneration. The final part of the thesis deals with the use of extreme value theory to make inference from the stationary samples of the random walks. Extremal events such as first hitting time of a large degree node, order statistics and mean cluster size are well captured in the parameter “extremal index”. We theoretically study and estimate extremal index of different random walk sampling techniques
44
Dou, Carl C. Z. (Carl Changzhu). "Studies of random walks on groups and random graphs." Thesis, Massachusetts Institute of Technology, 1992. http://hdl.handle.net/1721.1/13243.
Full text
45
Ma, Qi. "Reinforcement in Biology : Stochastic models of group formation and network construction." Doctoral thesis, Uppsala universitet, Analys och tillämpad matematik, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-186989.
Full textAbstract:
Empirical studies show that similar patterns emerge from a large number of different biological systems. For example, the group size distributions of several fish species and house sparrows all follow power law distributions with an exponential truncation. Networks built by ant colonies, slime mold and those are designed by engineers resemble each other in terms of structure and transportation efficiency. Based on the investigation of experimental data, we propose a variety of simple stochastic models to unravel the underlying mechanisms which lead to the collective phenomena in different systems. All the mechanisms employed in these models are rooted in the concept of selective reinforcement. In some systems the reinforcement can build optimal solutions for biological problem solving. This thesis consists of five papers. In the first three papers, I collaborate with biologists to look into group formation in house sparrows and the movement decisions of damsel fish. In the last two articles, I look at how shortest paths and networks are constructed by slime molds and pheromone laying ants, as well as studying speed-accuracy tradeoffs in slime molds' decision making. The general goal of the study is to better understand how macro level patterns and behaviors emerges from micro level interactions in both spatial and non-spatial biological systems. With the combination of mathematical modeling and experimentation, we are able to reproduce the macro level patterns in the studied biological systems and predict behaviors of the systems using minimum number of parameters.
46
Bertacchi, D., and Andreas Cap@esi ac at. "Random Walks on Diestel--Leader Graphs." ESI preprints, 2001. ftp://ftp.esi.ac.at/pub/Preprints/esi1004.ps.
Full text
47
Dykiel, Patrik. "Asymptotic properties of coalescing random walks." Thesis, Uppsala University, Department of Mathematics, 2005. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-121369.
Full text
48
He, Mu. "The Torsion Angle of Random Walks." TopSCHOLAR®, 2013. http://digitalcommons.wku.edu/theses/1242.
Full textAbstract:
In this thesis, we study the expected mean of the torsion angle of an n-stepequilateral random walk in 3D. We consider the random walk is generated within a confining sphere or without a confining sphere: given three consecutive vectors →e1 , →e2 , and →e3 of the random walk then the vectors →e1 and →e2 define a plane and the vectors →e2 and →e3 define a second plane. The angle between the two planes is called the torsion angle of the three vectors. Algorithms are described to generate random walks which are used in a particular space (both without and with confinement). The torsion angle is expressed as a function of six variables for a random walk in both cases: without confinement and with confinement, respectively. Then we find the probability density functions of these six variables of a random walk and demonstrate an explicit integral expression for the expected mean torsion value. Finally, we conclude that the expected torsion angle obtained by the integral agrees with the numerical average torsion obtained by a simulation of random walks with confinement.
49
Deligiannidis, Georgios. "Some results associated with random walks." Thesis, University of Nottingham, 2010. http://eprints.nottingham.ac.uk/13104/.
Full textAbstract:
In this thesis we treat three problems from the theory and applications of random walks. The first question we tackle is from the theory of the optimal stopping of random walks. We solve the infinite-horizon optimal stopping problem for a class of reward functions admitting a representation introduced in Boyarchenko and Levendorskii [1], and obtain closed expressions for the expected reward and optimal stopping time. Our methodology is a generalization of an early paper by Darling et al. [2] and is based on probabilistic techniques: in particular a path decomposition related to the Wiener-Hopf factorization. Examples from the literature and perturbations are treated to demonstrate the flexibility of our approach. The second question is related to the path structure of lattice random walks. We obtain the exact asymptotics of the variance of the self- intersection local time Vn which counts the number of times the paths of a random walk intersect themselves. Our approach extends and improves upon that of Bolthausen [3], by making use of complex power series. In particular we state and prove a complex Tauberian lemma, which avoids the assumption of monotonicity present in the classical Tauberian theorem. While a bound of order 0(n2) has previously been claimed in the literature ([3], [4]) we argue that existing methods only show the tipper bound O(n2 log n), unless extra conditions are imposed to ensure monotonicity of the underlying sequence. Using the complex Tauberian approach we show that Var (Vn ) Cn2, thus settling a long-standing misunderstanding. Finally, in the last chapter, we prove a functional central limit theorem for one-dimensional random walk in random scenery, a result conjectured in 1979 by Kesten and Spitzer [5]. Essentially random walk in random scenery is the process defined by the partial suins of a collection of random variables (the random scenery), sampled by a random walk. We show that for Z-valued random walk attracted to the symmetric Cauchy law, and centered random scenery with second moments, a functional central limit theorem holds, thus proving the Kesten and Spitzer [5] conjecture which had remained open since 1979. Our proof makes use of tile asymptotic results obtained in the Chapter 3.
50
Xu, Chang. "Convex hulls of planar random walks." Thesis, University of Strathclyde, 2017. http://digitool.lib.strath.ac.uk:80/R/?func=dbin-jump-full&object_id=28164.
Full textAbstract:
For the perimeter length Ln and the area An of the convex hull of the first n steps of a planar random walk, this thesis study n â mean and variance asymptotics and establish distributional limits. The results apply to random walks both with drift (the mean of random walk increments) and with no drift under mild moments assumptions on the increments. Assuming increments of the random walk have finite second moment and non zero mean, Snyder and Steele showed that nâ1Ln converges almost surely to a deterministic limit, and proved an upper bound on the variance Var[Ln] = O(n).We show that nâ1Var[Ln] converges and give a simple expression for the limit,which is non-zero for walks outside a certain degenerate class. This answers a question of Snyder and Steele. Furthermore, we prove a central limit theorem for Ln in the non-degenerate case. Then we focus on the perimeter length with no drift and area with both drift and zero-drift cases. These results complement and contrast with previous work and establish non-Gaussian distributional limits. We deduce these results from weak convergence statements for the convex hulls of random walks to scaling limits defined in terms of convex hulls of certain Brownian motions. We give bounds that confirm that the limiting variances in our results are non-zero.