β-contraction: a Framework for Contracting Coloured Networks. Use Cases and Applications
Networks are nowadays pervasive in Big Data. It is often useful to regroup such data in clusters according to distinctive node features and use a representative element for each cluster, hence generating a novel contracted graph that shrank in size.
Overview
Abstract
Networks are nowadays pervasive in Big Data. It is often useful to regroup such data in clusters according to distinctive node features and use a representative element for each cluster, hence generating a novel contracted graph that shrank in size. In many real-world cases, clusters can be identified by a set of connected vertices that share the result of some coloring function γ. For example, we can identify contiguous terrains with the same discrete property on a geographical map, leveraging Space Syntax, or we can cluster users in a social network depending on the language they speak or the political preferences they manifest. If contracted properly, generated graphs retain many properties of the original networks, including topological information on their nodes and edge distributions. This can help identify issues and characteristics of the original structures that were not visible before.
In this talk, we introduce and discuss the problem of how extracting a small representative graph G/γ from a (possibly large) colored network G by means of colored-contraction (or γ-contraction). In particular, we introduce an innovative framework called β-contraction that produces G/γ with an iterative greedy approach that is inherently parallelizable. Besides the technical details, we also present a few use cases of this approach, including its applicability to cryptocurrencies, social networks, and city planning.
References
Flavio Lombardi and Elia Onofri. Graph contraction on attribute-based coloring. Procedia Computer Science, 201:429–436, 04 2022. The 13th International Conference on Ambient Systems, Networks, and Technologies (ANT) / The 5th International Conference on Emerging Data and Industry 4.0 (EDI40).
Flavio Lombardi and Elia Onofri. Some results on colored network contraction. Journal of Ubiquitous Systems and Pervasive Networks, 17(2):91–98, 12 2022.
Elia Onofri. ML- and graph-based data analysis and prediction methods: applications in vehicular traffic, pedestrian dynamics, and computational biology. PhD thesis, Roma Tre Univ., 2023.
Brief Biography
Elia Onofri obtained his Ph.D. in mathematics in October 2023 at the University of Roma Tre (Italy) after a B.D. in mathematics and an M.D. in Computational Sciences.
Currently, he is a research fellow at the Institute for Applied Mathematics of the National Research Council of Italy (IAC-CNR) and a professor at Roma Tre University, where he teaches Cryptography and Algorithm and Data Structures.
Elia's expertise spans a wide range of fields, including graph theory, cryptography, computational biology, machine learning, and numerical simulations; this allows him to collaborate with many research groups scattered in four countries.
Despite obtaining his Ph.D., which is very recent, he has already published 10+ scientific articles, most of which are Scopus-indexed.