Searching for Maximum Quasi-bicliques

This paper is devoted to the investigation of the problem of finding the maximal quasi-bicliques in a bipartite graph. Quasi-biclique in the graph is called an almost complete subgraph. Relaxation of completeness can be understood variously; in this paper, we assume that the subgraph is a quasi-biclique if it lacks gamma * 100% of the edges to become a clique for fixed gamma. For a bigraph and a fixed gamma, the problem of finding the maximal quasi-biclique consists in finding subsets of the fractions of the graph such that the induced by these subsets subgraph is a quasi-biclique and its size is maximal for a given graph. In this graduation work, algorithms that use models of mixed integer programming (MIP) to search for a quasi-biclique are constructed and tested for working efficiency. Also, a model is tested that simultaneously maximizes both the size of the quasi-bicli and its density, using the idea of the TriBox method of triclaster generation in a triadic context narrowed to two-dimensional space. Keywords: quasi-biclique, problem of finding the maximal quasi-biclik, mixed integer programming, MIP.