The excellent performance reported by BBMCSP—an exact maximum clique algorithm tailored for massive real networks— in a previous post has raised a number of comments, some even questioning either the report itself or the problem’s complexity. This post gives an insight on how BBMCSP works. In the process, and similar to what happens when magicians explain their tricks, we are aware that some of the magic will be lost.
In a previous post we introduced the maximum clique problem (MCP) and reported performance of the efficient bit-parallel exact solver BBMC, implemented with BITSCAN and GRAPH libraries available in the Biicode repositories pablodev/bitscan and pablodev/graph respectively. BBMC is concerned with small and middle size graphs.
Also very challenging are real networks that arise from different fields such as social networks, infrastructure networks, scientific networks and so on. These graphs tend to have many thousands—even millions— of nodes but are usually very sparse —the Network Data Repository hosts more than 500 of such graphs—. An open problem is finding the clique number (the cardinality of a maximum clique) of such networks to get an insight into their structure. Unfortunately the problem is NP-hard and no polynomial algorithm is expected to be found; tailoring and exact solver for this task is as yet an open question .
The maximum clique problem (MCP) consists in finding in a graph a clique—i.e., a complete subgraph, one such all vertices are pairwise adjacent— of maximum cardinality. The term *clique* has its roots in the social sciences; in a social network, a clique refers to a group of individuals who all know—or are linked together by some relation such as friendship— each other. The first algorithm for the MCP can be traced back to Harary & Ross in the late 50s. The first modern enumerative algorithm is most probably the one from Bron & Kerbosch in the early 70s.