Troika algorithm: Approximate optimization for accurate clique partitioning and clustering of weighted networks

Clique partitioning is the fundamental network clustering task of identifying an optimal node partition for a weighted graph according to the real-valued edge weights. An optimal partition is one that maximizes the sum of within-cluster edge weights over all possible node partitions. This paper introduces a novel approximation algorithm, named Troika, to solve this NP-hard problem in small to mid-sized networks for instances of theoretical and practical relevance. Troika uses a branch-and-cut scheme for branching on node triples to find a partition that is within a user-specified optimality gap tolerance. Troika offers advantages over alternative methods for clique partitioning like heuristics and integer programming solvers. Unlike heuristics, Troika returns solutions within a guaranteed proximity to global optimality. Compared to the integer programming solver, Gurobi, Troika is faster for most benchmark instances. Besides its advantages for solving the clique partitioning problem, we demonstrate the applications of Troika in community detection and portfolio analysis. Troika returns partitions with higher proximity to optimal compared to eight modularity-based community detection algorithms. When used on networks of correlations among stocks, Troika reveals the dynamic changes in the structure of portfolio networks including downturns from the 2008 financial crisis and the reaction to the COVID-19 pandemic. Our comprehensive results based on benchmarks from the literature and new real and random networks point to Troika as a reliable and accurate method for solving clique partitioning instances with up to 5000 edges on standard hardware.Author summary: Clique partitioning is an unsupervised network clustering problem with applications across various fields. It involves partitioning the nodes of a real-valued weighted graph to maximize the total within-cluster edge weights. This paper introduces the Troika algorithm for approximating the globally optimal solution of the clique partitioning problem on small to mid-sized networks. Utilizing a branch-and-cut scheme for branching on node triples, Troika provides solutions within a user-specified optimality gap tolerance. Evaluations on benchmark datasets reveal Troika’s superior performance compared to existing methods. Troika strikes a tradeoff between speed and solution quality: it is much faster than the Gurobi integer programming solver, while it delivers solutions more accurate than heuristic solutions. Beyond clique partitioning, Troika excels in optimization-based community detection and portfolio analysis, outperforming eight modularity-based algorithms and uncovering dynamic changes to financial portfolios, including the 2008 financial crisis and COVID-19 impacts. Troika reliably provides optimal and near-optimal solutions for graphs with up to 5,000 edges on standard hardware.