Parallel Maximum Clique Algorithms with Applications to Network Analysis and Storage

摘要: We 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 roughly linear runtime scaling over real-world networks ranging from 1000 100 million nodes. In test on network with 1.8 billion edges, the finds largest in about 20 minutes. Our employs branch bound strategy novel aggressive pruning techniques. For instance, we use core number vertex combination good heuristic finder efficiently remove vast majority search space. addition, parallelize exploration tree. During search, processes immediately communicate changes upper lower bounds size clique, which occasionally results super-linear speedup because vertices spaces can be pruned by other processes. apply two problems: compute temporal strong components compress graphs.