Graph structures 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. In many real-world cases, clusters can be identified by a set of connected vertices that share the result of some categorical function, i.e. a mapping of the vertices into some categorical representation that takes values in a finite set C. As an example, we can identify contiguous terrains with the same discrete property on a geographical map, leveraging Space Syntax. In this case, thematic areas within cities are labelled with different colors and color zones are analysed by means of their structure and their mutual interactions. Contracted graphs can help identify issues and characteristics of the original structures that were not visible before. This paper introduces and discusses the problem of contracting possibly large colored graphs into much smaller representatives. It also provides a novel serial but parallelizable algorithm to tackle this task. Some initial performance plots are given and discussed together with hints for future development.

Lombardi, F., Onofri, E. (2022). Graph Contraction on Attribute-Based Coloring. In The 13th International Conference on Ambient Systems, Networks and Technologies (ANT) / The 5th International Conference on Emerging Data and Industry 4.0 (EDI40) (pp.429-436) [10.1016/j.procs.2022.03.056].

Graph Contraction on Attribute-Based Coloring

Lombardi F.;Onofri E.
2022

Abstract

Graph structures 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. In many real-world cases, clusters can be identified by a set of connected vertices that share the result of some categorical function, i.e. a mapping of the vertices into some categorical representation that takes values in a finite set C. As an example, we can identify contiguous terrains with the same discrete property on a geographical map, leveraging Space Syntax. In this case, thematic areas within cities are labelled with different colors and color zones are analysed by means of their structure and their mutual interactions. Contracted graphs can help identify issues and characteristics of the original structures that were not visible before. This paper introduces and discusses the problem of contracting possibly large colored graphs into much smaller representatives. It also provides a novel serial but parallelizable algorithm to tackle this task. Some initial performance plots are given and discussed together with hints for future development.
Lombardi, F., Onofri, E. (2022). Graph Contraction on Attribute-Based Coloring. In The 13th International Conference on Ambient Systems, Networks and Technologies (ANT) / The 5th International Conference on Emerging Data and Industry 4.0 (EDI40) (pp.429-436) [10.1016/j.procs.2022.03.056].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/421671
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact