1,720,969 research outputs found
Biologically inspired formulation of Optimal Transport Problems
Get PDFIn this thesis we propose a model that we conjecture is a new and original formulation of the Optimal Transport Problem, a recently expanding area of mathematics that studies optimal strategies to move resources from one place to another. The proposed approach is an infinite-dimensional extension of a model describing the dynamics of Physarum Polycephalum (PP), a slime mold with surprising abilities to find the shortest path connecting two food sources. The original model describes the dynamics of the slime mold on a finite planar graph using a pipe-flow analogy whereby mass transfer occurs because of pressure differences with a conductivity coefficient that varies with the flow intensity. This model has been shown to be equivalent to a problem of "optimal transportation" on graphs.
Our extension abandons the graph structure and moves to a continuous domain, coupling an elliptic diffusion equation enforcing PP density balance with an ordinary differential equations governing the flow dynamics. We conjecture that the new system of equations presents a time-asymptotic equilibrium connected to solutions of many instances of OTP, including the standard L1 case and the congested and branched transport problems.
From a theoretical point of view, we are only able to prove well-posedness of the proposed model for sufficiently small times and under restrictive hypothesis on the the regularity of the diffusion coefficient and the functions describing the initial and final configurations of the transported mass. However, our extensive numerical results show that the approximate solution of our proposed formulation converges at large times to an equilibrium configuration that well compares with the solutions of the different flavors of OTP. In particular, we are able to efficiently recover the numerical solutions that closely resemble the singular and ramified structures typical of branched transport problems. These simulations provide strong support to our conjectures. Notwithstanding the numerical difficulties related mainly to the ill-conditioning of the algebraic systems, the rather simple approach adopted for the discretization of the proposed formulation resulted highly efficient and robust in terms of convergence and computational speed.
We also propose and tackle several applications to real world problems. In particular, we discuss how our formulation can be applied to model the geomorphology of river networks and the dynamics of plant roots. In addition, based on numerical evidence, we argue that the emergence of robustness-enhancing loops in complex networks can be attributed to non-stationarity of the forcing terms rather than optimality of the network configuration.In questa tesi proponiamo un nuovo modello che congetturiamo rappresenti una nuova formulazione del Problema di Trasporto Ottimo, un'area della matematica notevolmente sviluppatasi negli ultimi ultimi anni e che studia come trasportare in maniera efficiente delle risorse da un luogo ad un altro.
La formulazione da noi proposta è l'estensione infinito-dimensionale di un modello nato per descrivere il comportamento di una muffa, dal nome Physarum Polycephalum (PP), capace di trovare il cammino minimo tra due fonti di cibo. Nel modello originale, definito su grafi, il corpo di PP viene schematizzata come un tubo attraverso il quale il trasporto di risorse avviene per mezzo di un flusso dato dal prodotto di un gradiente di pressione per un coefficiente di diffusione. Quest'ultimo varia nel tempo in funzione dell'intensità del flusso stesso, descrivendo in tal modo la dinamica adattativa della muffa.
L'equivalenza tra tale modello e la soluzione di problemi di trasporto ottimo su grafi è già stata dimostrata. Il formulazione da noi proposta abbandona la struttura finito dimensionale del grafo per passare in un ambiente continuo. Il derivante modello è descritto da un sistema composto da un'equazione ellittica con un coefficiente di diffusione e un'equazione differenziale ordinaria per il coefficiente. In questa tesi proponiamo la congettura che quest'ultimo sistema ammetta un equilibrio stazionario legato alla soluzione di problemi di trasporto ottimo, sia per il caso L1, sia per i problemi di trasporto congestionato e ramificato.
Da un punto di visto teorico, siamo riusciti a provare che il modello è ben posto solo assumendo determinate ipotesi di regolarità del coefficiente di diffusione e delle densità che descrivono la configurazione iniziale e finale delle masse trasportate. Nonostante ciò, numerosi risultati numerici mostrano come la soluzione approssimata del nostro modello converga a soluzioni stazionarie che ben si confrontano con la soluzione dei sopracitati problemi di trasporto ottimo. Riusciamo inoltre ad ottenere soluzioni numeriche che assomigliano fortemente alle strutture singolari del trasporto ramificato, dando ulteriore supporto alle nostre congetture. Nonostante alcune difficoltà numeriche, essenzialmente legate al malcondizionamenteo di sistemi lineari, lo schema numerico utilizzato per la discretizzazione del nostro modello, la cui implementazione risulta relativamente semplice, si è rivelato estremamente efficiente e robusto, sia da punto di visto delle convergenze numeriche, sia dal punto di vista dell'efficienza computazionale.
Il nostro modello si presta inoltre a numerose applicazioni a problemi reali, come lo studio della morfologia dei fiumi e la modellizzazione dell'evoluzione delle radici delle piante, argomenti discussi nella parte finale della tesi. In ultimo, sulla base di prove numeriche, analizziamo come la presenza di loop in reti complesse, indice della loro robustezza, possa essere interpretata non come una proprietà di "ottimalità" della rete stessa, bensì come un riflesso della non stazionarietà delle forzanti
Fast Iterative Solution of the Optimal Transport Problem on Graphs
Get PDFIn this paper, we address the numerical solution of the optimal transport problem on
undirected weighted graphs, taking the shortest path distance as transport cost. The optimal solution
is obtained from the long-time limit of the gradient descent dynamics. Among dierent time stepping
procedures for the discretization of this dynamics, a backward Euler time stepping scheme combined
with the inexact Newton{Raphson method results in a robust and accurate approach for the solution
of the optimal transport problem on graphs. It is found experimentally that the algorithm requires
solving between O(1) and O(m0:36) linear systems involving weighted Laplacian matrices, where m
is the number of edges. These linear systems are solved via algebraic multigrid methods, resulting
in an ecient solver for the optimal transport problem on graphs
Numerical Solution of Monge–Kantorovich Equations via a Dynamic Formulation
No full textWe extend our previous work on a biologically inspired dynamic Monge-Kantorovich model (Facca et al. in SIAM J Appl Math 78:651-676, 2018) and propose it as an effective tool for the numerical solution of the L1-PDE based optimal transportation model. We first introduce a new Lyapunov-candidate functional and show that its derivative along the solution trajectory is strictly negative. Moreover, we are able to show that this functional admits the optimal transport density as a unique minimizer, providing further support to the conjecture that our dynamic model is time-asymptotically equivalent to the Monge-Kantorovich equations governing L1 optimal transport. Remarkably, this newly proposed Lyapunov-candidate functional can be effectively used to calculate the Wasserstein-1 (or earth mover's) distance between two measures. We numerically solve these equations via a simple approach based on standard forward Euler time stepping and linear Galerkin finite element. The accuracy and robustness of the proposed solver is verified on a number of test problems of mixed complexity also in comparison with other approaches proposed in the literature. Numerical results show that the proposed scheme is very efficient and accurate for the calculation the Wasserstein-1 distances
Towards a stationary Monge-Kantorovich dynamics: the Physarum Polycephalum experience
Get PDFIn this work we propose an extension to the continuous setting of a model describing
the dynamics of slime mold, Physarum Polycephalum (PP), which was proposed to simulate the
ability of PP to find the shortest path connecting two food sources in a maze. The original model
describes the dynamics of the slime mold on a finite-dimensional planar graph using a pipe-flow
analogy whereby mass transfer occurs because of pressure differences with a conductivity coefficient
that varies with the flow intensity. This model has been shown to be equivalent to a problem of
“optimal transportation” on graphs. We propose an extension that abandons the graph structure
and moves to a continuous domain. The new model couples an elliptic diffusion equation enforcing PP
density balance with an ordinary differential equation governing the flow dynamics. We conjecture
that the new system of equations presents a time-asymptotic equilibrium and that such an equilibrium
point is precisely the solution of Monge–Kantorovich partial differential equations governing optimal
transportation problems. To support this conjecture, we analyze the proposed model by recasting
it into an infinite-dimensional dynamical system. We are then able to show well-posedness of the
proposed model for sufficiently small times under the hypotheses of H ̈older continuous diffusion
coefficients and essentially bounded forcing functions. Numerical results obtained with a simple fixed-
point iteration combining P1/P0 finite elements with backward Euler time stepping show that the
approximate solution of our formulation of the transportation problem converges at large times to an
equilibrium configuration that well compares with the numerical solution of the Monge–Kantorovich
equation
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Get PDFWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Dispelling the Myths Behind First-author Citation Counts
Get PDFWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
- …
