Phase Transition in Opportunistic Mobile Networks

Opportunistic mobile networks take advantage of local opportunities of wireless communication between devices (cellphones, etc.) to construct a path over time between a source and a destination. This paper uses a model of random temporal network to study the existence of those paths that use a small number of time slots and a small number of steps. It establishes that a phase transition occurs as time and hops are jointly increase according to the logarithm of the network size. For a given intensity of contact, as time grows the network abruptly change from a regime where almost surely no path exists to a regime where paths exist with a positive probability. Our proof illustrates a strong correlation close to the critical point between nearby paths (those who share a prefix and suffix term), which explain the relatively high value of the variance. We identify combinatorial properties specific to temporal paths, which are critical to characterize the phase transition and impact the estimation of the probability of success. We believe that it is the first rigorous proof that a phenomenon recalling the small world effect may be found in dynamic random graphs.