\texttt{PQser:} a Matlab package for spectral seriation

DOI10.1007/S11075-018-0510-6zbMATH Open1409.65117arXiv1711.05677OpenAlexW2964266046WikidataQ130103620 ScholiaQ130103620MaRDI QIDQ670489FDOQ670489

Authors: Anna Concas, C. Fenu, G. Rodriguez 

Publication date: 18 March 2019

Published in: Numerical Algorithms (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1711.05677

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

zbMATH Keywords

seriationbipartite graphsPQ-treesbandwidth reductionFiedler value

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational methods for sparse matrices (65F50) Packaged methods for numerical algorithms (65Y15) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Cites Work

• Network properties revealed through matrix functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Recognition of Robinsonian dissimilarities
• Incidence matrices and interval graphs
• Incidence matrices, interval graphs and seriation in archeology
• An optimal algorithm to recognize Robinsonian dissimilarities
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• Title not available (Why is that?)
• Old and new results on algebraic connectivity of graphs
• Optimal linear labelings and eigenvalues of graphs
• Spectral clustering and its use in bioinformatics
• Title not available (Why is that?)
• Title not available (Why is that?)
• A spectral algorithm for envelope reduction of sparse matrices
• Seriation and matrix reordering methods: An historical overview
• A Lex-BFS-based recognition algorithm for Robinsonian matrices
• Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition
• The simultaneous consecutive ones problem
• Convex Relaxations for Permutation Problems
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (6)

• 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

Uses Software

• Matlab
• seriation
• PermutMatrix

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)