Transfer distance between partitions. (English) Zbl 1284.05319

Summary: The comparison of partitions is a central topic in clustering, as well as when comparing partitioning algorithms or when classifying nominal variables. In this paper, we deal with the transfer distance between partitions, defined as the minimum number of transfers of one element from its class to another (possibly empty) necessary to turn one partition into the other one. After reviewing some theoretical results about this distance, we analyse its behaviour by an experimental study in order to make its interpretation easier.


05C90 Applications of graph theory
05C12 Distance in graphs
05C35 Extremal problems in graph theory
05D99 Extremal combinatorics
62G15 Nonparametric tolerance and confidence regions
62G30 Order statistics; empirical distribution functions
62H30 Classification and discrimination; cluster analysis (statistical aspects)
Full Text: DOI


[1] Barthélemy J-P (1979) Propriétés métriques des ensembles ordonnés. Comparaison et agrégation des relations binaires. PhD thesis, Université de Franche-Comté, Besançon
[2] Batagelj V, Mrvar M, Zaversnik M (1999) Partitioning approach to visualisation of large graphs. In: GD’99 Proceedings of the 7th international symposium on graph drawing, Lecture notes in computer science, vol 1731. Springer, Berlin, pp 90–97
[3] Boorman SA, Olivier DC (1973) Metrics on spaces of finite trees. J Math Psychol 10: 26–59 · Zbl 0271.92011
[4] Charon I, Denoeud L, Guénoche A, Hudry O (2006) Maximum transfer distance between partitions. J Classif 23(1): 103–121 · Zbl 1244.05023
[5] Charon I, Denoeud L, Hudry O (2007) Maximum de la distance de transfert à une partition donnée. Mathématiques et Sciences Humaines 179: 45–83 · Zbl 1180.05016
[6] Day W (1981) The complexity of computing metric distances between partitions. Math Soc Sci 1: 269–287 · Zbl 0497.62049
[7] de Frayssex H, Kuntz P (1992) Pagination of large scale networks; embedding a graph in $${\(\backslash\)mathbb{R}\^n}$$ for effective partitioning. Algorithmic Rev 2(3): 105–112
[8] Denoeud L (2006) Étude de la distance de transfert entre partitions et recherche de zones denses dans un graphe. PhD thesis, Université Paris 1, France
[9] Guénoche A (2005) Comparing recent methods in graph partitioning. Electron Notes Discrete Math 22: 83–89 · Zbl 1182.05096
[10] Hubert L, Arabie P (1985) Comparing partitions. J Classif 2: 193–218 · Zbl 0587.62128
[11] Jaccard P (1908) Nouvelle recherche sur la distribution florale. Bulletin de la Société Vaudoise des Sciences Naturelles 44: 223–270
[12] Kuhn HW (1955) The Hungarian method for the assignment problem. Naval Res Logist Q 2: 83–97
[13] Lerman IC (1988) Comparing partitions. Mathematical and statistical aspects. In: Bock HH (eds) Classification and related methods of data analysis, Elsevier, Amsterdam, pp 121–132
[14] Lovász L, Plummer MD (1986) Matching theory. Annals of discrete mathematics 29, North-Holland · Zbl 0618.05001
[15] Matsuda H, Ishihara T, Hashimoto A (1999) Classifying molecular sequences using a linkage graph with their pairwise similarities. Theor Comput Sci 210: 305–325 · Zbl 0912.68218
[16] Newman MEJ (2001) The structure of scientific collaboration networks. Proc Natl Acad Sci USA 98: 404–409 · Zbl 1065.00518
[17] Nijenhuis A, Wilf H (1978) Combinatorial algorithms. Academic Press, New York · Zbl 0476.68047
[18] Rand WM (1971) Objective criteria for the evaluation of clustering methods. J Am Stat Assoc 66: 846–850
[19] Régnier S (1965) Quelques aspects mathématiques des problèmes de classification automatique. ICC Bull 4
[20] Rota G-C (1964) The number of partitions of a set. Am Math Mon 71(5): 498–504 · Zbl 0121.01803
[21] Tijms H (2004) Understanding probability: chance rules in everyday life. Cambridge University Press, Cambridge · Zbl 1073.60001
[22] Wallace DL (1983) Comment. J Am Stat Assoc 78: 569–579
[23] Youness G, Saporta G (2004) Une méthodologie pour la comparaison des partitions. Revue de Statistique Appliquée 52(1): 97–120
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.