A New Mathematical Model for the Intersection Clustering Problem

The Intersection Clustering Problem (ICP) aims to identify data dependencies by grouping objects according to their use of shared resources, such as words used in writing fake news, collusion companies competing in public tenders or co-authors of scientific articles. In this work, starting from the concept of an intersection graph for ICP, we propose a new mathematical formulation for the problem, aiming to create an optimal partitioning with up to two objects in each part. The experiments carried out on artificial instances show that the new formulation was able to reach the optimum in all cases within the time limit, with a 99.2% reduction in the time taken to solve the instances. At the same time, the solutions obtained maintain the quality of the model in generating groups with better intersections than classical models according to the average silhouette intersection index metric.