Motivated by the growing interest in mobile systems, we study the dynamics of information dissemination between agents moving independently on a plane. Formally, we consider @math mobile agents performing independent random walks on an @math -node grid. At time @math , each agent is located at a random node of the grid and one agent has a rumor. The spread of the rumor is governed by a dynamic communication graph process @math , where two agents are connected by an edge in @math iff their distance at time @math is within their transmission radius @math . Modeling the physical reality that the speed of radio transmission is much faster than the motion of the agents, we assume that the rumor can travel throughout a connected component of @math before the graph is altered by the motion. We study the broadcast time @math of the system, which is the time it takes for all agents to know the rumor. We focus on the sparse case (below the percolation point @math ) where, with high probability, no connected component in @math has more than a logarithmic number of agents and the broadcast time is dominated by the time it takes for many independent random walks to meet each other. Quite surprisingly, we show that for a system below the percolation point the broadcast time does not depend on the relation between the mobility speed and the transmission radius. In fact, we prove that @math for any @math , even when the transmission range is significantly larger than the mobility range in one step, giving a tight characterization up to logarithmic factors. Our result complements a recent result of (SODA 2011) who showed that above the percolation point the broadcast time is polylogarithmic in @math .
A model similar to our scenario is often employed to represent the spreading of computer viruses in networks and the spreading time is also referred to as . Kesten and Sidoravicius @cite_9 characterized the rate at which an infection spreads among particles performing continuous-time random walks with the same jump rate. In @cite_6 , the authors provide a general bound on the average infection time when @math agents (one of them initially affected by the virus) move in an @math -node graph. For general graphs, this bound is @math , where @math denotes the maximum average meeting time of two random walks on the graph, and the maximum is taken over all pairs of starting locations of the random walks. Also, in the paper tighter bounds are provided for the complete graph and for expanders. Observe that the @math bound specializes to @math for the @math -node grid by applying the known bound on @math of @cite_18 . A tight bound of @math on the infection time on the grid is claimed in @cite_0 , based on a rather informal argument where some unwarranted independence assumptions are made. Our results show that this latter bound is incorrect.
@cite_0 @cite_9 @cite_18 @cite_6
2398538542 1974210749 2109426593 2170926923
The spread of epidemics and malware is commonly modeled by diffusion processes on networks. Protective interventions such as vaccinations or installing anti-virus software are used to contain their spread. Typically, each node in the network has to decide its own strategy of securing itself, and its benefit depends on which other nodes are secure, making this a natural game-theoretic setting. There has been a lot of work on network security game models, but most of the focus has been either on simplified epidemic models or homogeneous network structure. We develop a new formulation for an epidemic containment game, which relies on the characterization of the SIS model in terms of the spectral radius of the network. We show in this model that pure Nash equilibria (NE) always exist, and can be found by a best response strategy. We analyze the complexity of finding NE, and derive rigorous bounds on their costs and the Price of Anarchy or PoA (the ratio of the cost of the worst NE to the optimum social cost) in general graphs as well as in random graph models. In particular, for arbitrary power-law graphs with exponent β > 2, we show that the PoA is bounded by O(T2(β -1))), where T = γ α is the ratio of the recovery rate to the transmission rate in the SIS model. We prove that this bound is tight up to a constant factor for the Chung-Lu random power-law graph model. We study the characteristics of Nash equilibria empirically in different real communication and infrastructure networks, and find that our analytical results can help explain some of the empirical observations. Consider k particles, 1 red and k - 1 white, chasing each other on the nodes of a graph G. If the red one catches one of the white, it "infects" it with its color. The newly red particles are now available to infect more white ones. When is it the case that all white will become red? It turns out that this simple question is an instance of information propagation between random walks and has important applications to mobile computing where a set of mobile hosts acts as an intermediary for the spread of information. In this paper we model this problem by k concurrent random walks, one corresponding to the red particle and k - 1 to the white ones. The infection time Tk of infecting all the white particles with red color is then a random variable that depends on k, the initial position of the particles, the number of nodes and edges of the graph, as well as on the structure of the graph. In this work we develop a set of probabilistic tools that we use to obtain upper bounds on the (worst case w.r.t. initial positions of particles) expected value of Tk for general graphs and important special cases. We easily get that an upper bound on the expected value of Tk is the worst case (over all initial positions) expected meeting time m* of two random walks multiplied by Θ(log k). We demonstrate that this is, indeed, a tight bound; i.e. there is a graph G (a special case of the "lollipop" graph), a range of values k < n (such that √n - k = Θ(√n)) and an initial position of particles achieving this bound. When G is a clique or has nice expansion properties, we prove much smaller bounds for Tk. We have evaluated and validated all our results by large scale experiments which we also present and discuss here. In particular, the experiments demonstrate that our analytical results for these expander graphs are tight. A proof is provided of a strong law of large numbers for a one-dimensional random walk in a dynamic random environment given by a supercritical contact process in equilibrium. The proof is based on a coupling argument that traces the space-time cones containing the infection clusters generated by single infections and uses that the random walk eventually gets trapped inside the union of these cones. For the case where the local drifts of the random walk are smaller than the speed at which infection clusters grow, the random walk eventually gets trapped inside a single cone. This in turn leads to the existence of regeneration times at which the random walk forgets its past. The latter are used to prove a functional central limit theorem and a large deviation principle. The qualitative dependence of the speed, the volatility and the rate function on the infection parameter is investigated, and some open problems are mentioned. We consider the contact process on a random graph with fixed degree distribution given by a power law. We follow the work of Chatterjee and Durrett (2009), who showed that for arbitrarily small infection parameter @math , the survival time of the process is larger than a stretched exponential function of the number of vertices, @math . We obtain sharp bounds for the typical density of infected sites in the graph, as @math is kept fixed and @math tends to infinity. We exhibit three different regimes for this density, depending on the tail of the degree law.