Preliminary Results on Mixed Integer Programming for Searching Maximum Quasi-Bicliques and Large Dense Biclusters

D. I. Ignatov; Ivanova P.; Zamaletdinova A.; O. Prokopyev

?

Preliminary Results on Mixed Integer Programming for Searching Maximum Quasi-Bicliques and Large Dense Biclusters

P. 28–32.

Ignatov D. I., Ivanova P., Zamaletdinova A., Prokopyev O.

This short paper is related to the problem of finding maximum quasi-bicliques in a bipartite graph (bigraph). A quasi-biclique in a bigraph is its “almost” complete subgraph; here, we assume that the subgraph is a quasi-biclique if it lacks γ · 100% of the edges to become a biclique. The problem of finding the maximal quasi-biclique(s) consists of finding subset(s) of vertices of an input bigraph such that the induced by these subsets subgraph is a quasi-biclique and its size is maximal. A model based on mixed integer programming (MIP) to search for a quasi-biclique is proposed and tested. Another its variant is tested that simultaneously maximizes both the size of the quasi-biclique and its density, using the least-square criterion similar to the one exploited by TriBox method for tricluster generation. Therefore, the output patterns can be called large dense biclusters as well.

Language: English

Full text

Text on another site

Keywords: бикластеризация трикластеризация biclustering quasi-biclique maximal quasi-biclique triclustering mixed integer programming квазибиклика максимальная квазибиклика смешанное целочисленное программирование

In book

Supplementary Proceedings ICFCA 2019 Conference and Workshops

Vol. 2378. , CEUR Workshop Proceedings, 2019.

Object-Attribute Biclustering for Elimination of Missing Genotypes in Ischemic Stroke Genome-Wide Data

Ignatov D. I., Khvorykh G., Khrunin A. et al., , in: Recent Trends in Analysis of Images, Social Networks and Texts. 9th International Conference, AIST 2020, Skolkovo, Moscow, Russia, October 15–16, 2020 Revised Supplementary ProceedingsVol. 12602.: Springer, 2021. P. 185–204.

© 2021, Springer Nature Switzerland AG.Missing genotypes can affect the efficacy of machine learning approaches to identify the risk genetic variants of common diseases and traits. The problem occurs when genotypic data are collected from different experiments with different DNA microarrays, each being characterised by its pattern of uncalled (missing) genotypes. This can prevent the ...

Added: November 1, 2022

Mixed Integer Programming for Searching Maximum Quasi-Bicliques

Ignatov D. I., Иванова П., Замалетдинова А., , in: Network Algorithms, Data Mining, and Applications. Springer Proceedings in Mathematics & StatisticsVol. 315.: Springer, 2020. Ch. 2 P. 19–35.

This paper is related to the problem of finding the maximal quasi-bicliques in a bipartite graph (bigraph). A quasi-biclique in the bigraph is its “almost” complete subgraph. The relaxation of completeness can be understood variously; here, we assume that the subgraph is a \(\gamma \)-quasi-biclique if it lacks a certain number of edges to form ...

Added: February 22, 2020

Turning Krimp into a Triclustering Technique on Sets of Attribute-Condition Pairs that Compress

Ignatov D. I., Yurov M., , in: Rough Sets - International Joint Conference, IJCRS 2017, Olsztyn, Poland, July 3-7, 2017, Proceedings, Part II.Vol. 10314.: Springer, 2017. P. 558–569.

Mining ternary relations or triadic Boolean tensors is one of the recent trends in knowledge discovery that allows one to take into account various modalities of input object-attribute data. For example, in movie databases like IMBD, an analyst may find not only movies grouped by specific genres but see their common keywords. In the so-called ...

Added: February 9, 2020

A Branch and Bound Algorithm for a Fractional 0-1 Programming Problem

Irina Utkina, Mikhail Batsyn, Ekaterina Batsyna, , in: Discrete Optimization and Operations Research/9th International Conference, DOOR 2016, Vladivostok, Russia, September 19-23, 2016, Proceedings.: Springer, 2016. P. 244–255.

We consider a fractional 0-1 programming problem arising in manufacturing. The problem consists in clustering of machines together with parts processed on these machines into manufacturing cells so that intra-cell processing of parts is maximized and inter-cell movement is minimized. This problem is called Cell Formation Problem (CFP) and it is an NP-hard optimization problem ...

Added: October 3, 2018

A branch-and-bound algorithm for the cell formation problem

Irina E. Utkina, Mikhail V. Batsyn, Ekaterina K. Batsyna, International Journal of Production Research 2018 Vol. 56 No. 9 P. 3262–3273

The Cell Formation Problem (CFP) is an important optimisation problem in manufacturing. It has been introduced in the Group Technology (GT) and its goal is to group machines and parts processed on them into production cells minimising the movement of parts to other cells for processing and maximising for each cell the loading of its ...

Added: March 11, 2018

Multimodal Clustering for Community Detection

Ignatov D. I., Semenov A., Комиссарова Д. В. et al., , in: Formal Concept Analysis of Social Networks.: Springer, 2017. Ch. 4 P. 59–96.

Multimodal clustering is an unsupervised technique for mining interesting patterns in n-ary relations or n-mode networks. Among different types of such generalised patterns one can find biclusters and formal concepts (maximal bicliques) for two-mode case, triclusters and triconcepts for three-mode case, closed n-sets for n-mode case, etc. Object-attribute biclustering (OA-biclustering) for mining large binary datatables (formal contexts or two-mode ...

Added: December 17, 2017

Алгоритм ветвей и границ для задачи о формировании производственных ячеек

Utkina I. E., Batsyn M. V., Программные продукты, системы и алгоритмы 2017 № 4 С. 1–10

The Cell Formation Problem (CFP) is an NP-hard optimization problem considered for cellular man- ufacturing systems. Because of its high computational complexity there have been developed a lot of heuristics and almost no exact algorithms for solving this problem. In this paper we suggest a branch- and-bound algorithm which provides exact solutions for the CFP ...

Added: October 18, 2017

Towards a Unified Taxonomy of Biclustering Methods

Ignatov D. I., Watson B., , in: RuZA 2015 Workshop. Proceedings of Russian and South African Workshop on Knowledge Discovery Techniques Based on Formal Concept Analysis (RuZA 2015). November 30 - December 5, 2015, Stellenbosch, South AfricaVol. 1552.: Aachen: CEUR Workshop Proceedings, 2015.

Being an unsupervised machine learning and data mining technique, biclustering and its multimodal extensions are becoming popular tools for analysing object-attribute data in different domains. Apart from conventional clustering techniques, biclustering is searching for homogeneous groups of objects while keeping their common description, e.g., in binary setting, their shared attributes. In bioinformatics, biclustering is used ...

Added: June 14, 2016