This short paper is related to the problem of nding 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 nding the maximal quasi-biclique(s) consists of nding 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.
There are many data sources that can be represented as bipartite graphs. For example, social network data, where the underlying binary relation represents interactions between people and communities, advertisement data with a set of manufacturers and corresponding set of products etc.
Copyright c 2019 for this paper by its author. Copying permitted for private and academic purposes.
In this study, we are interested in analysis of such bipartite data and search for largest dense communities, where almost all elements are connected. A situation where all elements of a community are actually involved can be described by a biclique (complete subgraph) of a bipartite graph.
Unfortunately, the community completeness requirement excludes almost complete communities frequently met in real-world data. Due to this reason we allow some edges to be absent and introduce the concept of quasi-biclique. In order to bound the size of quasi-biclique we can use the subgraph minimal density or the maximum number of absent edges needed to complete a subgraph.
The problem of searching for maximal quasi-clique as well as the problem of searching for maximal clique is NP-hard. Many algorithms that solve the problem are being developed. For instance, Pattillo et al. [1] o ered an integer programming model for searching for maximal quasi-clique but the case of bipartite graph with biclique was not studied in details. Note that quasi-bicliques and dense biclusters can be considered as relaxed versions of formal concept de nition [2, 3].
The aim of this paper is to propose a mixed integer programming models for nding a maximum quasi-bicliques in a bipartite graph and compare those models with existing ones.
The remainder of the paper is organised as follows. Section 2 proposes two MIP models for quasi-biclique search. In Section 3, we provide the preliminary experimental results. Section 4 concludes the paper. 2
Quasi-biclique searching models De nition 1. A -quasi-biclique in a bipartite graph G = (U; V; E) is its bipartite induced subgraph G[V 0; U 0] with U 0 U , V 0 V and its number of edges jE0j jV 0j jU 0j, where 2 (0; 1].
The problem of maximum quasi-biclique in a bipartite graph G(U; V; E)
with xed : 0 < 1 is to nd U 0 U and V 0 V such that vertex-induced
subgraph G[U 0; V 0] is a -quasi-biclique of size jU 0j + jV 0j, maximum for this
graph. Lets denote a maximum { quasi-biclique in the graph G by ! (G)
Model 1. Here, we adapt model F3 from [4] for searching for maximum
quasibicliques. We introduce the following variables: ui = 1 , i 2 U 0, vj = 1 , j 2
V 0, yij = 1 , 9(i; j) 2 E \ (U 0
!l(
V 0), zk(
X
n=!l(
X
n=!l(
X
n=!l(
X
m=!l(
X
m=!l(
3 ! (G) = um;va;yx;z 4X ui +
X vj 5 ;
under conditions X
yij
n m z(
As in the model F3 we can bound zk(
Remark. In Model 1, condition 2 is not linear, so we linearize it further. In the worst-case scenario for dense graphs there are jU j + jV j binary variables and jEj + jU j jV j continuous variables to be optimized.
Model 2. Let us have a look at a di erent maximizing criteria for our MIP model from [5] dedicated to triclustering generation. By narrowing this criteria to binary setting, it is possible to produce another maximising criteria for model GF3(f) from [4].
For a bipartite graph G(U; V; E) and its subgraph G[C1; C2] the function f
is maximized over the density and the size of G[C1; C2].
f (C1; C2) =
(
X (i;j)2E
1 yij A log
X ui i2U ! 0
1 j2V (9)
Without any extra bounds on vertex sets of a quasi-biclique and the minimum number of edges in it, the model has 2 (jU j + jV j + jEj) variables.
Experimental Validation The greedy algorithm of nding of maximal -quasi-bicliques in a bipartite graph was written in Python 2.7. The MIP models were implemented with the optimisation package IBM Cplex. All calculations were carried out on a laptop with the MacOs operating system, 2.7 GHz Intel Core i5 processor, RAM 8 GB 1867 MHz.
Datasets for testing the performance of the algorithms are taken from [6, 7]: 1. Divorse in US: 9 50 vertices, 225 edges; 2. Dutch Elite: 3810 937 vertices, 5221 edges; 3. Dutch Elite (TOP-200): 200 395 vertices, 877 edges; 4. Movie-Lens (ml-latest-small): 9125 20 vertices, 20340 edges.
The results of applying the algorithms are presented in the Table 1 for = 0:6. For each algorithm the main parameters are indicated: the algorithm running time (time)4, the number of founded maximum quasi-bicliques (count) and the maximum size of the founded solution.
If one of the maximal quasi-biclique components has cardinality 1, this is marked in the table as (U 0; V 0), where U 0 and V 0 are the sizes of the fractions. One can note, that MIP models work an order of magnitude slower than the [8] algorithm, but they nd more quasi-cliques and generally each has larger size.
If we consider the results not in terms of speed, but in terms of quality, then Model 2 on the examples of data worked best. This model produced more unique and larger quasi-bicliques than other algorithms (however, only sizes of the maximum quasi-bicliques are mentioned in the tables). 4 Dashes ("-") in the following tables mean that the algorithm worked too long and did not nd a solution. Acknowledgement. The work of Dmitry Ignatov shown in all the sections has been supported by the Russian Science Foundation grant no. 17-11-01276 and performed at St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences, Russia.