Globs in the primordial soup

MobiHoc 2010 Conference Best Paper AwardInternational audienceIn many practical scenarios, nodes gathering at points of interest yield sizable connected components (clusters), which sometimes comprise the majority of nodes. While recent analysis of mobile networks focused on the process governing node encounters ("contacts"), this model is not particularly suitable for gathering behavior. In this paper, we propose a model of stochastic coalescence (merge) and fragmentation (split) of clusters. We implement this process as a Markov chain and derive analytically the exact stationary distribution of cluster size. Further, we prove that, as the number of nodes grows, the clustering behavior converges to a mean field, which is obtained as a closed-form expression. This expression translates the empirical merge and split rate of a scenario, a microscopic property, to an important macroscopic property--the cluster size distribution--with surprising accuracy. We validate all results with synthetic as well as real-world mobility traces from conference visitors and taxicabs with several thousand nodes