Modern quantitative challenges require to tackle problems on increasingly complex systems in which the relationships between the comprised entities cannot be modelled in a simple pairwise fashion, as graphs do. Such approximation of higher-order relations may lead to a substantial loss of information, hence the need to use more general models than graphs. The most natural choice is to use hypergraphs, discrete structures able to capture k-adic relationships among the entities participating in the problem, modelled as vertices, by grouping them in non-empty sets which constitute the hyperedges of the hypergraph. Since one of the most desirable abilities in this context is to quantify the difference between two such high-order systems, devising distance metrics between hypergraphs becomes of the utmost importance. In this paper, we aim at tackling precisely this problem. Motivated by our previous work on graphs, we propose two distance measures between attributed hypergraphs and we prove that they satisfy the properties of a metric. Both metrics are based on the notion of the maximal common subhypergraph. (c) 2021 Elsevier B.V. All rights reserved.

Two metrics for attributed hypergraphs

Smaniotto, S;Pelillo, M
2021-01-01

Abstract

Modern quantitative challenges require to tackle problems on increasingly complex systems in which the relationships between the comprised entities cannot be modelled in a simple pairwise fashion, as graphs do. Such approximation of higher-order relations may lead to a substantial loss of information, hence the need to use more general models than graphs. The most natural choice is to use hypergraphs, discrete structures able to capture k-adic relationships among the entities participating in the problem, modelled as vertices, by grouping them in non-empty sets which constitute the hyperedges of the hypergraph. Since one of the most desirable abilities in this context is to quantify the difference between two such high-order systems, devising distance metrics between hypergraphs becomes of the utmost importance. In this paper, we aim at tackling precisely this problem. Motivated by our previous work on graphs, we propose two distance measures between attributed hypergraphs and we prove that they satisfy the properties of a metric. Both metrics are based on the notion of the maximal common subhypergraph. (c) 2021 Elsevier B.V. All rights reserved.
File in questo prodotto:
File Dimensione Formato  
PRL 2021.pdf

non disponibili

Tipologia: Versione dell'editore
Licenza: Accesso chiuso-personale
Dimensione 526.18 kB
Formato Adobe PDF
526.18 kB Adobe PDF   Visualizza/Apri

I documenti in ARCA 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/10278/5004662
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact