An official website of the United States government
Abstract 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.
more »
« less
Symmetry breaking in optimal transport networks
Abstract Engineering multilayer networks that efficiently connect sets of points in space is a crucial task in all practical applications that concern the transport of people or the delivery of goods. Unfortunately, our current theoretical understanding of the shape of such optimal transport networks is quite limited. Not much is known about how the topology of the optimal network changes as a function of its size, the relative efficiency of its layers, and the cost of switching between layers. Here, we show that optimal networks undergo sharp transitions from symmetric to asymmetric shapes, indicating that it is sometimes better to avoid serving a whole area to save on switching costs. Also, we analyze the real transportation networks of the cities of Atlanta, Boston, and Toronto using our theoretical framework and find that they are farther away from their optimal shapes as traffic congestion increases.
more »
« less
- Award ID(s):
- 1927418
- PAR ID:
- 10504821
- Publisher / Repository:
- Nature Publishing Group
- Date Published:
- Journal Name:
- Nature Communications
- Volume:
- 15
- Issue:
- 1
- ISSN:
- 2041-1723
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract An excellent method for predicting links in multiplex networks is reflected in its ability to reconstruct them accurately. Although link prediction methods perform well on estimating the existence probability of each potential link in monoplex networks by the set of partially observed links, we lack a mathematical tool to reconstruct the multiplex network from the observed aggregate topology and partially observed links in multiplex networks. Here, we fill this gap by developing a theoretical and computational framework that builds a probability space containing possible structures with a maximum likelihood estimation. Then, we discovered that the discrimination, an indicator quantifying differences between layers from an entropy perspective, determines the reconstructability, i.e., the accuracy of such reconstruction. This finding enables us to design the optimal strategy to allocate the set of observed links in different layers for promoting the optimal reconstruction of multiplex networks. Finally, the theoretical analyses are corroborated by empirical results from biological, social, engineered systems, and a large volume of synthetic networks.more » « less
-
Abstract Atomic frequency comb (AFC) quantum memories are a promising technology for quantum repeater networks because they enable multi-mode, long-time, and high-fidelity storage of photons with on-demand retrieval. The optimization of the retrieval efficiency of an AFC memory is important because it strongly impacts the entanglement distribution rate in quantum networks. Despite initial theoretical analyses and recent experimental demonstrations, a rigorous proof of the universally optimal configuration for the highest AFC retrieval efficiency has not been presented. In this paper we present a simple analytical proof which shows that the optimized square tooth offers the highest retrieval efficiency among all tooth shapes, under the physical constraint of finite optical depth of an atomic ensemble. The optimality still holds when the non-zero background absorption and the finite optical linewidth of atoms are considered. We further compare square, Lorentzian and Gaussian tooth shapes to reinforce the practical advantage of the square-tooth AFC in retrieval efficiency. Our proof lays rigorous foundation for the recipe of creating optimal AFC under realistic experimental conditions.more » « less
-
Abstract Deployable geometries are finite auxetic structures that preserve their overall shapes during expansion and contraction. The topological behaviors emerge from intricately arranged elements and their connections. Despite the considerable utility of such configurations in nature and in engineering, deployable nanostructures have never been demonstrated. Here a deployable flight ring, a simplified planar structure of Hoberman sphere is shown, using DNA origami. The DNA flight ring consists of topologically assembled six triangles in two layers that can slide against each other, thereby switching between two distinct (open and closed) states. The origami topology is a trefoil knot, and its auxetic reconfiguration results in negative Poisson's ratios. This work shows the feasibility of deployable nanostructures, providing a versatile platform for topological studies and opening new opportunities for bioengineering.more » « less
-
Abstract Quantifying the structure and dynamics of species interactions in ecological communities is fundamental to studying ecology and evolution. While there are numerous approaches to analysing ecological networks, there is not yet an approach that can (1) quantify dissimilarity in the global structure of ecological networks that range from identical species and interaction composition to zero shared species or interactions and (2) map species between such networks while incorporating additional ecological information, such as species traits or abundances.To address these challenges, we introduce the use of optimal transport distances to quantify ecological network dissimilarity and functionally equivalent species between networks. Specifically, we describe the Gromov–Wasserstein (GW) and Fused Gromov–Wasserstein (FGW) distances. We apply these optimal transport methods to synthetic and empirical data, using mammal food webs throughout sub‐Saharan Africa for illustration. We showcase the application of GW and FGW distances to identify the most functionally similar species between food webs, incorporate additional trait information into network comparisons and quantify food web dissimilarity among geographic regions.Our results demonstrate that GW and FGW distances can effectively differentiate ecological networks based on their topological structure while identifying functionally equivalent species, even when networks have different species. The FGW distance further improves node mapping for basal species by incorporating node‐level traits. We show that these methods allow for a more nuanced understanding of the topological similarities in food web networks among geographic regions compared to an alternative measure of network dissimilarity based on species identities.Optimal transport distances offer a new approach for quantifying functional equivalence between networks and a measure of network dissimilarity suitable for a broader range of uses than existing approaches. OT methods can be harnessed to analyse ecological networks at large spatial scales and compare networks among ecosystems, realms or taxa. Optimal transport‐based distances, therefore, provide a powerful tool for analysing ecological networks with great potential to advance our understanding of ecological community structure and dynamics in a changing world.more » « less
