Multidimensional scaling and threshold graphs |
| |
| Affiliation: | 1. Department of Mathematics, Northeastern University USA;2. Department of Psychology, Harvard University USA;1. Department of Economics and Business, University of Catania, Italy;2. Department of Mathematics and Statistics, York University, Toronto, Canada;1. Department of Economics, Wagner College, and Center for International Policy Studies, Fordham University, NY, USA;2. Department of Economics, Monash Business School, Monash University, Australia;3. Department of Economics and Center for International Policy Studies, Fordham University, NY, USA;4. Population Studies Center, University of Pennsylvania, PA, USA;5. IZA, Bonn, Germany;1. Department of Mathematics, State University of New York at Buffalo, Buffalo, NY 14260-2900, USA;2. Computational and Data-Enabled Science and Engineering Program, State University of New York at Buffalo, Buffalo, NY 14260-5030, USA;3. Faculty of Science and Engineering, Waseda University, Tokyo 169-8555, Japan;1. Department of Economics, Georg-August-Universität, Göttingen, Germany;2. Department of Economics and Management, University of Pisa, Italy |
| |
| Abstract: | A set of data has a Guttman scale if and only if a corresponding graph is a threshold graph. In this paper we relate the concepts of disjunctive and conjuctive Guttman scales, and biorder dimension to the threshold dimension of a graph. For those graphical properties that can be tested in polynomial time, the comparable Guttman scaling techniques can be performed in polynomial time. Fast algorithms are provided for computing a Guttman scale, and the conjunctive and disjunctive dimension of data with no 3-crowns. We define an extended Guttman scale to indicate strength of agreement, dominance, etc., and show that this, too, exists if and only if a particular graph is a threshold graph. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
