-
Convergence properties of optimal transport-based temporal hypernetworks
Authors:
Diego Baptista,
Caterina De Bacco
Abstract:
We present a method to extract temporal hypergraphs from sequences of 2-dimensional functions obtained as solutions to Optimal Transport problems. We investigate optimality principles exhibited by these solutions from the point of view of hypergraph structures. Discrete properties follow patterns that differ from those characterizing their continuous counterparts. Analyzing these patterns can brin…
▽ More
We present a method to extract temporal hypergraphs from sequences of 2-dimensional functions obtained as solutions to Optimal Transport problems. We investigate optimality principles exhibited by these solutions from the point of view of hypergraph structures. Discrete properties follow patterns that differ from those characterizing their continuous counterparts. Analyzing these patterns can bring new insights into the studied transportation principles. We also compare these higher-order structures to their network counterparts in terms of standard graph properties. We give evidence that some transportation schemes might benefit from hypernetwork representations. We demonstrate our method on real data by analyzing the properties of hypernetworks extracted from images of real systems.
△ Less
Submitted 9 January, 2023;
originally announced January 2023.
-
Community Detection in networks by Dynamical Optimal Transport Formulation
Authors:
Daniela Leite,
Diego Baptista,
Abdullahi Ibrahim,
Enrico Facca,
Caterina De Bacco
Abstract:
Detecting communities in networks is important in various domains of applications. While a variety of methods exists to perform this task, recent efforts propose Optimal Transport (OT) principles combined with the geometric notion of Ollivier-Ricci curvature to classify nodes into groups by rigorously comparing the information encoded into nodes' neighborhoods. We present an OT-based approach that…
▽ More
Detecting communities in networks is important in various domains of applications. While a variety of methods exists to perform this task, recent efforts propose Optimal Transport (OT) principles combined with the geometric notion of Ollivier-Ricci curvature to classify nodes into groups by rigorously comparing the information encoded into nodes' neighborhoods. We present an OT-based approach that exploits recent advances in OT theory to allow tuning for traffic penalization, which enforces different transportation schemes. As a result, our model can flexibly capture different scenarios and thus increase performance accuracy in recovering communities, compared to standard OT-based formulations. We test the performance of our algorithm in both synthetic and real networks, achieving a comparable or better performance than other OT-based methods in the former case, while finding communities more aligned with node metadata in real data. This pushes further our understanding of geometric approaches in their ability to capture patterns in complex networks.
△ Less
Submitted 17 May, 2022;
originally announced May 2022.
-
Immiscible Color Flows in Optimal Transport Networks for Image Classification
Authors:
Alessandro Lonardi,
Diego Baptista,
Caterina De Bacco
Abstract:
In classification tasks, it is crucial to meaningfully exploit the information contained in data. While much of the work in addressing these tasks is devoted to building complex algorithmic infrastructures to process inputs in a black-box fashion, less is known about how to exploit the various facets of the data, before inputting this into an algorithm. Here, we focus on this latter perspective, b…
▽ More
In classification tasks, it is crucial to meaningfully exploit the information contained in data. While much of the work in addressing these tasks is devoted to building complex algorithmic infrastructures to process inputs in a black-box fashion, less is known about how to exploit the various facets of the data, before inputting this into an algorithm. Here, we focus on this latter perspective, by proposing a physics-inspired dynamical system that adapts Optimal Transport principles to effectively leverage color distributions of images. Our dynamics regulates immiscible fluxes of colors traveling on a network built from images. Instead of aggregating colors together, it treats them as different commodities that interact with a shared capacity on edges. The resulting optimal flows can then be fed into standard classifiers to distinguish images in different classes. We show how our method can outperform competing approaches on image classification tasks in datasets where color information matters.
△ Less
Submitted 27 February, 2023; v1 submitted 4 May, 2022;
originally announced May 2022.
-
Latent Network Models to Account for Noisy, Multiply-Reported Social Network Data
Authors:
Caterina De Bacco,
Martina Contisciani,
Jonathan Cardoso-Silva,
Hadiseh Safdari,
Diego Baptista,
Gabriela L. Borges,
Tracy Sweet,
Jean-Gabriel Young,
Jeremy Koster,
Cody T. Ross,
Richard McElreath,
Daniel Redhead,
Eleanor A. Power
Abstract:
Social network data are often constructed by incorporating reports from multiple individuals. However, it is not obvious how to reconcile discordant responses from individuals. There may be particular risks with multiply-reported data if people's responses reflect normative expectations -- such as an expectation of balanced, reciprocal relationships. Here, we propose a probabilistic model that inc…
▽ More
Social network data are often constructed by incorporating reports from multiple individuals. However, it is not obvious how to reconcile discordant responses from individuals. There may be particular risks with multiply-reported data if people's responses reflect normative expectations -- such as an expectation of balanced, reciprocal relationships. Here, we propose a probabilistic model that incorporates ties reported by multiple individuals to estimate the unobserved network structure. In addition to estimating a parameter for each reporter that is related to their tendency of over- or under-reporting relationships, the model explicitly incorporates a term for ``mutuality,'' the tendency to report ties in both directions involving the same alter. Our model's algorithmic implementation is based on variational inference, which makes it efficient and scalable to large systems. We apply our model to data from 75 Indian villages collected with a name-generator design, and a Nicaraguan community collected with a roster-based design. We observe strong evidence of ``mutuality'' in both datasets, and find that this value varies by relationship type. Consequently, our model estimates networks with reciprocity values that are substantially different than those resulting from standard deterministic aggregation approaches, demonstrating the need to consider such issues when gathering, constructing, and analysing survey-based network data.
△ Less
Submitted 12 December, 2022; v1 submitted 21 December, 2021;
originally announced December 2021.
-
Convergence properties of optimal transport-based temporal networks
Authors:
Diego Baptista,
Caterina De Bacco
Abstract:
We study network properties of networks evolving in time based on optimal transport principles. These evolve from a structure covering uniformly a continuous space towards an optimal design in terms of optimal transport theory. At convergence, the networks should optimize the way resources are transported through it. As the network structure shapes in time towards optimality, its topological prope…
▽ More
We study network properties of networks evolving in time based on optimal transport principles. These evolve from a structure covering uniformly a continuous space towards an optimal design in terms of optimal transport theory. At convergence, the networks should optimize the way resources are transported through it. As the network structure shapes in time towards optimality, its topological properties also change with it. The question is how do these change as we reach optimality. We study the behavior of various network properties on a number of network sequences evolving towards optimal design and find that the transport cost function converges earlier than network properties and that these monotonically decrease. This suggests a mechanism for designing optimal networks by compressing dense structures. We find a similar behavior in networks extracted from real images of the networks designed by the body shape of a slime mold evolving in time.
△ Less
Submitted 2 September, 2021;
originally announced September 2021.
-
Principled network extraction from images
Authors:
Diego Baptista,
Caterina De Bacco
Abstract:
Images of natural systems may represent patterns of network-like structure, which could reveal important information about the topological properties of the underlying subject. However, the image itself does not automatically provide a formal definition of a network in terms of sets of nodes and edges. Instead, this information should be suitably extracted from the raw image data. Motivated by thi…
▽ More
Images of natural systems may represent patterns of network-like structure, which could reveal important information about the topological properties of the underlying subject. However, the image itself does not automatically provide a formal definition of a network in terms of sets of nodes and edges. Instead, this information should be suitably extracted from the raw image data. Motivated by this, we present a principled model to extract network topologies from images that is scalable and efficient. We map this goal into solving a routing optimization problem where the solution is a network that minimizes an energy function which can be interpreted in terms of an operational and infrastructural cost. Our method relies on recent results from optimal transport theory and is a principled alternative to standard image-processing techniques that are based on heuristics. We test our model on real images of the retinal vascular system, slime mold and river networks and compare with routines combining image-processing techniques. Results are tested in terms of a similarity measure related to the amount of information preserved in the extraction. We find that our model finds networks from retina vascular network images that are more similar to hand-labeled ones, while also giving high performance in extracting networks from images of rivers and slime mold for which there is no ground truth available. While there is no unique method that fits all the images the best, our approach performs consistently across datasets, its algorithmic implementation is efficient and can be fully automatized to be run on several datasets with little supervision.
△ Less
Submitted 23 December, 2020;
originally announced December 2020.
-
Network extraction by routing optimization
Authors:
Diego Baptista,
Daniela Leite,
Enrico Facca,
Mario Putti,
Caterina De Bacco
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…
▽ More
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.
△ Less
Submitted 4 May, 2020;
originally announced May 2020.
-
Extracting Geospatial Preferences Using Relational Neighbors
Authors:
Leandro Balby Marinho,
Cláudio de Souza Baptista,
Thomas Sandholm,
Iury Nunes,
Caio Nóbrega,
Jordão Araújo
Abstract:
With the increasing popularity of location-based social media applications and devices that automatically tag generated content with locations, large repositories of collaborative geo-referenced data are appearing on-line. Efficiently extracting user preferences from these data to determine what information to recommend is challenging because of the sheer volume of data as well as the frequency of…
▽ More
With the increasing popularity of location-based social media applications and devices that automatically tag generated content with locations, large repositories of collaborative geo-referenced data are appearing on-line. Efficiently extracting user preferences from these data to determine what information to recommend is challenging because of the sheer volume of data as well as the frequency of updates. Traditional recommender systems focus on the interplay between users and items, but ignore contextual parameters such as location. In this paper we take a geospatial approach to determine locational preferences and similarities between users. We propose to capture the geographic context of user preferences for items using a relational graph, through which we are able to derive many new and state-of-the-art recommendation algorithms, including combinations of them, requiring changes only in the definition of the edge weights. Furthermore, we discuss several solutions for cold-start scenarios. Finally, we conduct experiments using two real-world datasets and provide empirical evidence that many of the proposed algorithms outperform existing location-aware recommender algorithms.
△ Less
Submitted 6 April, 2012;
originally announced April 2012.
