Mixed Integer Programming for Searching Maximum Quasi-Bicliques

DOI10.1007/978-3-030-37157-9_2MaRDI QIDQ3294898zbMATH OpenOpenAlexFDO

Authors Dmitry I. Ignatov, Polina Ivanova, Albina Zamaletdinova

Publication date 29 June 2020

Published in Springer Proceedings in Mathematics & Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2002.09880

zbMATH Keywords

biclusteringmaximal quasi-bicliquemixed integer programmingquasi-bicliquetriclustering

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Integer programming (90C10)

Abstract: 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 a biclique such that its density is at least $gammain(0,1]$. For a bigraph and fixed $gamma$, the problem of searching for the maximal quasi-biclique consists of finding a subset of vertices of the bigraph such that the induced subgraph is a quasi-biclique and its size is maximal for a given graph. Several models based on Mixed Integer Programming (MIP) to search for a quasi-biclique are proposed and tested for working efficiency. An alternative model inspired by biclustering is formulated and tested; this model simultaneously maximizes both the size of the quasi-biclique and its density, using the least-square criterion similar to the one exploited by triclustering extsc{TriBox}.

Recommendations

• Near optimal solutions for maximum quasi-bicliques
• Near optimal solutions for maximum quasi-bicliques
• A branch-and-bound approach for maximum quasi-cliques
• Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs
• Solving the maximum vertex weight clique problem via binary quadratic programming
• An exact algorithm for the maximum quasi‐clique problem
• On the maximum quasi-clique problem
• LP-based dual bounds for the maximum quasi-clique problem
• Algorithms for induced biclique optimization problems
• scientific article; zbMATH DE number 956840

Cites work

• Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs
• Factorizing Boolean matrices using formal concepts and iterative usage of essential entries
• scientific article; zbMATH DE number 2086259 (Why is no real title available?)
• Mining a New Fault-Tolerant Pattern Type as an Alternative to Formal Concept Discovery
• Near optimal solutions for maximum quasi-bicliques
• On the maximum quasi-clique problem
• Quasi-bicliques: Complexity and Binding Pairs
• The maximum edge biclique problem is NP-complete
• Triadic formal concept analysis and triclustering: searching for optimal patterns

Cited in

(4)

• A VNS approach for book marketing campaigns generated with quasi-bicliques probabilities
• Near optimal solutions for maximum quasi-bicliques
• Quasi-bicliques: Complexity and Binding Pairs
• Near optimal solutions for maximum quasi-bicliques

Describes a project that uses

Uses Software

• Pajek
• MovieLens

This page was built for publication: Mixed Integer Programming for Searching Maximum Quasi-Bicliques

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3294898)