Seriation is a problem consisting of seeking the best enumeration order of a set of units whose interrelationship is described by a bipartite graph. An algorithm for spectral seriation based on the use of the Fiedler vector of the Laplacian matrix associated to the problem was developed by Atkins et al. under the assumption that the Fiedler value is simple. In this paper, we analyze the case in which the Fiedler value of the Laplacian is not simple, discuss its effect on the set of the admissible solutions, and study possible approaches to actually perform the computation. Examples and numerical experiments illustrate the effectiveness of the proposed methods.

The seriation problem in the presence of a double Fiedler value

Concas A.;Fenu C.
;
Rodriguez G.;
2023-01-01

Abstract

Seriation is a problem consisting of seeking the best enumeration order of a set of units whose interrelationship is described by a bipartite graph. An algorithm for spectral seriation based on the use of the Fiedler vector of the Laplacian matrix associated to the problem was developed by Atkins et al. under the assumption that the Fiedler value is simple. In this paper, we analyze the case in which the Fiedler value of the Laplacian is not simple, discuss its effect on the set of the admissible solutions, and study possible approaches to actually perform the computation. Examples and numerical experiments illustrate the effectiveness of the proposed methods.
Bipartite graph
Fiedler vector
Seriation problem
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/11584/352825
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact