Consensus of partitions: a constructive approach. (English) Zbl 1253.68258

Summary: Given a profile (family) \(\Pi\) of partitions of a set of objects or items \(X\), we try to establish a consensus partition containing a maximum number of joined or separated pairs in \(X\) that are also joined or separated in the profile. To do so, we define a score function, \(S_\Pi\) associated to any partition on \(X\). Consensus partitions for \(\Pi\) are those maximizing this function. Therefore, these consensus partitions have the median property for the profile and the symmetric difference distance. This optimization problem can be solved, in certain cases, by integer linear programming. We define a polynomial heuristic which can be applied to partitions on a large set of items. In cases where an optimal solution can be computed, we show that the partitions built by this algorithm are very close to the optimum which is reached in practically all the cases, except for some sets of bipartitions.


68R05 Combinatorics in computer science
90C27 Combinatorial optimization
68W25 Approximation algorithms
Full Text: DOI


[1] Barthélemy JP, Monjardet B (1981) The median procedure in cluster analysis and social choice. Theory Math Soc Sci 1:235–268 · Zbl 0486.62057
[2] Barthélemy JP, Leclerc B (1995) The median procedure for partitions. DIMACS Ser Discret Math Theor Compu Sci 19: 3–34 · Zbl 0814.62031
[3] Brenac T (2002) Contribution des méthodes de partition centrale à la mise en evidence expérimentale de catégories cognitives. INRETS, Arcueil
[4] Celeux G, Diday E, Govaert G, Lechevalier Y, Ralambondrainy H (1989) Classification automatique des Données. Dunod, Paris
[5] Charon I, Denoeud L, Guénoche A, Hudry O (2006) Maximum transfer distance between partitions. J Classif 23(1): 103–121 · Zbl 1244.05023
[6] Day W (1981) The complexity of computing metric distances between partitions. Math Soc Sci 1: 269–287 · Zbl 0497.62049
[7] Denoeud L (2008) Transfer distance between partitions. Adv Data Anal Classif 2: 279–294 · Zbl 1284.05319
[8] Dubois D (1991) Sémantique et cognition–Catégories, prototypes et typicalité. Edition du CNRS, Paris
[9] Filkov V, Skiena S (2003) Integrating microarray data by consensus clustering. In: Proceedings of International Conference on Tools with Artificial Intelligence (ICTAI), pp 418–425
[10] Grötschel M, Wakabayashi Y (1989) A cutting plan algorithm for a clustering problem. Math Program 45: 59–96 · Zbl 0675.90072
[11] Guénoche A (2010) Bootstrap clustering for graph partitioning. MARAMI proceedings (submitted)
[12] Gusfield D (2002) Partition-distance. Inf Process Lett 82(3): 159–164 · Zbl 1013.68142
[13] Jain AK, Moreau JV (1987) Bootstrap technique in cluster analysis. Pattern Recognit 20(5): 547–568
[14] Krivanek M, Moravek J (1986) NP-hard problems in hierarchical-tree clustering. Acta Informatica 23: 311–323 · Zbl 0644.68055
[15] Leclerc B (1984) Efficient and binary consensus functions on transitively valued relations. Math Soc Sci 8: 45–61 · Zbl 0566.90003
[16] Mirkin BG (1975) On the problem of reconciling partitions. In: Quantitative Sociology. Academic Press, New York, pp 441–449
[17] Monjardet B (1990) Arrowian characterization of latticial federation consensus functions. Math Soc Sci 20: 51–71 · Zbl 0746.90002
[18] Newman ME (2004) A fast algorithm for detecting community structure in networks. Phys Rev E Stat Nonlin Soft Matter Phys 69: 066133
[19] Nijenhuis A, Wilf H (1978) Combinatorial algorithms. Academic Press, New York · Zbl 0476.68047
[20] Pinto da Costa JF, Rao PR (2004) Central partition for a partition-distance and strong pattern graph. REVSTAT 2(2): 128–143 · Zbl 1080.62046
[21] Régnier S (1965) Sur quelques aspects mathématiques des problèmes de classification automatique. Mathématiques et Sciences humaines 82:1983, 13–29 (reprint of I.C.C. bulletin 4: 1965, 175–191)
[22] Zahn CT (1964) Approximating symmetric relations by equivalence relations. SIAM J Appl Math 12: 840–847 · Zbl 0129.16003
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.