Search

Understanding the structural dynamics of many-particle glassy systems remains a key challenge in statistical physics. Over the last decade, glassy dynamics has also been reported in biological tissues, but is far from being understood. It was recently shown that vertex models of dense biological tissue exhibit very atypical, sub-Arrhenius dynamics, and here we ask whether such atypical structural dynamics of vertex models are related to unusual elastic properties. It is known that at zero temperature these models have an elasticity controlled by their under-constrained or isostatic nature, but little is known about how their elasticity varies with temperature. To address this question we investigate the 2D Voronoi model and measure the temperature dependence of the intermediate-time plateau shear modulus and the bulk modulus. We find that unlike in conventional glassformers, these moduli increase monotonically with temperature until the system fluidizes. We further show that the structural relaxation time can be quantitatively linked to the plateau shear modulus $G_p$, i.e.\ $G_p$ modulates the typical energy barrier scale for cell rearrangements. This suggests that the anomalous, structural dynamics of the 2D Voronoi model originates in its unusual elastic properties. Based on our results, we hypothesize that under-constrained systems might more generally give rise to a new class of "ultra-strong" glassformers., Comment: 5 pages, 5 figures

Flocking phase transitions found in models of polar active matter are paradigmatic examples of active phase transitions in soft matter. An interesting specialization of flocking models concerns a ``topological'' vs ``metric'' choice by which agents are considered to be interacting neighbors. While recent theoretical work suggests that the order-disorder transition in these polar aligning models is universally first order, numerical studies have suggested that topological models may instead have a continuous transition. Some recent simulations have found that some variations of topologically interacting flocking agents have a discontinuous transition, but unambiguous observations of phase coexistence using common Voronoi-based alignment remains elusive. In this work, we use a custom GPU-accelerated simulation package to perform million-particle-scale simulations of these Voronoi-Vicsek flocking models. By accessing such large systems on appropriately long time scales, we are able to show that a regime of stable phase coexistence between the ordered and disordered phases, confirming the discontinuous nature of this transition in the thermodynamic limit., Comment: 7 pages, 7 figures, many simulations

Observations of glassy dynamics in experiments on confluent cellular tissue have inspired a wealth of computational and theoretical research to model their emergent collective behavior. Initial studies of the physical properties of several geometric cell models, including vertex-type models, have highlighted anomalous sub-Arrhenius, or "ultra-strong," scaling of the dynamics with temperature. Here we show that the dynamics and material properties of the 2d Voronoi model deviate even further from the standard glassforming paradigm. By varying the characteristic shape index $p_0$, we demonstrate that the system properties can be tuned between displaying expected glassforming behavior, including the breakdown of the Stokes-Einstein-Sutherland relation and the formation of dynamical heterogeneities, and an unusual regime in which the viscosity does not diverge as the characteristic relaxation time increase and dynamical heterogeneities are strongly suppressed. Our results provide further insight into the fundamental properties of this class of anomalous glassy materials, and provide a step towards designing materials with predetermined glassy dynamics., Comment: 10 pages, 4 figures

The properties of tissue interfaces -- between separate populations of cells, or between a group of cells and its environment -- has attracted intense theoretical, computational, and experimental study. Recent work on shape-based models inspired by dense epithelia have suggested a possible ``topological sharpening'' effect, by which four-fold vertices spatially coordinated along a cellular interface lead to a cusp-like restoring force acting on cells at the interface, which in turn greatly suppresses interfacial fluctuations. We revisit these interfacial fluctuations, focusing on the distinction between short length scale reduction of interfacial fluctuations and long length scale renormalized surface tension. To do this, we implement a spectrally resolved analysis of fluctuations over extremely long simulation times. This leads to more quantitative information on the topological sharpening effect, in which the degree of sharpening depends on the length scale over which it is measured. We compare our findings with a Brownian bridge model of the interface, and close by analyzing existing experimental data in support of the role of short-length-scale topological sharpening effects in real biological systems., Comment: 9 pages, 7 figures

A large number of powerful, high-quality, and open-source simulation packages exist to efficiently perform molecular dynamics simulations, and their prevalence has greatly accelerated discoveries across a wide range of scientific domains. These packages typically simulate particles in free (Euclidean) space, with options to specify a variety of boundary conditions. While more exotic, many physical systems are constrained to and interact across curved surfaces, such as organisms moving across the landscape, colloids pinned at curved fluid-fluid interfaces, and layers of epithelial cells forming highly curved tissues. The calculation of distances and the updating of equations of motion in idealized geometries (namely, on surfaces of constant curvature) can be done analytically, but it is much more challenging to efficiently perform molecular-dynamics-like simulations on arbitrarily curved surfaces. This article discusses a simulation framework which combines tools from particle-based simulations with recent work in discrete differential geometry to model particles that interact via geodesic distances and move on an arbitrarily curved surface. We present computational cost estimates for a variety of surface complexities with and without various algorithmic specializations (e.g., restrictions to short-range interaction potentials, or multi-threaded parallelization). Our flexible and extensible framework is set up to easily handle both equilibrium and non-equilibrium dynamics, and will enable researchers to access time- and particle-number-scales previously inaccessible., Comment: 12 pages, 7 figures, the whole megillah

We present a novel approach for finding multiple noisily embedded template graphs in a very large background graph. Our method builds upon the graph-matching-matched-filter technique proposed in Sussman et al., with the discovery of multiple diverse matchings being achieved by iteratively penalizing a suitable node-pair similarity matrix in the matched filter algorithm. In addition, we propose algorithmic speed-ups that greatly enhance the scalability of our matched-filter approach. We present theoretical justification of our methodology in the setting of correlated Erdos-Renyi graphs, showing its ability to sequentially discover multiple templates under mild model conditions. We additionally demonstrate our method's utility via extensive experiments both using simulated models and real-world dataset, include human brain connectomes and a large transactional knowledge base., Comment: 27 pages, 12 figures, 3 tables

Flocking behavior is observed in biological systems from the cellular to super-organismal length scales, and the mechanisms and purposes of this behavior are objects of intense interest. In this paper, we study the collective dynamics of bovine sperm cells in a viscoelastic fluid. These cells appear not to spontaneously flock, but transition into a long-lived flocking phase after being exposed to a transient ordering pulse of fluid flow. Surprisingly, this induced flocking phase has many qualitative similarities with the spontaneous polar flocking phases predicted by Toner-Tu theory, such as anisotropic giant number fluctuations and non-trivial transverse density correlations, despite the induced nature of the phase and the clearly important role of momentum conservation between the swimmers and the surrounding fluid in these experiments. We also find self-organized global vortex state of the sperm cells, and map out an experimental phase diagram of states of collective motion as a function of cell density and motility statistics. We compare our experiments with a parameter-matched computational model of persistently turning active particles, and find that the experimental order-disorder phase boundary as a function of cell density and persistence time can be approximately predicted from measures of single-cell properties. Our results may have implications for the evaluation of sample fertility by studying the collective phase behavior of dense groups of swimming sperm., Comment: Version 2: 11 pages, 9 figures, even more data than before

Data-driven approaches to inferring the local structures responsible for plasticity in amorphous materials have made substantial contributions to our understanding of the failure, flow, and rearrangement dynamics of supercooled fluids. Some of these methods, such as the ``softness'' approach based on linear support vector machines, have identified combinations of local structural features of a supercooled particle's environment that predict energy barriers associated with particle rearrangements. This approach also predicts the onset temperature, often characterized as the temperature below which the system's dynamics becomes non-Arrhenius and above which local structures are no longer predictive of dynamical activity. We implement a transfer-learning approach in which we first show that classifiers can be trained to predict dynamical activity even far above the onset temperature. We then show that applying these classifiers to data from the supercooled phase recovers essentially the same physical information about the relationship between local structures and energy barriers that softness does., Comment: 9 pages, 9 figures

Droplet coalescence is essential in a host of biological and industrial processes, involving complex systems as diverse as cellular aggregates, colloidal suspensions, and polymeric liquids. Classical solutions for the time evolution of coalescing clusters are typically based on tractable limiting physics, such as analytical solutions to the Stokes equation. By combining computational and theoretical analyses, we show that there is an unexplored family of coalescence processes: those governed by highly dissipative coupling to the environment. This leads to new scaling laws characterizing droplet coalescence, as well as new time-invariant parameterizations of the shape evolution of the coalescing system. We demonstrate these effects via particle-based simulations and both continuum and boundary-integral solutions to hydrodynamic equations, which we then understand in the context of a generalized Navier-Stokes-like equation. Our theoretical description of highly frictional coalescence mathematically maps onto Darcy flow in the presence of surface tension effects, opening up exciting avenues of research in applying well-studied fluid dynamical techniques to a broad range of novel systems.

Linear regression with shuffled labels and with a noisy latent design matrix arises in many correspondence recovery problems. We propose a total least-squares approach to the problem of estimating the underlying true permutation and provide an upper bound to the normalized Procrustes quadratic loss of the estimator. We also provide an iterative algorithm to approximate the estimator and demonstrate its performance on simulated data.

Causal inference methods have been applied in various fields where researchers want to estimate treatment effects. In traditional causal inference settings, one assumes that the outcome of a unit does not depend on treatments of other units. However, as causal inference methods are extended to more applications, there is a greater need for estimators of general causal effects. We use an exposure mapping framework [Aronow and Samii, 2017] to map the relationship between the treatment allocation and the potential outcomes. Under the exposure model, we propose linear unbiased estimators (LUEs) for general causal effects under the assumption that treatment effects are additive. Additivity provides statistical advantages, where contrasts in exposures are now equivalent, and so the set of estimators considered grows. We identify a subset of LUEs that forms an affine basis for LUEs, and we characterize optimal LUEs with minimum integrated variance through defining conditions on the support of the estimator. We show, through simulations that our proposed estimators are fairly robust to violations of the additivity assumption, and in general, there is benefit in leveraging information from all exposures.

Many models of flocking involve alignment rules based on the mean orientation of neighboring particles, which we show introduces microscopic non-reciprocal interactions. In the absence of this microscopic non-reciprocity an exceptional phase transition is predicted at low noise strength within the Toner-Tu framework of polar aligning matter; we demonstrate this transition via large-scale numerical simulations. By coarse-graining the microscopic non-reciprocal forces found in more common models of flocking, we identify additional terms in a hydrodynamic description which lead to a highly ordered clustered phase in metric models and restore the homogeneous flocking phase in topological models., Comment: We have found an important bug in the code used to implement the simulations described in this work. We have fixed the bug but cannot yet verify that the numerical claims made are correct

We study particle-scale motion in sheared highly polydisperse amorphous materials, in which the largest particles are as much as ten times the size of the smallest. We find strikingly different behavior from the more commonly studied amorphous systems with low polydispersity. In particular, analysis of the nonaffine motion of particles reveals qualitative differences between large and small particles: the smaller particles have dramatically more nonaffine motion, which is induced by the presence of the large particles. We characterize the crossover in nonaffine motion from the low- to high-polydispersity regime, and demonstrate a quantitative way to distinguish between "large" and "small" particles in systems with broad distributions of particle sizes.

iGraphMatch is an R package for finding corresponding vertices between two graphs, also known as graph matching. The package implements three categories of prevalent graph matching algorithms including relaxation-based, percolation-based, and spectral-based, which are applicable to matching graphs under general settings: weighted directed graphs of different order and graphs of multiple layers. We provide versatile options to incorporate prior information in the form of seeds with or without noise and similarity scores. In addition, iGraphMatch provides functions to summarize the graph matching results in terms of several evaluation measures and visualize the matching performance. Finally, the package enables users to sample correlated random graph pairs from classic random graph models to generate data for simulations. This paper illustrates the practical applications of the package to the analysis of graph matching by detailed examples using real data from communication, neuron, and transportation networks.

Random walk based node embedding algorithms learn vector representations of nodes by optimizing an objective function of node embedding vectors and skip-bigram statistics computed from random walks on the network. They have been applied to many supervised learning problems such as link prediction and node classification and have demonstrated state-of-the-art performance. Yet, their properties remain poorly understood. This paper studies properties of random walk based node embeddings in the unsupervised setting of discovering hidden block structure in the network, i.e., learning node representations whose cluster structure in Euclidean space reflects their adjacency structure within the network. We characterize the ergodic limits of the embedding objective, its generalization, and related convex relaxations to derive corresponding non-randomized versions of the node embedding objectives. We also characterize the optimal node embedding Grammians of the non-randomized objectives for the expected graph of a two-community Stochastic Block Model (SBM). We prove that the solution Grammian has rank $1$ for a suitable nuclear norm relaxation of the non-randomized objective. Comprehensive experimental results on SBM random networks reveal that our non-randomized ergodic objectives yield node embeddings whose distribution is Gaussian-like, centered at the node embeddings of the expected network within each community, and concentrate in the linear degree-scaling regime as the number of nodes increases.

Increasingly, there is a marked interest in estimating causal effects under network interference due to the fact that interference manifests naturally in networked experiments. However, network information generally is available only up to some level of error. We study the propagation of such errors to estimators of average causal effects under network interference. Specifically, assuming a four-level exposure model and Bernoulli random assignment of treatment, we characterize the impact of network noise on the bias and variance of standard estimators in homogeneous and inhomogeneous networks. In addition, we propose method-of-moments estimators for bias reduction where a minimal number of network replicates are available. We show our estimators are asymptotically normal and provide confidence intervals for quantifying the uncertainty in these estimates. We illustrate the practical performance of our estimators through simulation studies in British secondary school contact networks., Comment: 68 pages, 1 figure

It is common in the study of a dizzying array of soft matter systems to perform agent-based simulations of particles interacting via conservative and often short-ranged forces. In this context, well-established algorithms for efficiently computing the set of pairs of interacting particles have established excellent open-source packages to efficiently simulate large systems over long time scales -- a crucial consideration given the separation in time- and length-scales often observed in soft matter. What happens, though, when we think more broadly about what it means to construct a neighbor list? What if interactions are non-reciprocal, or if the "range" of an interaction is determined not by a distance scale but according to some other consideration? As the field of soft and active matter increasingly considers the properties of living matter -- from the cellular to the super-organismal scale -- these questions become increasingly relevant, and encourage us to think about new physical and computational paradigms in the modeling of active matter. In this chapter we examine case studies in the use of non-metric interactions., Comment: These are lecture notes for the Marie Curie Training school "Initial Training on Numerical Methods for Active Matter." (http://active-matter.eu)

Machine learning techniques have been used to quantify the relationship between local structural features and variations in local dynamical activity in disordered glass-forming materials. To date these methods have been applied to an array of standard (Arrhenius and super-Arrhenius) glass formers, where work on "soft spots" indicates a connection between the linear vibrational response of a configuration and the energy barriers to non-linear deformations. Here we study the Voronoi model, which takes its inspiration from dense epithelial monolayers and which displays anomalous, sub-Arrhenius scaling of its dynamical relaxation time with decreasing temperature. Despite these differences, we find that the likelihood of rearrangements can vary by several orders of magnitude within the model tissue and extract a local structural quantity, "softness" that accurately predicts the temperature-dependence of the relaxation time. We use an information-theoretic measure to quantify the extent to which softness determines impending topological rearrangements; we find that softness captures nearly all of the information about rearrangements that is obtainable from structure, and that this information is large in the solid phase of the model and decreases rapidly as state variables are varied into the fluid phase., Comment: 13 pages, 7 figures, questions both answered and unanswered

In development and homeostasis, multi-cellular systems exhibit spatial and temporal heterogeneity in their biochemical and mechanical properties. Nevertheless, it remains unclear how spatiotemporally heterogeneous forces affect the dynamical and mechanical properties of confluent tissue. To address this question, we study the dynamical behavior of the two-dimensional cellular vertex model for epithelial monolayers in the presence of fluctuating cell-cell interfacial tensions, which is a biologically relevant source of mechanical spatiotemporal heterogeneity. In particular, we investigate the effects of the amplitude and persistence time of fluctuating tension on the tissue dynamics. We unexpectedly find that the long-time diffusion constant describing cell rearrangements depends non-monotonically on the persistence time, while it increases monotonically as the amplitude increases. Our analysis indicates that at low and intermediate persistence times tension fluctuations drive motion of vertices and promote cell rearrangements, while at the highest persistence times the tension in the network evolves so slowly that rearrangements become rare., Comment: 16 pages, 14 figures

Joint spectral embeddings facilitate analysis of multiple network data by simultaneously mapping vertices in each network to points in Euclidean space where statistical inference is then performed. In this work, we consider one such joint embedding technique, the omnibus embedding of arXiv:1705.09355 , which has been successfully used for community detection, anomaly detection, and hypothesis testing tasks. To date the theoretical properties of this method have only been established under the strong assumption that the networks are conditionally i.i.d. random dot product graphs. Herein, we take a first step in characterizing the theoretical properties of the omnibus embedding in the presence of heterogeneous network data. Under a latent position model, we show the omnibus embedding implicitly regularizes its latent position estimates which induces a finite-sample bias-variance tradeoff for latent position estimation. We establish an explicit bias expression, derive a uniform concentration bound on the residual, and prove a central limit theorem characterizing the distributional properties of these estimates. These explicit bias and variance expressions enable us to state sufficient conditions for exact recovery in community detection tasks and develop a pivotal test statistic to determine whether two graphs share the same set of latent positions; demonstrating that accurate inference is achievable despite the estimator's inconsistency. These results are demonstrated in several experimental settings where statistical procedures utilizing the omnibus embedding are competitive, and oftentimes preferable, to comparable embedding techniques. These observations accentuate the viability of the omnibus embedding for multiple graph inference beyond the homogeneous network setting., Comment: 45 pages, 7 figures

Many fundamental concepts in network-based epidemic modeling depend on the branching factor, which captures a sense of dispersion in the network connectivity and quantifies the rate of spreading across the network. Moreover, contact network information generally is available only up to some level of error. We study the propagation of such errors to the estimation of the branching factor. Specifically, we characterize the impact of network noise on the bias and variance of the observed branching factor for arbitrary true networks, with examples in sparse, dense, homogeneous and inhomogeneous networks. In addition, we propose a method-of-moments estimator for the true branching factor. We illustrate the practical performance of our estimator through simulation studies and with contact networks observed in British secondary schools and a French hospital., Comment: 44 pages, 4 figures

Rigidity transitions in simple models of confluent cells have been a powerful organizing principle in understanding the dynamics and mechanics of dense biological tissue. In this work we explore the interplay between geometry and rigidity in two-dimensional vertex models confined to the surface of a sphere. By considering shapes of cells defined by perimeters whose magnitude depends on geodesic distances and areas determined by spherical polygons, the critical shape index in such models is affected by the size of the cell relative to the radius of the sphere on which it is embedded. This implies that cells can collectively rigidify by growing the size of the sphere, i.e. by tuning the curvature of their domain. Finite-temperature studies indicate that cell motility is affected well away from the zero-temperature transition point., Comment: 8 pages, 4 figures, fun numerical results

Numerical modeling of nematic liquid crystals using the tensorial Landau-de Gennes (LdG) theory provides detailed insights into the structure and energetics of the enormous variety of possible topological defect configurations that may arise when the liquid crystal is in contact with colloidal inclusions or structured boundaries. However, these methods can be computationally expensive, making it challenging to predict (meta)stable configurations involving several colloidal particles, and they are often restricted to system sizes well below the experimental scale. Here we present an open-source software package that exploits the embarrassingly parallel structure of the lattice discretization of the LdG approach. Our implementation, combining CUDA/C++ and OpenMPI, allows users to accelerate simulations using both CPU and GPU resources in either single- or multiple-core configurations. We make use of an efficient minimization algorithm, the Fast Inertial Relaxation Engine (FIRE) method, that is well-suited to large-scale parallelization, requiring little additional memory or computational cost while offering performance competitive with other commonly used methods. In multi-core operation we are able to scale simulations up to supra-micron length scales of experimental relevance, and in single-core operation the simulation package includes a user-friendly GUI environment for rapid prototyping of interfacial features and the multifarious defect states they can promote. To demonstrate this software package, we examine in detail the competition between curvilinear disclinations and point-like hedgehog defects as size scale, material properties, and geometric features are varied. We also study the effects of an interface patterned with an array of topological point-defects., Comment: 16 pages, 6 figures, 1 youtube link. The full catastrophe

We consider the problem of detecting a noisy induced multiplex template network in a larger multiplex background network. Our approach, which extends the framework of Sussman et al. (2019) to the multiplex setting, leverages a multiplex analogue of the classical graph matching problem to use the template as a matched filter for efficiently searching the background for candidate template matches. The effectiveness of our approach is demonstrated both theoretically and empirically, with particular attention paid to the potential benefits of considering multiple channels., Comment: 27 pages, 10 figures

Recent work on particle-based models of tissues has suggested that any finite rate of cell division and cell death is sufficient to fluidize an epithelial tissue. At the same time, experimental evidence has indicated the existence of glassy dynamics in some epithelial layers despite continued cell cycling. To address this discrepancy, we quantify the role of cell birth and death on glassy states in confluent tissues using simulations of an active vertex model that includes cell motility, cell division, and cell death. Our simulation data is consistent with a simple ansatz in which the rate of cell-life cycling and the rate of relaxation of the tissue in the absence of cell cycling contribute independently and additively to the overall rate of cell motion. Specifically, we find that a glass-like regime with caging behavior indicated by subdiffusive cell displacements can be achieved in systems with sufficiently low rates of cell cycling., Comment: Main text (10 pages, 5 figures) and Appendices (7 pages, 7 figures)

Surface tension governed by differential adhesion can drive fluid particle mixtures to sort into separate regions, i.e., demix. Does the same phenomenon occur in confluent biological tissues? We begin to answer this question for epithelial monolayers with a combination of theory via a vertex model and experiments on keratinocyte monolayers. Vertex models are distinct from particle models in that the interactions between the cells are shape-based, as opposed to distance-dependent. We investigate whether a disparity in cell shape or size alone is sufficient to drive demixing in bidisperse vertex model fluid mixtures. Surprisingly, we observe that both types of bidisperse systems robustly mix on large lengthscales. On the other hand, shape disparity generates slight demixing over a few cell diameters, a phenomenon we term micro-demixing. This result can be understood by examining the differential energy barriers for neighbor exchanges (T1 transitions). Experiments with mixtures of wild-type and E-cadherin-deficient keratinocytes on a substrate are consistent with the predicted phenomenon of micro-demixing, which biology may exploit to create subtle patterning. The robustness of mixing at large scales, however, suggests that despite some differences in cell shape and size, progenitor cells can readily mix throughout a developing tissue until acquiring means of recognizing cells of different types., Comment: 32 pages, 17 figures

Given a pair of graphs with the same number of vertices, the inexact graph matching problem consists in finding a correspondence between the vertices of these graphs that minimizes the total number of induced edge disagreements. We study this problem from a statistical framework in which one of the graphs is an errorfully observed copy of the other. We introduce a corrupting channel model, and show that in this model framework, the solution to the graph matching problem is a maximum likelihood estimator. Necessary and sufficient conditions for consistency of this MLE are presented, as well as a relaxed notion of consistency in which a negligible fraction of the vertices need not be matched correctly. The results are used to study matchability in several families of random graphs, including edge independent models, random regular graphs and small-world networks. We also use these results to introduce measures of matching feasibility, and experimentally validate the results on simulated and real-world networks.

The graph matching problem aims to discover a latent correspondence between the vertex sets of two observed graphs. This problem has proven to be quite challenging, with few satisfying methods that are computationally tractable and widely applicable. The FAQ algorithm has proven to have good performance on benchmark problems and works with a indefinite relaxation of the problem. Due to the indefinite relaxation, FAQ is not guaranteed to find the global maximum. However, if prior information is known about the true correspondence, this can be leveraged to initialize the algorithm near the truth. We show that given certain properties of this initial matrix, with high probability the FAQ algorithm will converge in two steps to the truth under a flexible model for pairs of random graphs. Importantly, this result implies that there will be no local optima near the global optima, providing a method to assess performance., Comment: 26 pages, 3 figures

Purely repulsive active particles spontaneously undergo motility-induced phase separation (MIPS) into condensed and dilute phases. Remarkably, the mechanical tension measured along the interface between these phases is negative. In equilibrium this would imply an unstable interface that wants to expand, but these out-of-equilibrium systems display long-time stability and have intrinsically stiff boundaries. Here, we study this phenomenon in detail using active Brownian particle simulations and a novel frame of reference. By shifting from the global (or laboratory) frame to a local frame that follows the dynamics of the phase boundary, we observe correlations between the local curvature of the interface and the measured value of the tension. Importantly, our analysis reveals the presence of sustained local tangential motion of particles within a surface layer in both the gas and the dense regions. The combined tangential current in the gas and self-shearing of the surface of the dense phase suggest a stiffening interface that redirects particles along itself to heal local fluctuations. These currents restore the otherwise wildly fluctuating interface through an out-of-equilibrium Marangoni effect. We discuss the implications of our observations on phenomenological models of interfacial dynamics., Comment: 10 pages, 9 figures

The problem of finding the vertex correspondence between two noisy graphs with different number of vertices where the smaller graph is still large has many applications in social networks, neuroscience, and computer vision. We propose a solution to this problem via a graph matching matched filter: centering and padding the smaller adjacency matrix and applying graph matching methods to align it to the larger network. The centering and padding schemes can be incorporated into any algorithm that matches using adjacency matrices. Under a statistical model for correlated pairs of graphs, which yields a noisy copy of the small graph within the larger graph, the resulting optimization problem can be guaranteed to recover the true vertex correspondence between the networks. However, there are currently no efficient algorithms for solving this problem. To illustrate the possibilities and challenges of such problems, we use an algorithm that can exploit a partially known correspondence and show via varied simulations and applications to {\it Drosophila} and human connectomes that this approach can achieve good performance., Comment: 41 pages, 7 figures

In order to understand the mechanisms for glassy dynamics in biological tissues and shed light on those in non-biological materials, we study the low-temperature disordered phase of 2D vertex-like models. Recently it has been noted that vertex models have quite unusual behavior in the zero-temperature limit, with rigidity transitions that are controlled by residual stresses and therefore exhibit very different scaling and phenomenology compared to particulate systems. Here we investigate the finite-temperature phase of two-dimensional Voronoi and Vertex models, and show that they have highly unusual, sub-Arrhenius scaling of dynamics with temperature. We connect the anomalous glassy dynamics to features of the potential energy landscape associated with zero-temperature inherent states., Comment: 8 pages, 8 figures

How can dense biological tissue maintain sharp boundaries between coexisting cell populations? We explore this question within a simple vertex model for cells, focusing on the role of topology and tissue surface tension. We show that the ability of cells to independently regulate adhesivity and tension, together with neighbor-based interaction rules, lets them support strikingly unusual interfaces. In particular, we show that mechanical- and fluctuation-based measurements of the effective surface tension of a cellular aggregate yield different results, leading to mechanically soft interfaces that are nevertheless extremely sharp.

The random dot product graph (RDPG) is an independent-edge random graph that is analytically tractable and, simultaneously, either encompasses or can successfully approximate a wide range of random graphs, from relatively simple stochastic block models to complex latent position graphs. In this survey paper, we describe a comprehensive paradigm for statistical inference on random dot product graphs, a paradigm centered on spectral embeddings of adjacency and Laplacian matrices. We examine the analogues, in graph inference, of several canonical tenets of classical Euclidean inference: in particular, we summarize a body of existing results on the consistency and asymptotic normality of the adjacency and Laplacian spectral embeddings, and the role these spectral embeddings can play in the construction of single- and multi-sample hypothesis tests for graph data. We investigate several real-world applications, including community detection and classification in large social networks and the determination of functional and biologically relevant network properties from an exploratory data analysis of the Drosophila connectome. We outline requisite background and current open problems in spectral graph inference., Comment: An expository survey paper on a comprehensive paradigm for inference for random dot product graphs, centered on graph adjacency and Laplacian spectral embeddings. Paper outlines requisite background; summarizes theory, methodology, and applications from previous and ongoing work; and closes with a discussion of several open problems

Vertex models are a popular approach to modeling the mechanical and dynamical properties of dense biological tissues, describing the tissue as a network of connected polygons representing the cells. Recently a class of two-dimensional vertex models was shown to exhibit a disordered rigidity transition controlled by the preferred cellular geometry, echoing experimental findings. An attractive variant of these models uses a Voronoi tessellation to describe the cells and endows them with a non-equilibrium model of cellular motility, leading to rich, glassy behavior. This glassy behavior was suggested to be inextricably linked to an underlying jamming transition. We test this conjecture, exploring the low-effective-temperature limit of the Voronoi model by studying cell trajectories from detailed dynamical simulations in combination with rigidity measurements of energy-minimized disordered cell configurations. We find that the zero-temperature limit of this model has no unjamming transition., Comment: 6 pages, 4 figures

We consider the problem of graph matchability in non-identically distributed networks. In a general class of edge-independent networks, we demonstrate that graph matchability can be lost with high probability when matching the networks directly. We further demonstrate that under mild model assumptions, matchability is almost perfectly recovered by centering the networks using Universal Singular Value Thresholding before matching. These theoretical results are then demonstrated in both real and synthetic simulation settings. We also recover analogous core-matchability results in a very general core-junk network model, wherein some vertices do not correspond between the graph pair., Comment: 44 pages, 10 figures