  Finding maximum cliques in large networks is a challenging combinatorial
problem with many real-world applications. We present a fast algorithm to
achieve the exact solution for the maximum clique problem in large sparse
networks based on efficient graph decomposition. A bunch of effective
techniques is being used to greatly prune the graph and a novel concept called
Complete-Upper-Bound-Induced Subgraph (CUBIS) is proposed to ensure that the
structures with the potential to form the maximum clique are retained in the
process of graph decomposition. Our algorithm first pre-prunes peripheral
nodes, subsequently, one or two small-scale CUBISs are constructed guided by
the core number and current maximum clique size. Bron-Kerbosch search is
performed on each CUBIS to find the maximum clique. Experiments on 50 empirical
networks with a scale of up to 20 million show the CUBIS scales are largely
independent of the original network scale. This enables an approximately linear
runtime, making our algorithm amenable for large networks. Our work provides a
new framework for effectively solving maximum clique problems on massive sparse
graphs, which not only makes the graph scale no longer the bottleneck but also
shows some light on solving other clique-related problems.
