posted on 2013-02-21, 00:00authored byRajmonda 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.
History
Advisor
Berger-Wolf, Tanya
Department
Mathematics, Statistics and Computer Science
Degree Grantor
University of Illinois at Chicago
Degree Level
Doctoral
Committee Member
Yang, Jie
Grossman, Robert
Pelsmajer, Michael
Kaul, Hemanshu
Turan, Gyorgy