Abstract: In this paper we study the problem of basic communication
in ad-hoc mobile networks where the deployment area changes in a
highly dynamic way and is unknown. We call such networks
highly changing ad-hoc mobile networks.
For such networks we investigate an efficient communication protocol which extends
the idea (introduced in [WAE01,POMC01]) of exploiting the co-ordinated
motion of a small part of an ad-hoc mobile
network (the ``runners support") to achieve
very fast communication between any two mobile users of the network.
The basic idea of the new protocol presented here is, instead
of using a fixed sized support for the whole duration of the protocol,
to employ a support of some initial (small) size which
adapts (given some time which can be made fast enough) to the
actual levels of traffic and the
(unknown and possibly rapidly changing) network area by
changing its size in order to converge to an optimal size,
thus satisfying certain Quality of Service criteria.
We provide here some proofs of correctness and fault tolerance
of this adaptive approach and we also provide analytical results
using MarkovChains and random walk techniques to show that such
an adaptive approach is, for this class of ad-hoc mobile networks, significantly more efficient than a simple non-adaptive
implementation of the basic ``runners support" idea.
Abstract: We consider the Moran process, as generalized by Lieberman, Hauert and Nowak (Nature, 433:312--316, 2005). A population resides on the vertices of a finite, connected, undirected graph and, at each time step, an individual is chosen at random with probability proportional to its assigned 'fitness' value. It reproduces, placing a copy of itself on a neighbouring vertex chosen uniformly at random, replacing the individual that was there. The initial population consists of a single mutant of fitness r>0 placed uniformly at random, with every other vertex occupied by an individual of fitness 1. The main quantities of interest are the probabilities that the descendants of the initial mutant come to occupy the whole graph (fixation) and that they die out (extinction); almost surely, these are the only possibilities. In general, exact computation of these quantities by standard Markovchain techniques requires solving a system of linear equations of size exponential in the order of the graph so is not feasible. We show that, with high probability, the number of steps needed to reach fixation or extinction is bounded by a polynomial in the number of vertices in the graph. This bound allows us to construct fully polynomial randomized approximation schemes (FPRAS) for the probability of fixation (when r≥1) and of extinction (for all r>0).
Abstract: In this paper we examine spectral properties of random intersection graphs when the number of vertices is equal to the number of labels. We call this class symmetric random intersection graphs. We examine symmetric random intersection graphs when the probability that a vertex selects a label is close to the connectivity threshold $\tau_c$. In particular, we examine the size of the second eigenvalue of the transition matrix corresponding to the MarkovChain that describes a random walk on an instance of the symmetric random intersection graph $G_{n, n, p}$. We show that with high probability the second eigenvalue is upper bounded by some constant $\zeta < 1$.
Abstract: In this paper we examine spectral properties of random intersection graphs when the number
of vertices is equal to the number of labels. We call this class symmetric random intersection graphs.
We examine symmetric random intersection graphs when the probability that a vertex selects a label
is close to the connectivity threshold ¿c. In particular, we examine the size of the second eigenvalue of
the transition matrix corresponding to the MarkovChain that describes a random walk on an instance
of the symmetric random intersection graph Gn,n,p. We show that with high probability the second
eigenvalue is upper bounded by some constant ³ < 1.
