Enumerating Maximum Cliques in Massive Graphs

Can Lu, Jeffrey Xu Yu, Hao Wei, Yikai Zhang

Abstract

Cliques refer to subgraphs in an undirected graph such that vertices in each subgraph are pairwise adjacent. The maximum clique problem, to find the clique with most vertices in a given graph, has been extensively studied. Besides its theoretical value as an NP-hard problem, the maximum clique problem is known to have direct applications in various fields, such as community search in social networks and social media, team formation in expert networks, gene expression and motif discovery in bioinformatics and anomaly detection in complex networks, revealing the structure and function of networks. However, algorithms designed for the maximum clique problem are expensive to deal with real-world networks. In this paper, we first devise a randomized algorithm for the maximum clique problem. Different from previous algorithms that search from each vertex one after another, our approach <i>RMC</i> , for the randomized maximum clique problem, employs a binary search while maintaining a lower bound <inline-formula><tex-math notation="LaTeX">$\underline{\omega _c}$</tex-math></inline-formula> and an upper bound <inline-formula><tex-math notation="LaTeX">$\overline{\omega _c}$</tex-math></inline-formula> of <inline-formula><tex-math notation="LaTeX">$\omega (G)$</tex-math></inline-formula> . In each iteration, <i>RMC</i> attempts to find a <inline-formula><tex-math notation="LaTeX">$\omega _t$</tex-math></inline-formula> -clique where <inline-formula><tex-math notation="LaTeX">$\omega _t=\lfloor (\underline{\omega _c}+\overline{\omega _c})/2\rfloor$</tex-math></inline-formula> . As finding <inline-formula><tex-math notation="LaTeX">$\omega _t$</tex-math></inline-formula> in each iteration is NP-complete, we extract a seed set <inline-formula><tex-math notation="LaTeX">$S$</tex-math></inline-formula> such that the problem of finding a <inline-formula><tex-math notation="LaTeX">$\omega _t$</tex-math></inline-formula> -clique in <inline-formula><tex-math notation="LaTeX">$G$</tex-math></inline-formula> is equivalent to finding a <inline-formula><tex-math notation="LaTeX">$\omega _t$</tex-math></inline-formula> -clique in <inline-formula><tex-math notation="LaTeX">$S$</tex-math></inline-formula> with probability guarantees ( <inline-formula><tex-math notation="LaTeX">$\geq$</tex-math></inline-formula> <inline-formula><tex-math notation="LaTeX">$ 1-n^{-c}$</tex-math></inline-formula> ). We propose a novel iterative algorithm to determine the maximum clique by searching a <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> -clique in <inline-formula><tex-math notation="LaTeX">$S$</tex-math></inline-formula> starting from <inline-formula><tex-math notation="LaTeX">$k=\underline{\omega _c}+1$</tex-math></inline-formula> until <inline-formula><tex-math notation="LaTeX">$S$</tex-math></inline-formula> becomes <inline-formula><tex-math notation="LaTeX">$\lbrace \rbrace$</tex-math></inline-formula> , when more iterations benefit marginally. Due to the potential inconsistency of maximum clique algorithms, we study the problem of maximum clique enumeration and propose an efficient algorithm <i>RMCE</i> to enumerate all maximum cliques in a given graph. As confirmed by the experiments, both <i>RMC</i> and <i>RMCE</i> are much more efficient and robust than previous solutions, <i>RMC</i> can always find the exact maximum clique, and <i>RMCE</i> can always enumerate all maximum cliques in a given graph.
BibTeX
@article{lu2022enumerating,
  author = {Can Lu and Jeffrey Xu Yu and Hao Wei and Yikai Zhang},
  title = {{Enumerating Maximum Cliques in Massive Graphs}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2022},
  doi = {10.1109/tkde.2020.3036013},
}

Loading related content...

Figure