Parallel Maximum Clique Algorithms with Applications to Network Analysis

摘要: We present a fast, parallel maximum clique algorithm for large sparse graphs that is designed to exploit characteristics of social and information networks. The method exhibits roughly linear runtime scaling over real-world networks ranging from thousand hundred million nodes. In test on network with 1.8 billion edges, the finds largest in about 20 minutes. At its heart employs branch-and-bound strategy novel aggressive pruning techniques. techniques include combined use core numbers vertices along good initial heuristic solution remove vast majority search space. addition, exploration tree parallelized. During search, processes immediately communicate changes upper lower bounds size clique. This exchange occasionally results superlinear speedup because tasks spaces can be pruned by other processes. de...