Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSimple Random Walks on Radio Networks (Simple Random Walks on Hyper-Graphs)
163
0
0.0
(
0
)
Added by
Chen Avin
Publication date
2009
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In recent years, protocols that are based on the properties of random walks on graphs have found many applications in communication and information networks, such as wireless networks, peer-to-peer networks and the Web. For wireless networks (and other networks), graphs are actually not the correct model of the communication; instead hyper-graphs better capture the communication over a wireless shared channel. Motivated by this example, we study in this paper random walks on hyper-graphs. First, we formalize the random walk process on hyper-graphs and generalize key notions from random walks on graphs. We then give the novel definition of radio cover time, namely, the expected time of a random walk to be heard (as opposed to visit) by all nodes. We then provide some basic bounds on the radio cover, in particular, we show that while on graphs the radio cover time is O(mn), in hyper-graphs it is O(mnr) where n, m and r are the number of nodes, the number of edges and the rank of the hyper-graph, respectively. In addition, we define radio hitting times and give a polynomial algorithm to compute them. We conclude the paper with results on specific hyper-graphs that model wireless networks in one and two dimensions.
rate research
Read More
We present an analytical method for computing the mean cover time of a random walk process on arbitrary, complex networks. The cover time is defined as the time a random walker requires to visit every node in the network at least once. This quantity is particularly important for random search processes and target localization in network topologies. Based on the global mean first passage time of target nodes we derive an estimate for the cumulative distribution function of the cover time based on first passage time statistics. We show that our result can be applied to various model networks, including ErdH{o}s-Renyi and Barabasi-Albert networks, as well as various real-world networks. Our results reveal an intimate link between first passage and cover time statistics in networks in which structurally induced temporal correlations decay quickly and offer a computationally efficient way for estimating cover times in network related applications.
We prove new results on lazy random walks on finite graphs. To start, we obtain new estimates on return probabilities $P^t(x,x)$ and the maximum expected hitting time $t_{rm hit}$, both in terms of the relaxation time. We also prove a discrete-time version of the first-named authors ``Meeting time lemma~ that bounds the probability of random walk hitting a deterministic trajectory in terms of hitting times of static vertices. The meeting time result is then used to bound the expected full coalescence time of multiple random walks over a graph. This last theorem is a discrete-time version of a result by the first-named author, which had been previously conjectured by Aldous and Fill. Our bounds improve on recent results by Lyons and Oveis-Gharan; Kanade et al; and (in certain regimes) Cooper et al.
Random walks constitute a fundamental mechanism for many dynamics taking place on complex networks. Besides, as a more realistic description of our society, multiplex networks have been receiving a growing interest, as well as the dynamical processes that occur on top of them. Here, inspired by one specific model of random walks that seems to be ubiquitous across many scientific fields, the Levy flight, we study a new navigation strategy on top of multiplex networks. Capitalizing on spectral graph and stochastic matrix theories, we derive analytical expressions for the mean first passage time and the average time to reach a node on these networks. Moreover, we also explore the efficiency of Levy random walks, which we found to be very different as compared to the single layer scenario, accounting for the structure and dynamics inherent to the multiplex network. Finally, by comparing with some other important random walk processes defined on multiplex networks, we find that in some region of the parameters, a Levy random walk is the most efficient strategy. Our results give us a deeper understanding of Levy random walks and show the importance of considering the topological structure of multiplex networks when trying to find efficient navigation strategies.
We study random walks on the giant component of the ErdH{o}s-Renyi random graph ${cal G}(n,p)$ where $p=lambda/n$ for $lambda>1$ fixed. The mixing time from a worst starting point was shown by Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald, to have order $log^2 n$. We prove that starting from a uniform vertex (equivalently, from a fixed vertex conditioned to belong to the giant) both accelerates mixing to $O(log n)$ and concentrates it (the cutoff phenomenon occurs): the typical mixing is at $( u {bf d})^{-1}log n pm (log n)^{1/2+o(1)}$, where $ u$ and ${bf d}$ are the speed of random walk and dimension of harmonic measure on a ${rm Poisson}(lambda)$-Galton-Watson tree. Analogous results are given for graphs with prescribed degree sequences, where cutoff is shown both for the simple and for the non-backtracking random walk.
Random walks have been proven to be useful for constructing various algorithms to gain information on networks. Algorithm node2vec employs biased random walks to realize embeddings of nodes into low-dimensional spaces, which can then be used for tasks such as multi-label classification and link prediction. The usefulness of node2vec in these applications is considered to be contingent upon properties of random walks that the node2vec algorithm uses. In the present study, we theoretically and numerically analyze random walks used by the node2vec. The node2vec random walk is a second-order Markov chain. We exploit the mapping of its transition rule to a transition probability matrix among directed edges to analyze the stationary probability, relaxation times, and coalescence time. In particular, we provide a multitude of evidence that node2vec random walk accelerates diffusion when its parameters are tuned such that walkers avoid both back-tracking and visiting a neighbor of the previously visited node, but not excessively.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
