Intelligent Systems
Note: This research group has relocated.



no image
A model for efficient dynamical ranking in networks

Della Vecchia, A., Neocosmos, K., Larremore, D. B., Moore, C., De Bacco, C.

August 2023 (article) Submitted

Preprint Code link (url) [BibTex]

Preprint Code link (url) [BibTex]


no image
Latent Network Models to Account for Noisy, Multiply-Reported Social Network Data.

De Bacco, C., Contisciani, M., Cardoso-Silva, J., Safdari, H., Theuerkauf, D. B., Sweet, T., Young, J., Koster, J., Ross, C. T., McElreath, R., Redhead, D., Power, E. A.

Journal of the Royal Statistical Society: Series A, 186(3):355-375, July 2023 (article)

Code Preprint link (url) DOI [BibTex]

Code Preprint link (url) DOI [BibTex]


no image
Community Detection in Large Hypergraphs

Ruggeri, N., Contisciani, M., Battiston, F., De Bacco, C.

Science Advances, 9, eadg9159, June 2023 (article)

Preprint Code Published version DOI [BibTex]


no image
Hypergraphx: a library for higher-order network analysis

Lotito, Q. F., Contisciani, M., De Bacco, C., Di Gaetano, L., Gallo, L., Montresor, A., Musciotto, F., Ruggeri, N., Battiston, F.

Journal of Complex Networks, 11, May 2023 (article)

Preprint Code DOI [BibTex]

Preprint Code DOI [BibTex]


no image
Convergence properties of optimal transport-based temporal hypernetworks

Baptista, D., De Bacco, C.

Applied Network Science, 8:3, January 2023 (article)

Preprint DOI [BibTex]

Preprint DOI [BibTex]


no image
Community Detection in networks by Dynamical Optimal Transport Formulation

Leite, D., Baptista, D., Ibrahim, A. A., Facca, E., De Bacco, C.

Scientific Reports, 12, pages: 16811, October 2022 (article)

Preprint Code link (url) DOI [BibTex]

Preprint Code link (url) DOI [BibTex]


no image
Revealing the similarity between urban transportation networks and optimal transport-based infrastructures

Leite, D., De Bacco, C.

September 2022 (article) Submitted

Abstract
Designing and optimizing the structure of urban transportation networks is a challenging task. In this study, we propose a method inspired by optimal transport theory to reproduce the optimal structure of public transportation networks, that uses little information in input. Contrarily to standard approaches, it does not assume any initial backbone network infrastructure, but rather extracts this directly from a continuous space using only a few origin and destination points. Analyzing a set of urban rail, tram and subway networks, we find a high degree of similarity between simulated and real infrastructures. By tuning one parameter, our method can simulate a range of different networks that can be further used to suggest possible improvements in terms of relevant transportation properties. Outputs of our algorithm provide naturally a principled quantitative measure of similarity between two networks that can be used to automatize the selection of similar simulated networks.

Preprint Code link (url) DOI [BibTex]


no image
Multicommodity routing optimization for engineering networks

Lonardi, A., Putti, M., De Bacco, C.

Scientific Reports , 12, pages: 7474, May 2022 (article)

Preprint Code link (url) DOI [BibTex]

2021


no image
Designing optimal networks for multicommodity transport problem

Lonardi, A., Facca, E., Putti, M., De Bacco, C.

Physical Review Research, 3(4):043010, October 2021 (article)

Abstract
Designing and optimizing different flows in networks is a relevant problem in many contexts. While a number of methods have been proposed in the physics and optimal transport literature for the one-commodity case, we lack similar results for the multi-commodity scenario. In this paper we present a model based on optimal transport theory for finding optimal multi-commodity flow configurations on networks. This model introduces a dynamics that regulates the edge conductivities to achieve, at infinite times, a minimum of a Lyapunov functional given by the sum of a convex transport cost and a concave infrastructure cost. We show that the long time asymptotics of this dynamics are the solutions of a standard constrained optimization problem that generalizes the one-commodity framework. Our results provide new insights into the nature and properties of optimal network topologies. In particular, they show that loops can arise as a consequence of distinguishing different flow types, complementing previous results where loops, in the one-commodity case, were obtained as a consequence of imposing dynamical rules to the sources and sinks or when enforcing robustness to damage. Finally, we provide an efficient implementation of our model which convergences faster than standard optimization methods based on gradient descent.

Code Preprint DOI [BibTex]

2021

Code Preprint DOI [BibTex]


no image
Principled network extraction from images

Baptista, D., Bacco, C. D.

Royal Society Open Science, 8(7):210025, July 2021 (article)

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 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.

Preprint Code DOI [BibTex]

Preprint Code DOI [BibTex]


no image
Optimal Transport in Multilayer Networks for Traffic Flow Optimization for Traffic Flow Optimization

Ibrahim, A. A., Lonardi, A., Bacco, C. D.

Algorithms, 14(7):189, June 2021 (article)

Abstract
Modeling traffic distribution and extracting optimal flows in multilayer networks is of the utmost importance to design efficient, multi-modal network infrastructures. Recent results based on optimal transport theory provide powerful and computationally efficient methods to address this problem, but they are mainly focused on modeling single-layer networks. Here, we adapt these results to study how optimal flows distribute on multilayer networks. We propose a model where optimal flows on different layers contribute differently to the total cost to be minimized. This is done by means of a parameter that varies with layers, which allows to flexibly tune the sensitivity to the traffic congestion of the various layers. As an application, we consider transportation networks, where each layer is associated to a different transportation system, and show how the traffic distribution varies as we tune this parameter across layers. We show an example of this result on the real, 2-layer network of the city of Bordeaux with a bus and tram, where we find that in certain regimes, the presence of the tram network significantly unburdens the traffic on the road network. Our model paves the way for further analysis of optimal flows and navigability strategies in real, multilayer networks.

Code Preprint DOI [BibTex]


no image
Generative model for reciprocity and community detection in networks

Safdari, H., Contisciani, M., Bacco, C. D.

Physical Review Research, 3(2):023209, April 2021 (article)

Preprint Code link (url) DOI [BibTex]

2020


no image
Network extraction by routing optimization

Baptista, T. D., Leite, D., Facca, E., Putti, M., De Bacco, C.

Scientific Reports, 10, pages: 20806, November 2020 (article)

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.

Code Preprint link (url) DOI [BibTex]

2020

Code Preprint link (url) DOI [BibTex]


no image
Sampling on networks: estimating spectral centrality measures and their impact in evaluating other relevant network measures

Ruggeri, N., De Bacco, C.

Applied Network Science, 5:81, October 2020 (article)

Abstract
We perform an extensive analysis of how sampling impacts the estimate of several relevant network measures. In particular, we focus on how a sampling strategy optimized to recover a particular spectral centrality measure impacts other topological quantities. Our goal is on one hand to extend the analysis of the behavior of TCEC [Ruggeri2019], a theoretically-grounded sampling method for eigenvector centrality estimation. On the other hand, to demonstrate more broadly how sampling can impact the estimation of relevant network properties like centrality measures different than the one aimed at optimizing, community structure and node attribute distribution. Finally, we adapt the theoretical framework behind TCEC for the case of PageRank centrality and propose a sampling algorithm aimed at optimizing its estimation. We show that, while the theoretical derivation can be suitably adapted to cover this case, the resulting algorithm suffers of a high computational complexity that requires further approximations compared to the eigenvector centrality case.

Code Preprint pdf DOI [BibTex]


no image
Community detection with node attributes in multilayer networks

Contisciani, M., Power, E. A., De Bacco, C.

Scientific Reports, 10, pages: 15736, Nature, September 2020 (article)

Code Preprint pdf DOI [BibTex]

Code Preprint pdf DOI [BibTex]

2019


no image
Sampling on Networks: Estimating Eigenvector Centrality on Incomplete Networks

Ruggeri, N., De Bacco, C.

International Conference on Complex Networks and Their Applications, November 2019 (article)

Abstract
We develop a new sampling method to estimate eigenvector centrality on incomplete networks. Our goalis to estimate this global centrality measure having at disposal a limited amount of data. This is the case inmany real-world scenarios where data collection is expensive, the network is too big for data storage capacityor only partial information is available. The sampling algorithm is theoretically grounded by results derivedfrom spectral approximation theory. We studied the problemon both synthetic and real data and tested theperformance comparing with traditional methods, such as random walk and uniform sampling. We show thatapproximations obtained from such methods are not always reliable and that our algorithm, while preservingcomputational scalability, improves performance under different error measures.

Code Preprint pdf DOI [BibTex]

2019

Code Preprint pdf DOI [BibTex]


no image
Dynamics of beneficial epidemics

Berdahl, A., Brelsford, C., De Bacco, C., Dumas, M., Ferdinand, V., Grochow, J. A., nt Hébert-Dufresne, L., Kallus, Y., Kempes, C. P., Kolchinsky, A., Larremore, D. B., Libby, E., Power, E. A., A., S. C., Tracey, B. D.

Scientific Reports, 9, pages: 15093, October 2019 (article)

DOI [BibTex]

DOI [BibTex]