Real-time analytics on large dynamic graphs

In today's fast-paced and interconnected digital world, the data generated by an increasing number of applications is being modeled as dynamic graphs. The graph structure encodes relationships among data items, while the structural changes to the graphs as well as the continuous stream of information produced by the entities in these graphs make them dynamic in nature. Examples include social networks where users post status updates, images, videos, etc.; phone call networks where nodes may send text messages or place phone calls; road traffic networks where the traffic behavior of the road segments changes constantly, and so on. There is a tremendous value in storing, managing, and analyzing such dynamic graphs and deriving meaningful insights in real-time. However, a majority of the work in graph analytics assumes a static setting, and there is a lack of systematic study of the various dynamic scenarios, the complexity they impose on the analysis tasks, and the challenges in building efficient systems that can support such tasks at a large scale. In this dissertation, I design a unified streaming graph data management framework, and develop prototype systems to support increasingly complex tasks on dynamic graphs. In the first part, I focus on the management and querying of distributed graph data. I develop a hybrid replication policy that monitors the read-write frequencies of the nodes to decide dynamically what data to replicate, and whether to do eager or lazy replication in order to minimize network communication and support low-latency querying. In the second part, I study parallel execution of continuous neighborhood-driven aggregates, where each node aggregates the information generated in its neighborhoods. I build my system around the notion of an aggregation overlay graph, a pre-compiled data structure that enables sharing of partial aggregates across different queries, and also allows partial pre-computation of the aggregates to minimize the query latencies and increase throughput. Finally, I extend the framework to support continuous detection and analysis of activity-based subgraphs, where subgraphs could be specified using both graph structure as well as activity conditions on the nodes. The query specification tasks in my system are expressed using a set of active structural primitives, which allows the query evaluator to use a set of novel optimization techniques, thereby achieving high throughput. Overall, in this dissertation, I define and investigate a set of novel tasks on dynamic graphs, design scalable optimization techniques, build prototype systems, and show the effectiveness of the proposed techniques through extensive evaluation using large-scale real and synthetic datasets.

Dynamic Coculture of a Prevascularized Engineered Bone Construct

The generation of functional, vascularized tissues is a key challenge for the field of tissue engineering. Before clinical implantations of tissue engineered bone constructs can succeed, in vitro fabrication needs to address limitations in large-scale tissue development, including controlled osteogenesis and an inadequate vasculature network to prevent necrosis of large constructs. The tubular perfusion system (TPS) bioreactor is an effective culturing method to augment osteogenic differentiation and maintain viability of human mesenchymal stem cell (hMSC)-seeded scaffolds while they are developed in vitro. To further enhance this process, we developed a novel osteogenic growth factors delivery system for dynamically cultured hMSCs using microparticles encapsulated in three-dimensional alginate scaffolds. In light of this increased differentiation, we characterized the endogenous cytokine distribution throughout the TPS bioreactor. An advantageous effect in the ‘outlet’ portion of the uniaxial growth chamber was discovered due to the system’s downstream circulation and the unique modular aspect of the scaffolds. This unique trait allowed us to carefully tune the differentiation behavior of specific cell populations. We applied the knowledge gained from the growth profile of the TPS bioreactor to culture a high-volume bone composite in a 3D-printed femur mold. This resulted in a tissue engineered bone construct with a volume of 200cm3, a 20-fold increase over previously reported sizes. We demonstrated high viability of the cultured cells throughout the culture period as well as early signs of osteogenic differentiation. Taking one step closer toward a viable implant and minimize tissue necrosis after implantation, we designed a composite construct by coculturing endothelial cells (ECs) and differentiating hMSCs, encouraging prevascularization and anastomosis of the graft with the host vasculature. We discovered the necessity of cell to cell proximity between the two cell types as well as preference for the natural cell binding capabilities of hydrogels like collagen. Notably, the results suggested increased osteogenic and angiogenic potential of the encapsulated cells when dynamically cultured in the TPS bioreactor, suggesting a synergistic effect between coculture and applied shear stress. This work highlights the feasibility of fabricating a high-volume, prevascularized tissue engineered bone construct for the regeneration of a critical size defect.

Guided Migration and Collective Behavior: Cell Dynamics during Cancer Progression

This dissertation focuses on gaining understanding of cell migration and collective behavior through a combination of experiment, analysis, and modeling techniques. Cell migration is a ubiquitous process that plays an important role during embryonic development and wound healing as well as in diseases like cancer, which is a particular focus of this work. As cancer cells become increasingly malignant, they acquire the ability to migrate away from the primary tumor and spread throughout the body to form metastatic tumors. During this process, changes in gene expression and the surrounding tumor environment can lead to changes in cell migration characteristics. In this thesis, I analyze how cells are guided by the texture of their environment and how cells cooperate with their neighbors to move collectively. The emergent properties of collectively moving groups are a particular focus of this work as collective cell dynamics are known to change in diseases such as cancer. The internal machinery for cell migration involves polymerization of the actin cytoskeleton to create protrusions that---in coordination with retraction of the rear of the cell---lead to cell motion. This actin machinery has been previously shown to respond to the topography of the surrounding surface, leading to guided migration of amoeboid cells. Here we show that epithelial cells on nanoscale ridge structures also show changes in the morphology of their cytoskeletons; actin is found to align with the ridge structures. The migration of the cells is also guided preferentially along the ridge length. These ridge structures are on length scales similar to those found in tumor microenvironments and as such provide a system for studying the response of the cells' internal migration machinery to physiologically relevant topographical cues. In addition to sensing surface topography, individual cells can also be influenced by the pushing and pulling of neighboring cells. The emergent properties of collectively migrating cells show interesting dynamics and are relevant for cancer progression, but have been less studied than the motion of individual cells. We use Particle Image Velocimetry (PIV) to extract the motion of a collectively migrating cell sheet from time lapse images. The resulting flow fields allow us to analyze collective behavior over multiple length and time scales. To analyze the connection between individual cell properties and collective migration behavior, we compare experimental flow fields with the migration of simulated cell groups. Our collective migration metrics allow for a quantitative comparison between experimental and simulated results. This comparison shows that tissue-scale decreases in collective behavior can result from changes in individual cell activity without the need to postulate the existence of subpopulations of leader cells or global gradients. In addition to tissue-scale trends in collective behavior, the migration of cell groups includes localized dynamic features such as cell rearrangements. An individual cell may smoothly follow the motion of its neighbors (affine motion) or move in a more individualistic manner (non-affine motion). By decomposing individual motion into both affine and non-affine components, we measure cell rearrangements within a collective sheet. Finally, finite-time Lyapunov exponent (FTLE) values capture the stretching of the flow field and reflect its chaotic character. Applying collective migration analysis techniques to experimental data on both malignant and non-malignant human breast epithelial cells reveals differences in collective behavior that are not found from analyzing migration speeds alone. Non-malignant cells show increased cooperative motion on long time scales whereas malignant cells remain uncooperative as time progresses. Combining multiple analysis techniques also shows that these two cell types differ in their response to a perturbation of cell-cell adhesion through the molecule E-cadherin. Non-malignant MCF10A cells use E-cadherin for short time coordination of collective motion, yet even with decreased E-cadherin expression, the cells remain coordinated over long time scales. In contrast, the migration behavior of malignant and invasive MCF10CA1a cells, which already shows decreased collective dynamics on both time scales, is insensitive to the change in E-cadherin expression.

Guided Migration and Collective Behavior: Cell Dynamics during Cancer Progression

This dissertation focuses on gaining understanding of cell migration and collective behavior through a combination of experiment, analysis, and modeling techniques. Cell migration is a ubiquitous process that plays an important role during embryonic development and wound healing as well as in diseases like cancer, which is a particular focus of this work. As cancer cells become increasingly malignant, they acquire the ability to migrate away from the primary tumor and spread throughout the body to form metastatic tumors. During this process, changes in gene expression and the surrounding tumor environment can lead to changes in cell migration characteristics. In this thesis, I analyze how cells are guided by the texture of their environment and how cells cooperate with their neighbors to move collectively. The emergent properties of collectively moving groups are a particular focus of this work as collective cell dynamics are known to change in diseases such as cancer. The internal machinery for cell migration involves polymerization of the actin cytoskeleton to create protrusions that---in coordination with retraction of the rear of the cell---lead to cell motion. This actin machinery has been previously shown to respond to the topography of the surrounding surface, leading to guided migration of amoeboid cells. Here we show that epithelial cells on nanoscale ridge structures also show changes in the morphology of their cytoskeletons; actin is found to align with the ridge structures. The migration of the cells is also guided preferentially along the ridge length. These ridge structures are on length scales similar to those found in tumor microenvironments and as such provide a system for studying the response of the cells' internal migration machinery to physiologically relevant topographical cues. In addition to sensing surface topography, individual cells can also be influenced by the pushing and pulling of neighboring cells. The emergent properties of collectively migrating cells show interesting dynamics and are relevant for cancer progression, but have been less studied than the motion of individual cells. We use Particle Image Velocimetry (PIV) to extract the motion of a collectively migrating cell sheet from time lapse images. The resulting flow fields allow us to analyze collective behavior over multiple length and time scales. To analyze the connection between individual cell properties and collective migration behavior, we compare experimental flow fields with the migration of simulated cell groups. Our collective migration metrics allow for a quantitative comparison between experimental and simulated results. This comparison shows that tissue-scale decreases in collective behavior can result from changes in individual cell activity without the need to postulate the existence of subpopulations of leader cells or global gradients. In addition to tissue-scale trends in collective behavior, the migration of cell groups includes localized dynamic features such as cell rearrangements. An individual cell may smoothly follow the motion of its neighbors (affine motion) or move in a more individualistic manner (non-affine motion). By decomposing individual motion into both affine and non-affine components, we measure cell rearrangements within a collective sheet. Finally, finite-time Lyapunov exponent (FTLE) values capture the stretching of the flow field and reflect its chaotic character. Applying collective migration analysis techniques to experimental data on both malignant and non-malignant human breast epithelial cells reveals differences in collective behavior that are not found from analyzing migration speeds alone. Non-malignant cells show increased cooperative motion on long time scales whereas malignant cells remain uncooperative as time progresses. Combining multiple analysis techniques also shows that these two cell types differ in their response to a perturbation of cell-cell adhesion through the molecule E-cadherin. Non-malignant MCF10A cells use E-cadherin for short time coordination of collective motion, yet even with decreased E-cadherin expression, the cells remain coordinated over long time scales. In contrast, the migration behavior of malignant and invasive MCF10CA1a cells, which already shows decreased collective dynamics on both time scales, is insensitive to the change in E-cadherin expression.