Measuring and Mining Dynamic Networks

A dynamic network is a mathematical graph representation for time-varying natural systems that consist of many independently interacting entities. In particular, dynamic networks are most useful when the system exhibits extremely complex behavior and is continually changing over time, and when only a record of the interactions between entities are observed. In these cases, the goal is to learn about the underlying natural system by studying the dynamic behavior of the entities in it. By dealing with a graph representation, we can abstract away the increasingly diverse sources of dynamic network data, and extract information from the dynamics of interactions alone.;We start by analyzing how the change in structure of networks are quantified over time. This is a fundamental technique used in a variety of fields: for example, can we determine if the average shortest-path length between Internet routers is gradually decreasing from samples of its structure over time? By analyzing a bibliographic database like DBLP, can we conclude that publishing scientists are forming increasingly more connected collaboration networks? We survey existing techniques, and make a case for more sophisticated measurement and mining methods.;The first of these new methods is an efficient Fourier-like decomposition for dynamic network data that allows us to analyze the periodicities and periodic patterns present in a dynamic network dataset. Using this tool on several datasets, we find that the method is both efficient and able to recover a spectrum of plausible periodicities in real dynamic networks. Given that there is interesting information that can be extracted from network dynamics, the second new technique proposed is a data mining technique for finding interactions in a dynamic network where the occurrence of one predicts the other. This allows us to tease apart the parts of a network that are regular and predictable. All the methods proposed here serve the broader goal of characterizing and quantifying network dynamics, as advanced forms of measurement that make a minimal set of assumptions about the underlying system.