Graph algorithms · Weighted graphs

N Highest Weight K-Clique Algorithm

Find up to the top N highest weight k-cliques in vertex-weighted graphs with K-CliqueWeight and K-CliqueDynWeight.

Get the software

Download & installation

To install the latest version of the K-Clique(Dyn)Weight algorithm follow this link.
Weighted graphs that were used in the paper for testing the algorithm are available on the links below. Graphs have integer vertex weights. Each graph's vertices were shuffled 10-times to test the algorithm's performance with different initial vertex orderings. Therefore, suffixes int1 - int10.
Graph files:
- Random weighted graphs
- Docking weighted graphs

K-CliqueWeight, along with its variant K-CliqueDynWeight efficiently detects up to the top N highest weight k-cliques in vertex-weighted graphs. It was tested on general random graphs and graphs designed for protein-ligand docking. It incorporates a new approximate graph coloring approach, which provides efficient upper bounds to the size and weight of a k-clique in the branch-and-bound algorithm.
The algorithm achieved a significant increase in speed compared to alternative methods, often by several orders of magnitude. It is integrated into the existing ProBiS-Dock algorithm for molecular docking, which streamlines the process of drug discovery.

Kati Rozman, An Ghysels, Bogdan Zavalnij, Tanja Kunej, Urban Bren, Dušanka Janežič, Janez Konc. Enhanced Molecular Docking: Novel Algorithm for Identifying Highest Weight k-Cliques in Weighted General and Protein-Ligand Graphs. J. Mol. Struct., 2024, 1304, 137639. Open Access