\texttt{PQser:} a Matlab package for spectral seriation
From MaRDI portal
Publication:670489
Abstract: The seriation problem is an important ordering issue which consists of finding the best ordering of a set of units whose interrelationship is defined by a bipartite graph. It has important applications in, e.g., archaeology, anthropology, psychology, and biology. This paper presents a Matlab implementation of an algorithm for spectral seriation by Atkins et al., based on the use of the Fiedler vector of the Laplacian matrix associated to the problem, which encodes the set of admissible solutions into a PQ-tree. We introduce some numerical technicalities in the original algorithm to improve its performance, and point out that the presence of a multiple Fiedler value may have a substantial influence on the computation of an approximated solution, in the presence of inconsistent data sets. Practical examples and numerical experiments show how to use the toolbox to process data sets deriving from real-world applications.
Recommendations
- The seriation problem in the presence of a double Fiedler value
- A Spectral Algorithm for Seriation and the Consecutive Ones Problem
- A generalized insertion algorithm for the seriation problem
- Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
- Seriation in combinatorial and statistical data analysis
Cites work
- scientific article; zbMATH DE number 5977361 (Why is no real title available?)
- scientific article; zbMATH DE number 3650737 (Why is no real title available?)
- scientific article; zbMATH DE number 3843553 (Why is no real title available?)
- scientific article; zbMATH DE number 4208110 (Why is no real title available?)
- scientific article; zbMATH DE number 1187154 (Why is no real title available?)
- scientific article; zbMATH DE number 3681933 (Why is no real title available?)
- scientific article; zbMATH DE number 3400822 (Why is no real title available?)
- scientific article; zbMATH DE number 3417498 (Why is no real title available?)
- A Spectral Algorithm for Seriation and the Consecutive Ones Problem
- A first course in network theory
- A spectral algorithm for envelope reduction of sparse matrices
- An optimal algorithm to recognize Robinsonian dissimilarities
- Convex relaxations for permutation problems
- Incidence matrices and interval graphs
- Incidence matrices, interval graphs and seriation in archeology
- Network properties revealed through matrix functions
- Old and new results on algebraic connectivity of graphs
- Optimal linear labelings and eigenvalues of graphs
- Recognition of Robinsonian dissimilarities
- Seriation and matrix reordering methods: An historical overview
- Similarity-first search: a new algorithm with application to Robinsonian matrix recognition
- Spectral clustering and its use in bioinformatics
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The simultaneous consecutive ones problem
Cited in
(7)- A spectral method for bipartizing a network and detecting a large anti-community
- Metaheuristic algorithms for the bandwidth reduction of large-scale matrices
- Orthogonal expansion of network functions
- PQSER
- The seriation problem in the presence of a double Fiedler value
- Seriation by constrained correspondence analysis: a simulation study
- Seriation algorithms for determining the evolution of \textit{The Star Husband Tale}
This page was built for publication: \texttt{PQser:} a Matlab package for spectral seriation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q670489)
