.png){kind=icon}
.png){kind=icon}
Return
PARALLEL MAXIMUM CLIQUE ALGORITHMS WITH APPLICATIONS TO NETWORK ANALYSIS
.png){kind=icon}
PRE
AI
DOI：10.1137/14100018X.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 a roughly linear runtime scaling over real-world networks ranging from a thousand to a hundred million nodes. In a test on a social network with 1.8 billion edges, the algorithm finds the largest clique in about 20 minutes. At its heart the algorithm employs a branch-and-bound strategy with novel and aggressive pruning techniques. The pruning techniques include the combined use of core numbers of vertices along with a good initial heuristic solution to remove the vast majority of the search space. In addition, the exploration of the search tree is parallelized. During the search, processes immediately communicate changes to upper and lower bounds on the size of the maximum clique. This exchange of information occasionally results in a superlinear speedup because tasks with large search spaces can be pruned by other processes. We demonstrate the impact of the algorithm on applications using two different network analysis problems: computation of temporal strong components in dynamic networks and determination of compression-friendly ordering of nodes of massive networks.
Keywords:
parallel maximum clique algorithms
branch-and-bound
network analysis
temporal strong components
graph compression
Journal
IF:
2.6
Papers:
5.1K
Citations:
1.8W
