Temporal Scale of Dynamic Networks
thesisposted on 21.02.2013, 00:00 by Rajmonda S. Sulo Caceres
Networks have become an indispensable data abstraction that captures the nature of a diverse list of complex systems, such as on-line social interactions, email and cell phone communications, or protein interactions in a cell. All these systems are inherently dynamic and change over time. The abstraction of choice for incorporating time has been the "dynamic network'', a time series of graphs, each representing an aggregation of a small discrete time interval of the stream of interactions. While in many cases the system under observation naturally suggests the size of such a time interval, it is more often the case that the aggregation is arbitrary and is done for the convenience of the data representation and analysis. However, it is clear that the choice of the time interval at which the network is discretized and aggregated has great implications on the structures observed, analysis performed, and inference made about the nature of the network and the processes on it. This thesis is the first to establish a framework for the problem of Temporal Scale Inference (TSI) for dynamic networks. We formally define the TSI problem and explicitly present some of its associated challenges. We present an analytical framework for studying the characteristics of special cases of interaction streams as probabilistic processes. We give characterizations of a null model and define the notion of the "right" temporal scale of a list of structured interaction streams including the general class of oversampled, noisy stationary streams. We present an axiomatic framework that formalizes desired properties of the "right" temporal scale. This framework serves as a common ground for consistently comparing the performance of different heuristics for the TSI problem. We present two heuristics for identification of the inherent temporal scale of interaction streams. Overall, this thesis focuses on the analysis of the scale of dynamic networks with the objective to make the "art of looking at the right scale" more scientific.