.png){kind=icon}
返回
Enumerating Maximum Cliques in Massive Graphs
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2020.3036013.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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 RMC, for the randomized maximum clique problem, employs a binary search while maintaining a lower bound (omega(c)) under bar and an upper bound (omega(c)) over bar of omega(G). In each iteration, RMC attempts to find a omega(t)-clique where omega(t) = left perpendicular ((omega(c)) under bar + ((omega(c)) over bar)/2 right perpendicular. As finding omega(t) in each iteration is NP-complete, we extract a seed set S such that the problem of finding a omega(t)-clique in G is equivalent to finding a omega(t)-clique in S with probability guarantees (>= 1 - n(-c)). We propose a novel iterative algorithm to determine the maximum clique by searching a k-clique in S starting from k = (omega(c)) under bar + 1 until S becomes {}, 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 RMCE to enumerate all maximum cliques in a given graph. As confirmed by the experiments, both RMC and RMCE are much more efficient and robust than previous solutions, RMC can always find the exact maximum clique, and RMCE can always enumerate all maximum cliques in a given graph.
Keyword:
Maximum clique
community search
social networks
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
10.4
论文数:
6.9K
被引数:
3.2W
机构
引用论文
A cytochemical study of nuclear changes in boar, bull, goat, mouse, rat, and stallion spermatids
PREAI
分享收藏Reduced white matter microstructural integrity correlates with cognitive deficits in minimal hepatic encephalopathy轻度肝性脑病中白质微结构完整性降低与认知缺陷相关.png)
Gut
GutIF0
PREAI
分享收藏
分享收藏
查看更多内容