Search for: All records

We define a metric—the network Gromov–Wasserstein distance—on weighted, directed networks that is sensitive to the presence of outliers. In addition to proving its theoretical properties, we supply network invariants based on optimal transport that approximate this distance by means of lower bounds. We test these methods on a range of simulated network datasets and on a dataset of real-world global bilateral migration. For our simulations, we define a network generative model based on the stochastic block model. This may be of independent interest for benchmarking purposes.

We consider the problem of classifying curves when they are observed only partially on their parameter domains. We propose computational methods for (i) completion of partially observed curves; (ii) assessment of completion variability through a nonparametric multiple imputation procedure; (iii) development of nearest neighbor classifiers compatible with the completion techniques. Our contributions are founded on exploiting the geometric notion of shape of a curve, defined as those aspects of a curve that remain unchanged under translations, rotations and reparameterizations. Explicit incorporation of shape information into the computational methods plays the dual role of limiting the set of all possible completions of a curve to those with similar shape while simultaneously enabling more efficient use of training data in the classifier through shape-informed neighborhoods. Our methods are then used for taxonomic classification of partially observed curves arising from images of fossilized Bovidae teeth, obtained from a novel anthropological application concerning paleoenvironmental reconstruction.

In the parking model on ℤd, each vertex is initially occupied by a car (with probability p) or by a vacant parking spot (with probability 1−p). Cars perform independent random walks and when they enter a vacant spot, they park there, thereby rendering the spot occupied. Cars visiting occupied spots simply keep driving (continuing their random walk). It is known that p=1/2 is a critical value in the sense that the origin is a.s. visited by finitely many distinct cars when p<1/2, and by infinitely many distinct cars when p≥1/2. Furthermore, any given car a.s. eventually parks for p≤1/2 and with positive probability does not park for p>1/2. We study the subcritical phase and prove that the tail of the parking time τ of the car initially at the origin obeys the bounds exp(−C1tdd+2)≤ℙp(τ>t)≤exp(−c2tdd+2) for p>0 sufficiently small. For d=1, we prove these inequalities for all p∈[0,1/2). This result presents an asymmetry with the supercritical phase (p>1/2), where methods of Bramson--Lebowitz imply that for d=1 the corresponding tail of the parking time of the parking spot of the origin decays like e−ct√. Our exponent d/(d+2) also differs from those previously obtained in the case of moving obstacles.