Network extraction by routing optimization

Abstract

Routing optimization is a relevant problem in many contexts. Solving directly this type of optimization problem is often computationally unfeasible. Recent studies suggest that one can instead turn this problem into one of solving a dynamical system of equations, which can instead be solved efficiently using numerical methods. This results in enabling the acquisition of optimal network topologies from a variety of routing problems. However, the actual extraction of the solution in terms of a final network topology relies on numerical details which can prevent an accurate investigation of their topological properties. In this context, theoretical results are fully accessible only to an expert audience and ready-to-use implementations for non-experts are rarely available or insufficiently documented. In particular, in this framework, final graph acquisition is a challenging problem in-and-of-itself. Here we introduce a method to extract networks topologies from dynamical equations related to routing optimization under various parameters' settings. Our method is made of three steps: first, it extracts an optimal trajectory by solving a dynamical system, then it pre-extracts a network and finally, it filters out potential redundancies. Remarkably, we propose a principled model to address the filtering in the last step, and give a quantitative interpretation in terms of a transport-related cost function. This principled filtering can be applied to more general problems such as network extraction from images, thus going beyond the scenarios envisioned in the first step. Overall, this novel algorithm allows practitioners to easily extract optimal network topologies by combining basic tools from numerical methods, optimization and network theory. Thus, we provide an alternative to manual graph extraction which allows a grounded extraction from a large variety of optimal topologies.

arXiv comment17 pages, 7 main Figures, 3 SI figures

References in corpus (16)

• Optimal network topologies for local search with congestion
• Damage and fluctuations induce loops in optimal transport networks
• Entangled networks, synchronization, and optimal network topology
• Fluctuations and redundancy in optimal transport networks
• Designing optimal transport networks
• Global Optimization, Local Adaptation, and the Role of Growth in Distribution Networks
• From the Physics of Interacting Polymers to Optimizing Routes on the London Underground
• Statistical Mechanics of Steiner trees
• Towards a stationary Monge-Kantorovich dynamics: the Physarum Polycephalum experience
• Numerical Solution of Monge-Kantorovich Equations via a dynamic formulation
• Optimal noise-canceling networks
• Shortest node-disjoint paths on random graphs
• The edge-disjoint path problem on random graphs by message-passing
• IRLS and Slime Mold: Equivalence and Convergence
• Physarum Dynamics and Optimal Transport for Basis Pursuit
• The cavity approach for Steiner trees packing problems

Cited by in corpus (13)

• Urban transportation networks and optimal transport-based infrastructures: similarity and economy of scale
• Optimal transport in multilayer networks for traffic flow optimization
• Designing optimal networks for multi-commodity transport problem
• Sustainable optimal transport in multilayer networks
• Multicommodity routing optimization for engineering networks
• Principled network extraction from images
• Cohesive urban bicycle infrastructure design through optimal transport routing in multilayer networks
• Bilevel Optimization for Traffic Mitigation in Optimal Transport Networks
• Infrastructure adaptation and emergence of loops in network routing with time-dependent loads
• Community Detection in networks by Dynamical Optimal Transport Formulation
• Convergence properties of optimal transport-based temporal networks
• Immiscible Color Flows in Optimal Transport Networks for Image Classification
• Optimal transport with constraints: from mirror descent to classical mechanics