Scale Reduction Techniques for Computing Maximum Induced Bicliques Academic Article uri icon

abstract

  • © 2017 by the authors. Given a simple, undirected graph G, a biclique is a subset of vertices inducing a complete bipartite subgraph in G. In this paper, we consider two associated optimization problems, the maximum biclique problem, which asks for a biclique of the maximum cardinality in the graph, and the maximum edge biclique problem, aiming to find a biclique with the maximum number of edges in the graph. These NP-hard problems find applications in biclustering-type tasks arising in complex network analysis. Real-life instances of these problems often involve massive, but sparse networks. We develop exact approaches for detecting optimal bicliques in large-scale graphs that combine effective scale reduction techniques with integer programming methodology. Results of computational experiments with numerous real-life network instances demonstrate the performance of the proposed approach.

author list (cited authors)

  • Shahinpour, S., Shirvani, S., Ertem, Z., & Butenko, S.

citation count

  • 2

publication date

  • October 2017