Intelligent Systems



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
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
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, qnac004, February 2023 (article)

Code Preprint DOI [BibTex]

Code Preprint 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
Modeling Node Exposure for Community Detection in Networks

Othman, S., Schulz, J., Baity-Jesi, M., De Bacco, C.

Proceedings of The Eleventh International Conference on Complex Networks and their Applications: COMPLEX NETWORKS 2022, Springer, July 2022 (conference)

Preprint link (url) DOI [BibTex]

Preprint 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]


no image
Estimating Social Influence from Observational Data

Sridhar, D., De Bacco, C., Blei, D.

First Conference on Causal Learning and Reasoning, 2022 (conference)

Preprint link (url) [BibTex]

Preprint link (url) [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
Convergence properties of optimal transport-based temporal networks

Baptista Theuerkauf, D., De Bacco, C.

Proceedings of the Tenth International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2021, September 2021 (conference)

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

Preprint [BibTex]

Preprint [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]


no image
Developing new methods for routing and optimal transport on networks

Lonardi, A.

Università degli studi di Padova, 2020 (mastersthesis)

pdf [BibTex]


no image
Edge-Disjoint Path Problem on Stochastic Block Models through Message Passing

Lorenzo Ferretti

Sapienza Università di Roma, 2020 (mastersthesis)

[BibTex]

[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
Analysis and modelling of information ecosystems

Emanuele Pigani

Università degli studi di Padova, October 2019 (mastersthesis)

link (url) [BibTex]

link (url) [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]


no image
A new approach for community detection in multilayer networks

Contisciani, M.

Università degli studi di Padova, September 2019 (mastersthesis)

link (url) [BibTex]

link (url) [BibTex]

2018


no image
A physical model for efficient ranking in networks

De Bacco, C., Larremore, D. B., Moore, C.

Science Advances, 4(7), American Association for the Advancement of Science, 2018 (article)

Code Preprint link (url) DOI [BibTex]

2018

Code Preprint link (url) DOI [BibTex]


no image
AreWater Smart Landscapes’ Contagious? An epidemic approach on networks to study peer effects

Brelsford, C., De Bacco, C.

Networks and Spatial Economics (NETS), pages: 1572-9427, 2018 (article)

Preprint link (url) [BibTex]

Preprint link (url) [BibTex]

2017


no image
Community detection, link prediction, and layer interdependence in multilayer networks

De Bacco, C., Power, E. A., Larremore, D. B., Moore, C.

Physical Review E, 95(4):042317, APS, 2017 (article)

Code Preprint link (url) [BibTex]

2017

Code Preprint link (url) [BibTex]

2016


no image
Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering

Lesieur, T., De Bacco, C., Banks, J., Krzakala, F., Moore, C., Zdeborová, L.

In Communication, Control, and Computing (Allerton), 2016 54th Annual Allerton Conference on, pages: 601-608, 2016 (inproceedings)

Preprint link (url) [BibTex]

2016

Preprint link (url) [BibTex]


no image
Stochastic search with Poisson and deterministic resetting

Bhat, U., De Bacco, C., Redner, S.

Journal of Statistical Mechanics: Theory and Experiment, 2016(8):083401, IOP Publishing, 2016 (article)

Preprint link (url) [BibTex]

Preprint link (url) [BibTex]


no image
Dynamics of beneficial epidemics

Berdahl, A., Brelsford, C., De Bacco, C., Dumas, M., Ferdinand, V., Grochow, J. A., Hébert-Dufresne, L., Kallus, Y., Kempes, C. P., Kolchinsky, A., others,

arXiv preprint arXiv:1604.02096, 2016 (article)

Preprint [BibTex]

Preprint [BibTex]