On the Phase Transition of Finding a Biclique in a larger Bipartite Graph
This addresses a computational bottleneck in domains like bioinformatics and social network analysis, but it is incremental as it applies known phase transition analysis to this specific problem.
The study tackled the problem of finding a complete bipartite subgraph of specified dimensions in a larger bipartite graph, identifying an order parameter via decision tree classification and revealing an easy-to-hard-to-easy-to-hard-to-easy phase transition pattern, with hardest instances occurring where a positive answer is more likely.
We report on the phase transition of finding a complete subgraph, of specified dimensions, in a bipartite graph. Finding a complete subgraph in a bipartite graph is a problem that has growing attention in several domains, including bioinformatics, social network analysis and domain clustering. A key step for a successful phase transition study is identifying a suitable order parameter, when none is known. To this purpose, we have applied a decision tree classifier to real-world instances of this problem, in order to understand what problem features separate an instance that is hard to solve from those that is not. We have successfully identified one such order parameter and with it the phase transition of finding a complete bipartite subgraph of specified dimensions. Our phase transition study shows an easy-to-hard-to-easy-to-hard-to-easy pattern. Further, our results indicate that the hardest instances are in a region where it is more likely that the corresponding bipartite graph will have a complete subgraph of specified dimensions, a positive answer. By contrast, instances with a negative answer are more likely to appear in a region where the computational cost is negligible. This behaviour is remarkably similar for problems of a number of different sizes.