Block seriation problems: A unified approach. Reply to the problem of H. Garcia and J. M. Proth. (English) Zbl 0624.90048

Marcotorchino, F.

Appl. Stochastic Models Data Anal. 3, 73-91 (1987).

In a recent article [ibid. 1, 25-34 (1985; Zbl 0583.90044)], H. Garcia and J. M. Proth have stated the following problem: starting from a (0,1) binary matrix of size (N\(\times M)\), how to divide into independent subsets the rows of this matrix simultaneously with a one-to- one corresponding partition of the columns, maximizing the presence of 1s in the intersecting blocks with a joint minimization of the presence of 0s outside of these blocks.
The authors have proposed an efficient and very fast heuristic algorithm in comparison with the existing methods of a fast-growing literature on the subject. The only drawback of this algorithm is dependence on the initial partition. In this paper, we try to improve this algorithm slightly, first in rewriting the objective function in a linear form and secondly in giving computational improvements related to this linear formulation.

MSC:

90B35	Deterministic scheduling theory in operations research
90C10	Integer programming

Keywords:

block seriation problems; non-hierarchical clustering data aggregation; heuristic algorithm

Citations:

Zbl 0583.90044

References:

[1]	Caraux, Revue de Statistique Appliquée 32 pp 5– (1984)
[2]	and , ’Constructing blockmodels: how and why’, Journal of Mathematical Psychology, (17), 21–63 (1978). · Zbl 0375.92001
[3]	’Seriation from abundance matrices’, in (ed.), Mathematics in the Archaeological and Historical Sciences, Edimburg Press, 1971. · Zbl 0333.62036
[4]	Dagnelie, Bulletin Serv. Cartes Phytogéographiques, série B 5 pp 7– (1960)
[5]	’Traitements graphiques et mathématiques. Différence fondamentale et complémentarité’, Mathématiques et Sciences Humaines, no. 72, 60–71 (1980).
[6]	EURISTA, logiciel ďaide à ľinterprétation de données en sciences humaines’, 2ème colloque de Micro. Info. Graphique, Université de Rouen, 1982.
[7]	Tournier, La Terre et la vie 33 pp 275–
[8]	and , ’Social structure from multiple networks. I. Blockmodels of roles and positions’, American Journal of Sociology, (81), 730–790, (1976).
[9]	Elmaghraby, Naval Research Logistics Quarterly 15 pp 23– (1968) · Zbl 0159.49101
[10]	Hanan, SIAM Review 14 pp 324– (1972)
[11]	’A survey of sparse matrix research’, Proceedings of the IIE, no. 65, 500–535 (1977).
[12]	Warnesson, Journal of Applied Stochastic Models and Data Analysis 1 pp 121– (1985)
[13]	Barnes, SIAM Journal of Algorithms and Discrete Methods 3 pp 541– (1982)
[14]	’Aggrégation à la majorité I: hommage à Condorcet’, IBM Scientific Centre Technical Report no. F051, 1981.
[15]	Marcotorchino, Revue de Statistique Appliquée 30 (1981)
[16]	’Approximating symmetric relations by equivalence relations’, SIAM Journal of Applied Mathematics, (12), 840–847 (1964). · Zbl 0129.16003
[17]	and , Optimisation en Analyse Ordinale des Données, Masson, Paris, 1979.
[18]	’Agrégation des similarités’ Thèse de Doctorat ďEtat, Université Paris VI, 1981.
[19]	and , ’Clustering procedures’, in (ed.), Multivariate Analysis I, Academic Press, New-York, 1966.
[20]	et al, ’Optimisation en Classification Automatique’, Volumes I and II, INRIA, Rocquencourt, 1979.
[21]	Classification et Analyse Ordinale des Données, Dunod, Paris, 1981).
[22]	and , ’An algorithm for clustering relational data with application to social network analysis and comparison with multidimensional scaling’, Journal of Mathematical Psychology, (12), 328–383 (1975).
[23]	’Classification simultanée de tableux binaires’, in Data Analysis and Informatics III. North-Holland, Amsterdam, 1984.