Some applications of graph theory to clustering. (English) Zbl 0317.62079


62P15 Applications of statistics to psychology
62H30 Classification and discrimination; cluster analysis (statistical aspects)
05C99 Graph theory
Full Text: DOI


[1] Abraham, C. T. Techniques for thesaurus organization and evaluation. In M. Kochen (ed.),Some problems in information science. New York: The Scarecrow Press, 1965, 131–150. (a)
[2] Abraham, C. T. Graph theoretic techniques for the organization of linked data. In M. Kochen (ed.),Some problems in information science. New York: The Scarecrow Press, 1965, 229–264. (b)
[3] Anderson, S. S.Graph theory and finite combinatorics. Chicago: Markham, 1970.
[4] Augustson, J. C. and Minker, J. An analysis of some graph theoretical cluster techniques.Journal of the Association for Computing Machinery, 1970,17, 571–588. (a) · Zbl 0206.17701
[5] Augustson, J. C. and Minker, J. Deriving term relations for a corpus by graph theoretical clusters.Journal of the American Society for Information Science, 1970,21, 101–111. (b) · Zbl 0206.17701 · doi:10.1002/asi.4630210202
[6] Bohisud, H. M. and Bohisud, L. E. A metric for classifications.Taxon, 1972,21, 607–613. · doi:10.2307/1219158
[7] Bonner, R. E. On some clustering techniques.IBM Journal, 1964,8, 22–32. · Zbl 0116.09705 · doi:10.1147/rd.81.0022
[8] Boorman, S. A. and Arabie, P. Structural measures and the method of sorting. In R. N. Shepard, A. K. Romney and S. B. Nerlove (eds.),Multidimensional scaling–Volume I. New York: Seminar Press, 1972, 225–249.
[9] Boorman, S. A. and Olivier, D. C. Metrics on spaces of finite trees.Journal of Mathematical Psychology, 1973,10, 26–59. · Zbl 0271.92011 · doi:10.1016/0022-2496(73)90003-5
[10] Busacker, R. G. and Saaty, T. L.Finite graphs and networks. New York: McGraw-Hill, 1965. · Zbl 0146.20104
[11] Cattell, R. B. and Coulter, M. A. Principles of behavioral taxonomy and the mathematical basis of the taxonome computer program.The British Journal of Mathematical and Statistical Psychology, 1966,19, 237–269.
[12] Chabot, J. A simplified example of the use of matrix multiplication for the analysis of sociometric data.Sociometry, 1950,13, 131–140. · doi:10.2307/2784939
[13] Clark, J. A. and McQuitty, L. L. Some problems and elaborations of interactive intercolumnar correlational analysis.Educational and Psychological Measurement, 1970,30, 773–784. · doi:10.1177/001316447003000401
[14] Cole, A. J. and Wishart, D. An improved algorithm for the Jardine-Sibson method of generating overlapping clusters.The Computer Journal, 1970,13, 156–163. · Zbl 0191.18405 · doi:10.1093/comjnl/13.2.156
[15] Constantinescu, P. The classification of a set of elements with respect to a set of properties.The Computer Journal, 1966,8, 352–357. · Zbl 0137.34904
[16] Constantinescu, P. A method of cluster analysis.The British Journal of Mathematical and Statistical Psychology, 1967,20, 93–106.
[17] Cormack, R. M. A review of classification.Journal of the Royal Statistical Society–Series A, 1971,134, 321–367. · doi:10.2307/2344237
[18] Doreian, P. A note on the detection of cliques in valued graphs.Sociometry, 1969,32, 237–242. · doi:10.2307/2786266
[19] Erdös, P. and Rényi, A. On the evolution of random graphs.Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 1960,5, 17–61. · Zbl 0103.16301
[20] Estabrook, G. F. A mathematical model in graph theory for biological classification.Journal of Theoretical Biology, 1966,12, 297–310. · doi:10.1016/0022-5193(66)90144-5
[21] Festinger, L. The analysis of sociograms using matrix algebra.Human Relations, 1949,2, 153–158. · doi:10.1177/001872674900200205
[22] Fillenbaum, S. and Rapoport, A.Structures in the subjective lexicon. New York: Academic Press, 1971.
[23] Ford, L. R. and Fulkerson, D. R.Flows in networks. Princeton: Princeton University Press, 1962. · Zbl 0106.34802
[24] Gorinshteyn, L. L. The partitioning of graphs.Engineering Cybernetics, 1969,1, 76–82.
[25] Gotlieb, C. C. and Kumar, S. Semantic clustering of index terms.Journal of the Association for Computing Machinery, 1968,15, 493–513.
[26] Gower, J. C. Comparison of some methods of cluster analysis.Biometrics, 1967,23, 623–637. · doi:10.2307/2528417
[27] Gower, J. C. and Ross, G. J. S. Minimum spanning trees and single linkage cluster analysis.Applied Statistics, 1969,18, 54–64. · doi:10.2307/2346439
[28] Harary, F. A graph theoretic approach to similarity relations.Psychometrika, 1964,29, 143–151. · Zbl 0132.40502 · doi:10.1007/BF02289696
[29] Harary, F.Graph theory. Reading, Mass.: Addison-Wesley, 1969.
[30] Harary, F. Graph theory as a structural model in the social sciences. In B. Harris (ed.),Graph theory and its applications. New York: Academic Press, 1970, 1–16.
[31] Harary, F., Norman, R. Z. and Cartwright, D.Structural models: An introduction to the theory of directed graphs. New York: Wiley, 1965. · Zbl 0139.41503
[32] Harary, F. and Ross, I. C. A procedure for clique detection using the group matrix.Sociometry, 1957,20, 205–215. · doi:10.2307/2785673
[33] Harrison, I. Cluster analysis.Metra, 1968,7, 513–528.
[34] Hartigan, J. A. Representation of similarity matrices by trees.Journal of the American Statistical Association, 1967,62, 1140–1158. · doi:10.2307/2283766
[35] Hubert, L. Some extensions of Johnson’s hierarchical clustering algorithms.Psychometrika, 1972,37, 261–274. · Zbl 0239.92014 · doi:10.1007/BF02306783
[36] Hubert, L. Monotone invariant clustering procedures.Psychometrika, 1973,38, 47–62. (a) · Zbl 0251.92013 · doi:10.1007/BF02291173
[37] Hubert, L. Min and max hierarchical clustering using asymmetric similarity measures.Psychometrika, 1973.38, 63–72. (b) · Zbl 0251.92014 · doi:10.1007/BF02291174
[38] Hubert, L. Approximate evaluation techniques for the single-link and complete-link hierarchical clustering procedures.Journal of the American Statistical Association, 1974,69, in press. (a) · Zbl 0291.62071
[39] Hubert, L. Spanning trees and aspects of clustering.British Journal of Mathematical and Statistical Psychology, 1974, in press. (b) · Zbl 0288.92024
[40] Hubert, L. and Schultz, J. The approximate sampling distribution for the minimum number of lines in a connected random graph.Journal of Statistical Computation and Simulation, 1974, in press.
[41] Jardine, N. Towards a general theory of clustering.Biometrics, 1969,25, 609–610.
[42] Jardine, N. Algorithms, methods and models in the simplification of complex data.The Computer Journal, 1970,13, 116–117. · doi:10.1093/comjnl/13.1.116
[43] Jardine, N. A new approach to pattern recognition.Nature, 1971,234, 526–528. · doi:10.1038/234526a0
[44] Jardine, N. and Sibson, R. A model for taxonomy.Mathematical Biosciences, 1968,2, 465–482. (a) · doi:10.1016/0025-5564(68)90030-8
[45] Jardine, N. and Sibson, R. The construction of hierarchic and non-hierarchic classifications.The Computer Journal, 1968,11, 177–184. (b) · Zbl 0164.46207
[46] Jardine, N. and Sibson, R.Mathematical taxonomy. New York: Wiley, 1971.
[47] Johnson, S. C. Hierarchical clustering schemes.Psychometrika, 1957,32, 241–254. · Zbl 1367.62191 · doi:10.1007/BF02289588
[48] Kruskal, J. B. On the shortest spanning subtree of a graph and the traveling salesman problem.Proceedings of the American Mathematical Society, 1956,7, 48–50. · Zbl 0070.18404 · doi:10.1090/S0002-9939-1956-0078686-7
[49] Lance, G. N. and Williams, W. T. A general theory of classifactory sorting strategies I. Hierarchical systems.The Computer Journal, 1967.10, 373–380. (a) · doi:10.1093/comjnl/10.3.271
[50] Lance, G. N. and Williams, W. T. A general theory of classifactory sorting strategies II. Clustering systems.The Computer Journal, 1967,10, 271–277. (b) · doi:10.1093/comjnl/10.3.271
[51] Legendre, P. and Rogers, D. J. Characters and clustering in taxonomy: A synthesis of two taximetric procedures.Taxon, 1972,21, 567–606. · doi:10.2307/1219157
[52] Lerman, I. C.Les bases de la classification automatique. Paris: Gauthier-Villars, 1970. · Zbl 0199.51402
[53] Levandowsky, M. and Winter, D. Distance between sets.Nature, 1971,234, 34–35. · doi:10.1038/234034a0
[54] Ling, R. F. On the theory and construction of k-clusters.The Computer Journal, 1972,15, 326–332. · Zbl 0248.68013 · doi:10.1093/comjnl/15.4.326
[55] Ling, R. F. A probability theory of cluster analysis.Journal of the American Statistical Association, 1973,68, 159–164. · Zbl 0285.62035 · doi:10.2307/2284161
[56] Luce, R. D. Connectivity and generalized cliques in sociometric group structure.Psychometrika, 1950,15, 169–190. · doi:10.1007/BF02289199
[57] Luce, R. D. Two decomposition theorems for a class of finite oriented graphs.American Journal of Mathematics, 1952,74, 701–722. · Zbl 0046.16902 · doi:10.2307/2372274
[58] Luce, R. D. Networks satisfying minimality conditions.American Journal of Mathematics, 1953,75, 825–838. · Zbl 0051.14703 · doi:10.2307/2372551
[59] Luce, R. D. and Perry, A. D. A method of matrix analysis of group structure.Psychometrika, 1949,14, 95–116. · doi:10.1007/BF02289146
[60] Marshall, C. W.Applied graph theory. New York: Wiley, 1971. · Zbl 0226.05101
[61] Matula, D. W. Cluster analysis via graph theoretic techniques. In R. C. Mullin, K. B. Reid, and D. P. Roselle (Eds.),Proceedings of the Louisiana Conference on combinatorics, graph theory, and computing. Winnipeg: University of Manitoba, 1970, 199–212. · Zbl 0222.05125
[62] Matula, D. W.k-components, clusters and slicings in graphs.SIAM Journal of Applied Mathematics, 1972,22, 459–480. · Zbl 0243.05111 · doi:10.1137/0122040
[63] Matula, D. W., Marble, G. and Isaacson, J. D. Graph coloring algorithms. In R. C. Read (Ed.),Graph theory and computing. New York: Academic Press, 1972, 109–122. · Zbl 0256.05108
[64] Menger, K. Zur allgemeinen Kurventheorie.Fundamenta Mathematicae, 1927,10, 96–115.
[65] McQuitty, L. L. Elementary linkage analysis for isolating orthogonal and oblique types and typal relevancies.Educational and Psychological Measurement, 1957,17, 207–229. · doi:10.1177/001316445701700204
[66] McQuitty, L. L. Typal analysis.Educational and Psychological Measurement, 1961,21, 677–697. (a)
[67] McQuitty, L. L. Elementary factor analysis.Psychological Reports, 1961,9, 71–78. (b) · doi:10.2466/PR0.9.5.71-78
[68] McQuitty, L. L. Rank order typal analysis.Educational and Psychological Measurement, 1963,23, 55–61. · doi:10.1177/001316446302300105
[69] McQuitty, L. L. Capabilities and improvements of linkage analysis as a clustering method.Educational and Psychological Measurement, 1964,24, 441–456. · doi:10.1177/001316446402400301
[70] McQuitty, L. L. A mutual development of some typological theories and pattern-analytic methods.Educational and Psychological Measurement, 1967,27, 21–48. · doi:10.1177/001316446702700103
[71] McQuitty, L. L. and Clark, J. A. Clusters from iterative intercolumnar correlational analysis.Educational and Psychological Measurement, 1968,28, 211–238. · doi:10.1177/001316446802800201
[72] Mulligan, G. C. and Corneil, D. G. Corrections to Bierstone’s algorithm for generating cliques.Journal of the Association for Computing Machinery, 1972,19, 244–247. · Zbl 0247.68010
[73] Needham, R. M.The theory of Clumps II. Report Number 139, Cambridge Language Research Unit, Cambridge, England, 1961.
[74] Ogilvie, J. C. The distribution of number and size of connected components in random graphs of medium size. In A. J. H. Morrell (Ed.),Information processing: 68. Amsterdam: North Holland Publishing Co., 1969, 1527–1530.
[75] Ore, O.Theory of graphs. Providence: American Mathematical Society, 1962. · Zbl 0105.35401
[76] Ore, O.Graphs and their use. New York: Random House, 1963. · Zbl 0122.41802
[77] Overall, J. E. A configural analysis of psychiatric diagnostic stereotypes.Behavioral Science, 1963,8, 211–219. · doi:10.1002/bs.3830080306
[78] Overall, J. E. and Klett, C. J.Applied multivariate analysis. New York: McGraw-Hill, 1972. · Zbl 0504.62044
[79] Parker-Rhodes, A. F.Contributions to the theory of clumps: The usefulness and feasibility of the theory. Report Number 137, Cambridge Language Research Unit, Cambridge, England, 1961.
[80] Parker-Rhodes, A. F. and Needham, R. M.The theory of clumps. Report Number 126, Cambridge Language Research Unit, Cambridge, England, 1961.
[81] Peay, E. R.An interactive clique detection procedure. Michigan Mathematical Psychology Program, 70–74, Ann Arbor, Michigan, 1970(a).
[82] Peay, E. R.Nonmetric grouping: Clusters and cliques. Michigan Mathematical Psychology Program, 70–75, Ann Arbor, Michigan, 1970(b).
[83] Prim, R. C. Shortest connection networks and some generalizations.Bell System Technical Journal, 1957,36, 1389–1401.
[84] Restle, F. A metric and an ordering on sets.Psychometrika, 1959,24, 207–219. · Zbl 0087.15903 · doi:10.1007/BF02289843
[85] Rose, M. J. Classification of a set of elements.The Computer Journal, 1964,7, 208–210. · Zbl 0233.68030 · doi:10.1093/comjnl/7.3.208
[86] Ross, G. J. S. Classification techniques for large sets of data. In A. J. Cole (Ed.),Numerical taxonomy. New York: Academic Press, 1969, 224–233.
[87] Ross, I. C. and Harary, F. On the determination of redundancies in sociometric chains.Psychometrika, 1952,17, 195–208. · Zbl 0049.37803 · doi:10.1007/BF02288782
[88] Ross, I. C. and Harary, F. Identification of the liaison persons of an organization using the structure matrix.Management Science, 1955,1, 251–258. · Zbl 0995.90583 · doi:10.1287/mnsc.1.3-4.251
[89] Ross, I. C. and Harary, F. A description of strenghtening and weakening group members.Sociometry, 1959,22, 139–147. · doi:10.2307/2786017
[90] Roy, D. An algorithm for a general constrained set covering problem. In R. C. Read (Ed.),Graph theory and computing. New York: Academic Press, 1972, 267–283.
[91] Schultz, J. and Hubert, L. Data analysis and the connectivity of random graphs.Journal of Mathematical Psychology, 1973,10, 421–428. · Zbl 0353.62031 · doi:10.1016/0022-2496(73)90025-4
[92] Shepard, R. N. A taxonomy of some principal types of data and of multidimensional methods for their analysis. In R. N. Shepard, A. K. Romney and S. B. Nerlove (Eds.),Multidimensional scaling-Volume I. New York: Seminar Press, 1972, 21–47.
[93] Shepherd, M. J. and Willmott, A. J. Cluster analysis on the Atlas computer.The Computer Journal, 1968,11, 56–62. · doi:10.1093/comjnl/11.1.57
[94] Sibson, R. Some observations on a paper by Lance and Williams.The Computer Journal, 1971,14, 156–157. · Zbl 0227.68049 · doi:10.1093/comjnl/14.2.156
[95] Sparck-Jones, K.Automatic keyword classification for information retrieval. London: Butterworths, 1971.
[96] Tryon, R. C. and Bailey, D. E. The BCTRY computer system of cluster and factor analysis.Multivariate Behavioral Research, 1966,1, 95–111. · doi:10.1207/s15327906mbr0101_6
[97] Tutte, W. T.The connectivity of graphs. Toronto: Toronto University Press, 1967. · Zbl 0152.41202
[98] Van Rijsbergen, C. J. A clustering algorithm.The Computer Journal, 1970,13, 113–115.
[99] Vaswani, P. K. T. A technique for cluster emphasis and its application to automatic indexing. In A. J. H. Morrell (Ed.),Information processing: 68. Amsterdam: North Holland Publishing Co., 1969, 1300–1303.
[100] Weiss, R. S. and Jacobson, E. A method for the analysis of the structure of complex organizations.American Sociological Review, 1955,20, 661–668. · doi:10.2307/2088670
[101] Whitney, H. Congruent graphs and the connectivity of graphs.American Journal of Mathematics, 1932,54, 150–168. · doi:10.2307/2371086
[102] Williams, W. T., Lance, G. N., Dale, M. B. and Clifford, H. T. Controversy concerning the criteria for taxonometric strategies.The Computer Journal, 1971,14, 162–165. · Zbl 0234.68041 · doi:10.1093/comjnl/14.2.162
[103] Wirth, M., Estabrook, G. F. and Rogers, D. J. A graph theory model for systematic biology, with an example for the Oncidiinae (Orchidaceae).Systematic Zoology, 1966,15, 59–69. · doi:10.2307/2411503
[104] Wishart, D. A generalization of nearest neighbor which reduces chaining effects. In A. J. Cole (Ed.),Numerical taxonomy. New York: Academic Press, 1969, 282–311.
[105] Zahn, C. T. Graph-theoretical methods for detecting and describing Gestalt clusters.IEEE Transactions on Computers, 1971,C-20, 68–86. · Zbl 0264.68040 · doi:10.1109/T-C.1971.223083
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.