Parallel Maximum Clique Algorithms With Applications to Network Analysis and Storage
The authors propose a fast, parallel maximum clique algorithm for large sparse graphs that is designed to exploit characteristics of social and information networks. The method exhibits a roughly linear runtime scaling over real-world networks ranging from 1000 to 100 million nodes. In a test on a social network with 1.8 billion edges, the algorithm finds the largest clique in about 20 minutes. Their method employs a branch and bound strategy with novel and aggressive pruning techniques.