Assortative partitions of complete graphs - Zlatanova, Magdalena (Ss Cyril and Methodius University in Skopje, Faculty of Computer Science and Engineering, Republic of North Macedonia, 2023)
This paper studies the problem of assortative partitions of complete graphs. Assortativity is a measure of the similarity of each node to its neighborhood. The results from numerical simulations suggest that for this class of graphs the assortative partitioning problem becomes more difficult as we increase the assortativity threshold. We observe a significant difference in the performance of the Gradient Descent algorithm when our assortativity threshold is set to 4 instead of 2. This numerically supports the hypothesis that the problem becomes more difficult.
Keywords: Combinatorial optimization, NP class, complete graphs, graph partitioning, statistical physics