Abstract
We present an algorithm for fitting general graphs to proximity data. The algorithm utilizes a mathematical programming procedure based on a penalty function approach to impose additivity constraints upon parameters. For a user-specified number of links, the algorithm seeks to provide the connected network that gives the least-squares approximation to the proximity data with the specified number of links, allowing for linear transformations of the data. The network distance is the minimum-path-length metric for connected graphs. As a limiting case, the algorithm provides a tree where each node corresponds to an object, if the number of links is set equal to the number of objects minus one. A Monte Carlo investigation indicates that the resulting networks tend to fall within one percentage point of the least-squares solution in terms of the variance accounted for, but do not always attain this global optimum. The network model is discussed in relation to ordinal network representations (Klauer 1989) and NETSCAL (Hutchinson 1989), and applied to several well-known data sets.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
ARABIE, P., and CARROLL, J. D. (1980), “MAPCLUS: A Mathematical Programming Approach to Fitting the ADCLUS Model,”Psychometrika, 45, 211–235.
ARABIE, P., CARROLL, J. D., and DESARBO, W. S. (1987),Three-way Scaling and Clustering, Newbury Park, California: Sage.
BORG, I., and LEUTNER, D. (1983), “Dimensional Models for the Perception of Rectangles,”Perception and Psychophysics, 34, 257–267.
CARROLL, J. D. (1976), “Spatial, Non-spatial and Hybrid Models for Scaling,”Psychometrika, 41, 439–463.
CARROLL, J. D., and CHANG, J.J. (1973), “A Method for Fitting a Class of Hierarchical Tree Structure Models to Dissimilarities Data and Its Applications to Some “Body Parts” Data of Miller's,” inProceedings of the 81st Annual Convention of the American Psychological Association, 8, 1097–1098.
CARROLL, J. D., CLARK, L. A., and DESARBO, W. S. (1984), “The Representation of Three-way Proximities Data by Single and Multiple Tree Structure Models,”Journal of Classification, 1, 25–74.
CARROLL, J. D., and PRUZANSKY, S. (1980), “Discrete and Hybrid Scaling Models,” inSimilarity and Choice, eds., E. D. Lantermann and H. Feger, Bern: Hans Huber, 108–139.
CORTER, J. E., and TVERSKY, A. (1986), “Extended Similarity Trees,”Psychometrika, 51, 257–283.
CUNNINGHAM, J. P. (1978), “Free Trees and Bidirectional Trees as Representations of Psychological Distance,”Journal of Mathematical Psychology, 17, 165–188.
CUNNINGHAM, J. P., and SHEPARD, R. N. (1974), “Monotone Mapping of Similarities into a General Metric Space,”Journal of Mathematical Psychology, 11, 335–363.
DESOETE, G. (1983), “A Least Squares Algorithm for Fitting Additive Trees to Proximity Data,”Psychometrika, 48, 621–626.
FEGER, H., and BIEN, W. (1982), “Network Unfolding,”Social Networks, 4, 257–283.
FEGER, H., and DROGE, U. (1984), “Ordinale Netzwerkskalierung [Ordinal network scaling],”Kölner Zeitschrift für Soziologie und Sozialpsychologie, 3, 417–423.
FOX, P. A., HALL, A. D., and SCHRYER, N. L. (1978), “The PORT Mathematical Subroutine Library,”ACM Transactions on Mathematical Software, 4, 104–126.
HUTCHINSON, J. W. (1989), “NETSCAL: A Network Scaling Algorithm for Nonsymmetric Proximity Data,”Psychometrika, 54, 25–52.
JOHNSON, S. C. (1967), “Hierarchical Clustering Schemes,”Psychometrika, 32, 241–254.
KLAUER, K. C. (1989), “Ordinal Network Representation: Representing Proximities by Graphs,”Psychometrika (in press).
ORTH, B. (1988), “Representing Similarities by Distance Graphs: Monotonic Network Analysis (MONA),” inClassification and Related Methods of Data Analysis, ed., H. H. Bock, Amsterdam: North-Holland, 489–494.
POWELL, M. J. D. (1977), “Restart Procedures for the Conjugate Gradient Method,”Mathematical Programming, 12, 241–254.
RESTLE, F. (1959), “A Metric and an Ordering on Sets,”Psychometrika, 24, 207–220.
ROSENBERG, S., and KIM, M. P. (1975), “The Method of Sorting as a Data-gathering Procedure in Multivariate Research,”Multivariate Behavior Research, 10, 489–502.
RYAN, D. M. (1974), “Penalty and Barrier Functions,” inNumerical Methods for Constrained Optimization, eds., P. E. Gill and W. Murray, New York: Academic Press, 175–190.
SATTATH, S., and TVERSKY, A. (1977), “Additive Similarity Trees,”Psychometrika, 42, 319–345.
SHEPARD, R. N., and ARABIE, P. (1979), “Additive Clustering: Representation of Similarities as Combinations of Discrete Overlapping Properties,”Psychological Review, 86, 87–123.
TVERSKY, A. (1977), “Features of Similarity,”Psychological Review, 84, 327–352.
TVERSKY, A., and GATI, I. (1982), “Similarity, Separability, and the Triangle Inequality,”Psychological Review, 89, 123–154.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Klauer, K.C., Carroll, J.D. A mathematical programming approach to fitting general graphs. Journal of Classification 6, 247–270 (1989). https://doi.org/10.1007/BF01908602
Issue Date:
DOI: https://doi.org/10.1007/BF01908602