UC Irvine

Network analysis and its exploit of graph-theoretical properties such as topology are important mathematical and computational problems, with implications in a variety of fields such as social sciences, economics, and the biological sciences. While the study of complex networks has evolved quite rapidly over the last few years, largely as a result of massive data sets and computational techniques, its study remains largely domain-specific, and focused on static, global network properties. Thus, the ability to achieve node-level granularity in the analysis of rapidly changing network data is currently non-existent.

In order to apply network analysis to rapidly changing complex network systems, such as those representing real-time, physical phenomena, their dynamics must be analyzed in a computationally efficient manner, and predictive mechanisms must exist for their classification and forecasting. This work provides important steps towards the efficient and effective analysis of dynamics in real-world complex networks.

First, we introduce a computationally efficient algorithm for the comparison of networks. The development of network alignment as an analysis technique has enabled the efficient mining of complex information from vast sets of data, such as those generated in the field of proteomics. However, network alignment methods have mostly been applied to the analysis of networks representing different entities, such as differing species or corporate structures, under static conditions. Our research explores the application of network alignment to the identification of dynamics in large, potentially fast-changing networks. As a result, we develop a computationally efficient algorithm with potential for distributed and parallel improvements. We compare our algorithm to well established network alignment alternatives, under various network models and complexity properties.

Second, this work presents methodology for the identification and labeling of node/edge-level events in a complex spatio-temporal network system. A process and associated measurements are introduced to effectively identify events, followed by the implementation of an inference method for the labeling of such events.

Finally, our methodology for identification and labeling of events is applied to a biological problem of high consequence for human health: That the identification of fission and fusion events in mitochondrial networks. Lastly, Successes and challenges of this application are discussed.

As stated, the work here presented comprises a series of important steps for the utilization of network alignment in the exploration of dynamics in complex networks, solely using the structural and topological features of the network. Further, the methodology here presented is not domain-specific, thus opening the possibilities for their utilization in the analysis of dynamics in real-world dynamic complex networks.