Algorithm 457: finding all cliques of an undirected graph
Open accessThe DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.
Abstract
bttroductian.A maximal complete subgraph (clique) is a complete subgraph that is not contained in any other complete subgraph.A recent paper [1] describes a number of techniques to find maximal complete subgraphs of a given undirected graph.In this paper, we present two backtracking algorithms, using a branchand-bound technique [4] to cut off branches that cannot lead to a clique.The first version is a straightforward implementation of the basic algorithm.It is mainly presented to illustrate the method used.This version generates cliques in alphabetic (lexicographic) order.The second version is derived from the first and generates cliques in a rather unpredictable order in an attempt to minimize the number of branches to be traversed.This version tends to produce the larger cliques first and to generate sequentially cliques having a large common intersection.The detailed algorithm for version 2 is presented here. Description of the algorithm--Version 1.Three sets play an important role in the algorithm.(1) The set compsub is the set to be extended by a new point or shrunk by one point on traveling along a branch of the backtracking tree.The points that are eligible to extend compsub, i.e. that are connected to all points in compsub, are collected recursively in the remaining two sets.(2) The set candidates is the set of all points that will in due time serve as an extension to the present configuration of compsub.(3) The set not is the set of all points that have at an earlier stage already served as an extension of the present configuration of compsub and are now explicitly excluded.The reason for maintaining this set trot will soon be made clear.The core of the algorithm consists of a recursively defined extension operator that will be applied to the three sets Just described.It has the duty to generate all extensions of the given configuration of compsub that it can make with the given set of candidates and that do not contain any of the points in not.To put it differently: all extensions of compsub containing any point in not have already been generated.The basic mechanism now consists of the following five steps:
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
An Algorithm for the Traveling Salesman Problem
Little, J. D. C., Murty, K. G., Sweeney, D. W., & Karel, C. (1963) · Operations Research · doi:10.1287/opre.11.6.972 · Cited by 1,058
Moon, J. W., & Moser, L. (1965) · Israel Journal of Mathematics · doi:10.1007/bf02760024 · Cited by 837
An Analysis of Some Graph Theoretical Cluster Techniques
Augustson, J. G., & Minker, J. (1970) · Journal of the ACM · doi:10.1145/321607.321608 · Cited by 229
Cited by
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293
“The BronKerbosch method (Bron and Kerbosch, 1973) runs in a time growing exponentially with the size of the graph.”
MethodMolecular Docking: A Powerful Approach for Structure-Based Drug Discovery
Meng, X.-Y., Zhang, H.-X., Mezei, M., & Cui, M. (2011) · Current Computer Aided-Drug Design · doi:10.2174/157340911795677602 · Cited by 3,771
“It characterizes the ligand and receptor as sets of spheres which could be overlaid by means of a clique detection procedure [101].”
MethodKrissinel, E., & Henrick, K. (2004) · Acta Crystallographica Section D Biological Crystallography · doi:10.1107/s0907444904026460 · Cited by 3,760
Gulati, R. (1999) · Strategic Management Journal · doi:10.1002/(sici)1097-0266(199905)20:5<397::aid-smj35>3.0.co;2-k · Cited by 2,482
An Algorithm for Subgraph Isomorphism
Ullmann, J. R. (1976) · Journal of the ACM · doi:10.1145/321921.321925 · Cited by 2,277
Community detection algorithms: A comparative analysis
Lancichinetti, A., & Fortunato, S. (2009) · Physical Review E · doi:10.1103/physreve.80.056117 · Cited by 2,177
Community detection in networks: a user guide
Fortunato, S., & Hric, D. (2016) · Physics Reports · doi:10.1016/j.physrep.2016.09.002 · Cited by 2,086
“Finding cliques is an NP-complete problem (Bomze et al., 1999); a popular technique is the Bron–Kerbosch method (Bron and Kerbosch, 1973).”
MethodThe Complexity of Enumeration and Reliability Problems
Valiant, L. G. (1979) · SIAM Journal on Computing · doi:10.1137/0208032 · Cited by 2,076
Detecting community structure in networks
Newman, M. E. J. (2004) · The European Physical Journal B - Condensed Matter · doi:10.1140/epjb/e2004-00124-y · Cited by 2,028
THIRTY YEARS OF GRAPH MATCHING IN PATTERN RECOGNITION
CONTE, D., FOGGIA, P., SANSONE, C., & VENTO, M. (2004) · International Journal of Pattern Recognition and Artificial Intelligence · doi:10.1142/s0218001404003228 · Cited by 1,370
Bomze, I. M., Budinich, M., Pardalos, P. M., & Pelillo, M. (1999) · Handbook of Combinatorial Optimization · doi:10.1007/978-1-4757-3023-4_1 · Cited by 1,148
Surprising similarities in structure comparison
Gibrat, J.-F., Madej, T., & Bryant, S. H. (1996) · Current Opinion in Structural Biology · doi:10.1016/s0959-440x(96)80058-3 · Cited by 1,049
TEASER: Fast and Certifiable Point Cloud Registration
Yang, H., Shi, J., & Carlone, L. (2021) · IEEE Transactions on Robotics · doi:10.1109/tro.2020.3033695 · Cited by 895
Using graph theory to analyze biological networks
Pavlopoulos, G. A., Secrier, M., Moschopoulos, C. N., Soldatos, T. G., Kossida, S., Aerts, J., Schneider, R., & Bagos, P. G. (2011) · BioData Mining · doi:10.1186/1756-0381-4-10 · Cited by 791
The worst-case time complexity for generating all maximal cliques and computational experiments
Tomita, E., Tanaka, A., & Takahashi, H. (2006) · Theoretical Computer Science · doi:10.1016/j.tcs.2006.06.015 · Cited by 771
Detect overlapping and hierarchical community structure in networks
Shen, H., Cheng, X., Cai, K., & Hu, M.-B. (2009) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2008.12.021 · Cited by 723
Microbial species delineation using whole genome sequences
Varghese, N. J., Mukherjee, S., Ivanova, N., Konstantinidis, K. T., Mavrommatis, K., Kyrpides, N. C., & Pati, A. (2015) · Nucleic Acids Research · doi:10.1093/nar/gkv657 · Cited by 704
Cortical high-density counterstream architectures
Markov, N. T., Ercsey-Ravasz, M., Van Essen, D. C., Knoblauch, K., Toroczkai, Z., & Kennedy, H. (2013) · Science · doi:10.1126/science.1238406 · Cited by 616
“Using methods adapted to high-density graphs (83), we have shown that the G29x29 subgraph harbors 13 cliques (complete subgraphs in which all possible connections are present) of size 10.”
MethodCommunity detection in Social Media: Performance and application considerations
Papadopoulos, S., Kompatsiaris, Y., Vakali, A., & Spyridonos, P. (2012) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-011-0224-z · Cited by 615
Predicting defects using network analysis on dependency graphs
Zimmermann, T., & Nagappan, N. (2008) · Proceedings of the 13th international conference on Software engineering - ICSE '08 · doi:10.1145/1368088.1368161 · Cited by 580
Critical evaluation of search algorithms for automated molecular docking and database screening
Ewing, T. J. A., & Kuntz, I. D. (1997) · Journal of Computational Chemistry · doi:10.1002/(sici)1096-987x(19970715)18:9<1175::aid-jcc6>3.0.co;2-o · Cited by 533
Isolating cause-effect chains from computer programs
Zeller, A. (2002) · Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering · doi:10.1145/587051.587053 · Cited by 530
Querying k-truss community in large and dynamic graphs
Huang, X., Cheng, H., Qin, L., Tian, W., & Yu, J. X. (2014) · Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2588555.2610495 · Cited by 488
A Predictive Network Model of Cerebral Cortical Connectivity Based on a Distance Rule
Ercsey-Ravasz, M., Markov, N. T., Lamy, C., Van Essen, D. C., Knoblauch, K., Toroczkai, Z., & Kennedy, H. (2013) · Neuron · doi:10.1016/j.neuron.2013.07.036 · Cited by 487
“Thus, oneneedsanovel method that is better suited to extracting network cores from high-density graphs such as clique distribution analysis (Bron and Kerbosch, 1973).”
Hattori, M., Okuno, Y., Goto, S., & Kanehisa, M. (2003) · Journal of the American Chemical Society · doi:10.1021/ja036030u · Cited by 484
Shepard, R. N., & Arabie, P. (1979) · Psychological Review · doi:10.1037//0033-295x.86.2.87 · Cited by 476
Finding a Maximum Independent Set
Tarjan, R. E., & Trojanowski, A. E. (1977) · SIAM Journal on Computing · doi:10.1137/0206038 · Cited by 474
FlexE: efficient molecular docking considering protein structure variations
Claußen, H., Buning, C., Rarey, M., & Lengauer, T. (2001) · Journal of Molecular Biology · doi:10.1006/jmbi.2001.4551 · Cited by 430
IMG/M: integrated genome and metagenome comparative data analysis system
Chen, I.-M. A., Markowitz, V. M., Chu, K., Palaniappan, K., Szeto, E., Pillay, M., Ratner, A., Huang, J., Andersen, E., Huntemann, M., et al. (2017) · Nucleic Acids Research · doi:10.1093/nar/gkw929 · Cited by 425
Maximum common subgraph isomorphism algorithms for the matching of chemical structures
Raymond, J. W., & Willett, P. (2002) · Journal of Computer-Aided Molecular Design · doi:10.1023/a:1021271615909 · Cited by 424
A New Method to Detect Related Function Among Proteins Independent of Sequence and Fold Homology
Schmitt, S., Kuhn, D., & Klebe, G. (2002) · Journal of Molecular Biology · doi:10.1016/s0022-2836(02)00811-2 · Cited by 423
Truss decomposition in massive networks
Wang, J., & Cheng, J. (2012) · Proceedings of the VLDB Endowment · doi:10.14778/2311906.2311909 · Cited by 423
Pardalos, P. M., & Xue, J. (1994) · Journal of Global Optimization · doi:10.1007/bf01098364 · Cited by 382
SVIM: structural variant identification using mapped long reads
Heller, D., & Vingron, M. (2019) · Bioinformatics · doi:10.1093/bioinformatics/btz041 · Cited by 372
Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time
Eppstein, D., Löffler, M., & Strash, D. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-17517-6_36 · Cited by 356
A classification for community discovery methods in complex networks
Coscia, M., Giannotti, F., & Pedreschi, D. (2011) · Statistical Analysis and Data Mining: The ASA Data Science Journal · doi:10.1002/sam.10133 · Cited by 353
Hu, Y., Boyd-Graber, J., Satinoff, B., & Smith, A. (2014) · Machine Learning · doi:10.1007/s10994-013-5413-0 · Cited by 338
Molecule-pharmacophore superpositioning and pattern matching in computational drug design
Wolber, G., Seidel, T., Bendix, F., & Langer, T. (2008) · Drug Discovery Today · doi:10.1016/j.drudis.2007.09.007 · Cited by 315
Efficient overlay of small organic molecules using 3D pharmacophores
Wolber, G., Dornhofer, A. A., & Langer, T. (2007) · Journal of Computer-Aided Molecular Design · doi:10.1007/s10822-006-9078-7 · Cited by 312
Niem�ller, K., & Schijf, B. (1980) · Quality and Quantity · doi:10.1007/bf00154795 · Cited by 309
Reverse engineering feature models
She, S., Lotufo, R., Berger, T., Wąsowski, A., & Czarnecki, K. (2011) · Proceedings of the 33rd International Conference on Software Engineering · doi:10.1145/1985793.1985856 · Cited by 302
Finding a Maximum Clique in an Arbitrary Graph
Balas, E., & Yu, C. S. (1986) · SIAM Journal on Computing · doi:10.1137/0215075 · Cited by 295
Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees
Tsourakakis, C., Bonchi, F., Gionis, A., Gullo, F., & Tsiarli, M. (2013) · Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2487575.2487645 · Cited by 294
Understanding Distributed Poisoning Attack in Federated Learning
Cao, D., Chang, S., Lin, Z., Liu, G., & Sun, D. (2019) · 2019 IEEE 25th International Conference on Parallel and Distributed Systems (ICPADS) · doi:10.1109/icpads47876.2019.00042 · Cited by 285
Detecting highly overlapping community structure by greedy clique expansion
Lee, C., Reid, F., McDaid, A. F., & Hurley, N. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1002.1827 · Cited by 271
Recognition of Functional Sites in Protein Structures
Shulman-Peleg, A., Nussinov, R., & Wolfson, H. J. (2004) · Journal of Molecular Biology · doi:10.1016/j.jmb.2004.04.012 · Cited by 269
Computational methods for the structural alignment of molecules
Lemmen, C., & Lengauer, T. (2000) · Journal of Computer-Aided Molecular Design · doi:10.1023/a:1008194019144 · Cited by 262
A Survey on Adaptive 360° Video Streaming: Solutions, Challenges and Opportunities
Yaqoob, A., Bi, T., & Muntean, G.-M. (2020) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2020.3006999 · Cited by 254
SAGA: a subgraph matching tool for biological graphs
Tian, Y., McEachin, R. C., Santos, C., States, D. J., & Patel, J. M. (2007) · Bioinformatics · doi:10.1093/bioinformatics/btl571 · Cited by 253
eHiTS: A new fast, exhaustive flexible ligand docking system
Zsoldos, Z., Reid, D., Simon, A., Sadjad, S. B., & Johnson, A. P. (2007) · Journal of Molecular Graphics and Modelling · doi:10.1016/j.jmgm.2006.06.002 · Cited by 249
Enumerating all connected maximal common subgraphs in two graphs
Koch, I. (2001) · Theoretical Computer Science · doi:10.1016/s0304-3975(00)00286-3 · Cited by 243
Community detection in large-scale social networks
Du, N., Wu, B., Pei, X., Wang, B., & Xu, L. (2007) · Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis · doi:10.1145/1348549.1348552 · Cited by 231
Structural and Chemical Profiling of the Human Cytosolic Sulfotransferases
Allali-Hassani, A., Pan, P. W., Dombrovski, L., Najmanovich, R., Tempel, W., Dong, A., Loppnau, P., Martin, F., Thonton, J., Edwards, A. M., et al. (2007) · PLoS Biology · doi:10.1371/journal.pbio.0050097 · Cited by 217
A Survey of Algorithms for Dense Subgraph Discovery
Lee, V. E., Ruan, N., Jin, R., & Aggarwal, C. (2010) · Advances in Database Systems · doi:10.1007/978-1-4419-6045-0_10 · Cited by 216
“One well-known enumeration algorithm for generating cliques was proposed by Bron and Kerbosch [12].”
MethodOlmea, O., & Valencia, A. (1997) · Folding and Design · doi:10.1016/s1359-0278(97)00060-6 · Cited by 203
Kinoshita, K., & Nakamura, H. (2003) · Protein Science · doi:10.1110/ps.0368703 · Cited by 162
“Finally, the largest clique was found for the graph using the conventional exhaustive search algorithm (Bron and Kerbosch 1973).”
MethodEncoding Protein–Ligand Interaction Patterns in Fingerprints and Graphs
Desaphy, J., Raimbaud, E., Ducrot, P., & Rognan, D. (2013) · Journal of Chemical Information and Modeling · doi:10.1021/ci300566n · Cited by 159
$O(N^3)$ Measurement Cost for Variational Quantum Eigensolver on Molecular Hamiltonians
Gokhale, P., Angiuli, O., Ding, Y., Gui, K., Tomesh, T., Suchara, M., Martonosi, M., & Chong, F. T. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2020.3035814 · Cited by 104
“In our benchmarking, we performed MIN-CLIQUECOVERs using the Boppana–Halldórsson algorithm [58] included in the NetworkX Python package [59], as well as the Bron–Kerbosch algorithm [60], which we implemented ourselves.”
Method$O(N^3)$ Measurement Cost for Variational Quantum Eigensolver on Molecular Hamiltonians
Gokhale, P., & Chong, F. T. (2019) · arXiv · doi:10.48550/arxiv.1908.11857 · Cited by 104
SWISH: semantic analysis of window titles and switching history
Oliver, N., Smith, G., Thakkar, C., & Surendran, A. C. (2006) · Proceedings of the 11th international conference on Intelligent user interfaces · doi:10.1145/1111449.1111492 · Cited by 89
Discovering user communities on the Internet using unsupervised machine learning techniques
Paliouras, G., Papatheodorou, C., Karkaletsis, V, & Spyropoulos, C. D. (2002) · Interacting with Computers · doi:10.1016/s0953-5438(02)00015-2 · Cited by 38
“Despite the large theoretical complexity of the clique-finding problem, in practice the algorithm that we have implemented (Bron and Kerbosch, 1973) is fast.”
BackgroundA Rete Network Construction Algorithm for Incremental Pattern Matching
Varró, G., & Deckwerth, F. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-38883-5_13 · Cited by 26
“As pairwise independence does not necessarily hold for the component deltas in set ∆s′ , the method allMaximalIndependentSets carries out the Bron-Kerbosch algorithm [11] (line 3), and calculates all such subsets of ∆s′ , whose (component delta) elements are pairwise independent.”
MethodPallante, L., Cannariato, M., Androutsos, L., Zizzi, E. A., Bompotas, A., Hada, X., Grasso, G., Kalogeras, A., Mavroudi, S., Di Benedetto, G., et al. (2024) · Scientific Reports · doi:10.1038/s41598-024-56893-7 · Cited by 12
Metadata
- Authors
- Bron, C., & Kerbosch, J.
- Venue
- Communications of the ACM
- Published
- 1973-09
- Volume
- 16
- Issue
- 9
- Pages
- 575-577
- ISSN
- 0001-0782 (ISSN-L)
- 1557-7317
- OpenAlex
- W2116007667
- Cited by
- 2,452
- References
- 3
- FWCI
- 4.51
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.