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.

This thesis describes a system that, given approximately-centered images of spiral galaxies, produces quantitative descriptions of spiral galaxy structure without the need for per-image human input. This structure information consists of a list of spiral arm segments, each associated with a fitted logarithmic spiral arc and a pixel region. This list-of-arcs representation allows description of arbitrary spiral galaxy structure: the arms do not need to be symmetric, may have forks or bends, and, more generally, may be arranged in any manner with a consistent spiral-pattern center (non-merging galaxies have a sufficiently well-defined center). Such flexibility is important in order to accommodate the myriad structure variations observed in spiral galaxies. From the arcs produced from our method it is possible to calculate measures of spiral galaxy structure such as winding direction, winding tightness, arm counts, asymmetry, or other values of interest (including user-defined measures). In addition to providing information about the spiral arm "skeleton" of each galaxy, our method can enable analyses of brightness within individual spiral arms, since we provide the pixel regions associated with each spiral arm segment. For winding direction, arm tightness, and arm count, comparable information is available (to various extents) from previous efforts; to the extent that such information is available, we find strong correspondence with our output. We also characterize the changes to (and invariances in) our output as a function of modifications to important algorithm parameters. By enabling generation of extensive data about spiral galaxy structure from large-scale sky surveys, our method will enable new discoveries and tests regarding the nature of galaxies and the universe, and will facilitate subsequent work to automatically fit detailed brightness models of spiral galaxies.

Over the past decade, the study of graphlets has emerged as a useful tool in the study of networks. Graphlets are small, induced, connected subgraphs on a larger graph. They aid in quantifying the structure of networks, identifying functionality of sub-regions within a network, and understanding how relationships and interactions represented by the network may evolve over time. In this study, we approach a variety of problems from the vantage point of graphlets. First, we model the structure of BioGRID protein-protein interaction (PPI) networks using different network models and assess their fitness primarily via their graphlet topology. We also briefly explore the relationships between various network comparison measures and find there is little agreement between them. Despite this disagreement, we find that the models most suited to modeling PPI networks have changed as the data evolve and that it is the STICKY and scale-free based models which best fit current PPI networks. Secondly, as the PPIs (and other networks) are constantly updated, they become larger and denser. As network data is growing in volume (some networks have on the order of hundreds of thousands of nodes and millions of edges), exhaustive enumeration of graphlets becomes infeasible and hence, in order to perform graphlet analysis on networks, we must sample graphlets from networks. We explore four different graphlet sampling techniques. We highlight the advantages and disadvantages of different sampling approaches and show that a Markov Chain Monte Carlo approach to graphlet sampling is best for approximating the proportion of each graphlet within a network. In addition, we find that though they have different biases, all four techniques are able sample a sufficiently diverse set of graphlets that graphlet-based network comparison measures are still able to distinguish between different network types. From sampling, we are also able to distinguish graphs of much higher density, which would ordinarily take weeks or months of CPU time to fully enumerate. Thirdly, we demonstrate a need for the development of synthetic network generators by showing that that many state-of-the-art synthetic network generators do not consistently reproduce networks matching traditional properties of real-world networks and graphlet distributions of the real-world networks. Finally, we analyze the brain fMRI connectivity in children with OCD and a control (CON) group. We find that the network connectivity is completely different in both networks and we highlight some of their differences, including hub nodes, different correlations between connectivity paths and physical distances in the brain, the occurrence of cliques and circuits and graphlet distributions. We also model the OCD and CON connectivity networks using theoretical models and find that the CON network is fit best by a Geometric with Gene Duplication and Mutation network while the OCD network has no best fit.

Spiral galaxies constitute a significant fraction of galaxies observed in the local universe yet their characteristic structure is not well understood. Current methods of analysis rely on manual intervention and expertise, both of which present a significant barrier to the investigation of spiral structure at the scale of modern observational surveys. We present an automated modeling pipeline that uses the simple, one-dimensional arc analysis from SpArcFiRe to generate an initial guess for GALFIT to produce two-dimensional photometric decompositions of spiral galaxies. Our automated method is encapsulated in a Python module entitled “GalfitModule” which contains a generalized framework to handle GALFIT components and parameters. GalfitModule employs this framework to translate SpArcFiRe's output to input for GALFIT, runs GALFIT using multiple novel techniques with distributed processing, and performs an assessment of the success of our decompositions. Using this pipeline, we produce two and three component decompositions of several samples of spiral galaxies from the SDSS DR7 data release, as selected by the Galaxy Zoo team. We then assess the performance of our method, validating our results by eye, and analyze the resultant parameterization of these in bulk. Our largest sample is 28912 galaxies, of which we estimate 54.3% (about 15,700) of the models accurately map the visible structure of the original observations. We identify trends in the Sérsic indices, magnitudes, and arm-to-total flux ratios, and compare these trends to previous decomposition studies, finding general agreement in the arm-to-total flux ratio. Of the other parameters, there is evidence that our models overfit the observations, causing disagreement. Finally, we present an extension to our method which evaluates the model's pitch angle as it varies along the length of the arm.

Summary

Availability and implementation

Contact

Supplementary information

Sea level contributions from the Greenland Ice Sheet are influenced by the rapid changes in glacial terminus positions. Also known as {\it calving front} positions this information is captured in satellite imagery, but determining the position of the actual front usually involves laborious human labor, causing a major bottleneck in processing the thousands of existing images. From Landsat satellite imagery, we face the task of generating 22,678 calving fronts across 66 Greenlandic glaciers. Automated methods face challenges that include the handling of clouds, illumination differences, sea ice mélange, and Landsat-7 Scanline Corrector Errors. To address these needs, we develop the Calving Front Machine (CALFIN), an automated method for extracting calving fronts from satellite images of marine-terminating glaciers, using neural networks. CALFIN builds upon existing neural network architectures, and specializes in the segmentation of line-like features, while simultaneously handling large amounts of noise in the source data. Novel post-processing algorithms are used to perform the feature extraction and vectorization. The results are often indistinguishable from manually-curated fronts, deviating by on average 2.25 ± 0.03 pixels (86.76 ± 1.43 meters) from the measured front. This improves on the state of the art in terms of the spatio-temporal coverage and accuracy of its outputs, and is validated through a comprehensive intercomparison with existing studies. The current implementation offers a new opportunity to explore sub-seasonal and regional trends on the extent of Greenland's margins, and supplies new constraints for simulations of the evolution of the mass balance of the Greenland Ice Sheet and its contributions to future sea level rise.

Large amounts of biological network data exist for many species. Analogous to sequence comparison, network comparison aims to provide biological insight. Graphlet-based methods are proving to be useful in this respect. Recently some doubt has arisen concerning the applicability of graphlet-based measures to low edge density networks-in particular that the methods are 'unstable'-and further that no existing network model matches the structure found in real biological networks.

We demonstrate that it is the model networks themselves that are 'unstable' at low edge density and that graphlet-based measures correctly reflect this instability. Furthermore, while model network topology is unstable at low edge density, biological network topology is stable. In particular, one must distinguish between average density and local density. While model networks of low average edge densities also have low local edge density, that is not the case with protein-protein interaction (PPI) networks: real PPI networks have low average edge density, but high local edge densities, and hence, they (and thus graphlet-based measures) are stable on these networks. Finally, we use a recently devised non-parametric statistical test to demonstrate that PPI networks of many species are well-fit by several models not previously tested. In addition, we model several viral PPI networks for the first time and demonstrate an exceptionally good fit between the data and theoretical models.