RESUMO
The paper presents an algorithm to approach the problem of Maximum Clique Enumeration, a well known NP-hard problem that have several real world applications. The proposed solution, called LGP-MCE, exploits Geometric Deep Learning, a Machine Learning technique on graphs, to filter out nodes that do not belong to maximum cliques and then applies an exact algorithm to the pruned network. To assess the LGP-MCE, we conducted multiple experiments using a substantial dataset of real-world networks, varying in size, density, and other characteristics. We show that LGP-MCE is able to drastically reduce the running time, while retaining all the maximum cliques.
Assuntos
Aprendizado Profundo , Algoritmos , Matemática , Aprendizado de MáquinaRESUMO
In the context of a global food system, the dynamics associated to international food trade have become key determinants of food security. In this paper, we resort to a diffusion model to simulate how shocks to domestic food production propagate through the international food trade network and study the relationship between trade openness and vulnerability. The results of our simulations suggest that low-income and food insecure countries tend to be the more exposed to external shocks and, at the same time, they are usually not in a position to take full advantage of international food trade when it comes to shield themselves from shocks to domestic production. We also study and discuss how nodes characteristics are associated with the propagation dynamics and with countries' vulnerability, finding that simple centrality measures can significantly predict the magnitude of the shock experienced by individual countries.
Assuntos
Comércio , Abastecimento de Alimentos , Alimentos , Segurança AlimentarRESUMO
From physics to engineering, biology and social science, natural and artificial systems are characterized by interconnected topologies whose features - e.g., heterogeneous connectivity, mesoscale organization, hierarchy - affect their robustness to external perturbations, such as targeted attacks to their units. Identifying the minimal set of units to attack to disintegrate a complex network, i.e. network dismantling, is a computationally challenging (NP-hard) problem which is usually attacked with heuristics. Here, we show that a machine trained to dismantle relatively small systems is able to identify higher-order topological patterns, allowing to disintegrate large-scale social, infrastructural and technological networks more efficiently than human-based heuristics. Remarkably, the machine assesses the probability that next attacks will disintegrate the system, providing a quantitative method to quantify systemic risk and detect early-warning signals of system's collapse. This demonstrates that machine-assisted analysis can be effectively used for policy and decision-making to better quantify the fragility of complex systems and their response to shocks.