Header logo is


2020


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.

pio

Code Preprint pdf DOI [BibTex]


no image
Optimal transport for multi-commodity routing on networks

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

October 2020 (article) Submitted

Abstract
We present a model for finding optimal multi-commodity flows on networks based on optimal transport theory. The model relies on solving a dynamical system of equations. We prove that its stationary solution is equivalent to the solution of an optimization problem that generalizes the one-commodity framework. In particular, it generalizes previous results in terms of optimality, scaling, and phase transitions obtained in the one-commodity case. Remarkably, for a suitable range of parameters, the optimal topologies have loops. This is radically different to the one-commodity case, where within an analogous parameter range the optimal topologies are trees. This important result is a consequence of the extension of Kirkchoff's law to the multi-commodity case, which enforces the distinction between fluxes of the different commodities. 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, and complement previous results where loops, in the one-commodity case, were arising as a consequence of imposing dynamical rules to the sources and sinks or when enforcing robustness to damage. Finally, we provide an efficient implementation for each of the two equivalent numerical frameworks, both of which achieve a computational complexity that is more efficient than that of standard optimization methods based on gradient descent. As a result, our model is not merely abstract but can be efficiently applied to large datasets. We give an example of concrete application by studying the network of the Paris metro.

pio

Code Preprint [BibTex]


no image
Community detection with node attributes in multilayer networks

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

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

pio

Code Preprint pdf [BibTex]

Code Preprint pdf [BibTex]


no image
Network extraction by routing optimization

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

Nature Scientific Reports , 10, 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.

pio

Code Preprint link (url) DOI [BibTex]

Code Preprint link (url) DOI [BibTex]