Raytheon BBN Technologies

We live in a world increasingly dominated by networks – com-munications, social, information, biological etc. A central at-tribute of many of these networks is that they are dynamic, that is, they exhibit structural changes over time. While the practice of dynamic networks has proliferated, we lag behind in the fundamental, mathematical understanding of network dynamism. Existing research on time-varying graphs ranges from preliminary algorithmic studies (e.g., Ferreira’s work on evolving graphs) to analysis of specific properties such as flooding time in dynamic random graphs. A popular model for studying dynamic graphs is a sequence of graphs arranged by increasing snapshots of time. In this paper, we study the fundamental property of reachability in a time-varying graph over time and characterize the latency with respect to two met-rics, namely store-or-advance latency and cut-through latency. Instead of expected value analysis, we concentrate on char-acterizing the exact probability distribution of routing latency along a randomly intermittent path in two popular dynamic random graph models. Using this analysis, we characterize the loss of accuracy (in a probabilistic setting) between mul-tiple temporal graph models, ranging from one that preserves all the temporal ordering information for the purpose of com-puting temporal graph properties to one that collapses various snapshots into one graph (an operation called smashing), with multiple intermediate variants. We also show how some other traditional graph theoretic properties can be extended to the temporal domain. Finally, we propose algorithms for control-ling the progress of a packet in single-copy adaptive routing schemes in various dynamic random graphs. ∗Research was sponsored by the Army Research Laboratory and was ac-complished under Cooperative Agreement Number W911NF-09-2-0053. The views and conclusions contained in this document are those of the authors an