CLOVE, a Travelling Salesman’s approach to hyperbolic embeddings of complex networks with communities

The embedding of complex networks into metric spaces has emerged as a prominent area of research, accompanied by a diverse array of proposed methodologies. Low-dimensional hyperbolic spaces provide a natural target for such embeddings, facilitating an approximately uniform spatial distribution of nodes – even in scale-free networks – while enabling efficient navigability and accurate estimation of linking probabilities. Despite ongoing state-of-the-art advancements, hyperbolic embedding techniques increasingly exhibit diminishing marginal returns. Recent findings indicate that, following optimization, the communities within a complex network can be effectively represented as distinct angular sectors in the hyperbolic space. In this work, we present CLOVE, a scalable embedding approach that leverages this property through an iterative hierarchical arrangement of communities down to the level of individual nodes. A key step of our method involves determining the optimal angular ordering of communities at each hierarchical level, a challenge addressed by formulating and solving an instance of the Travelling Salesman Problem. Given that CLOVE surpasses many alternative techniques across various embedding quality metrics while maintaining high computational efficiency, it holds significant promise for downstream machine learning applications, including AI-driven pattern recognition. Embedding complex networks in hyperbolic spaces facilitates navigation and link prediction, though recent techniques face diminishing improvements. The authors present CLOVE, a scalable method that hierarchically organizes communities down to the node level by solving instances of the Travelling Salesman Problems, delivering high-quality embeddings and high efficiency for networks up to millions of nodes.