Inferring propagation paths for sparsely observed perturbations on complex networks.
In a complex system, perturbations propagate by following paths on the network of interactions among the system's units. In contrast to what happens with the spreading of epidemics, observations of general perturbations are often very sparse in time (there is a single observation of the perturbed system) and in "space" (only a few perturbed and unperturbed units are observed). A major challenge in many areas, from biology to the social sciences, is to infer the propagation paths from observations of the effects of perturbation under these sparsity conditions. We address this problem and show that it is possible to go beyond the usual approach of using the shortest paths connecting the known perturbed nodes. Specifically, we show that a simple and general probabilistic model, which we solved using belief propagation, provides fast and accurate estimates of the probabilities of nodes being perturbed.
Departament d'Enginyeria Química, Universitat Rovira i Virgili, Tarragona 43007, Catalonia, Spain.
Francesco Alessandro
FA
Massucci
Departament d'Enginyeria Química, Universitat Rovira i Virgili, Tarragona 43007, Catalonia, Spain.
Jonathan
J
Wheeler
Cheminformatics and Nutrition Research Group, Department of Biochemistry and Biotechnology, Universitat Rovira i Virgili, Tarragona 43007, Spain.
Raúl
0000-0001-9691-1906
R
Beltrán-Debón
Unitat de Recerca Biomèdica, Hospital Universitari de Sant Joan, Institut d'Investigació Sanitària Pere Virgili, Universitat Rovira i Virgili, Reus, Catalonia, Spain.
Jorge
J
Joven
Departament d'Enginyeria Química, Universitat Rovira i Virgili, Tarragona 43007, Catalonia, Spain.
Marta
0000-0002-8140-6525
M
Sales-Pardo
Departament d'Enginyeria Química, Universitat Rovira i Virgili, Tarragona 43007, Catalonia, Spain.; Institució Catalana de Recerca i Estudis Avançats (ICREA), Barcelona 08010, Catalonia, Spain.
Roger
0000-0002-3597-4310
R
Guimerà
Complex networks; belief propagation; inference; perturbed systems