Model-independent embedding of directed networks into Euclidean and hyperbolic spaces

Complex systems are often represented as networks, where nodes represent entities and edges represent their interactions. Analyzing the structure of these networks reveals valuable insights into the system's behavior. Common characteristics of complex networks include the small-world property, high clustering coefficient, scale-free degree distribution, and community structure. Hyperbolic geometry provides an intuitive framework for understanding these properties simultaneously. Hyperbolic network models position nodes in hyperbolic space, connecting them with probabilities that decay with hyperbolic distance. This naturally generates networks with small-world, highly clustered, and scale-free characteristics, and often exhibit strong community structure. Furthermore, studies suggest that real-world networks also possess hidden geometric structures, hinting at underlying metric spaces that influence their properties. This has led to research on hyperbolic embedding, aiming to optimally arrange network nodes in hyperbolic space to reflect the given network structure. Existing methods, like HyperMap (based on E-PSO), LaBNE (Laplacian-based), coalescent embeddings, and hydra (hyperbolic distance recovery and approximation), primarily focus on undirected networks. While some methods account for directed networks, they often rely on specific models or complex neural networks. The present study addresses the significant gap in model-independent embedding methods capable of handling directed networks, where the direction of links indicates asymmetric relationships or flows.

Several methods have been developed for hyperbolic embedding of networks. Likelihood optimization approaches, such as HyperMap, utilize loss functions based on assumed hyperbolic generation models. Dimension reduction techniques applied to topology-representing matrices, including Laplacian-based methods (LaBNE) and coalescent embeddings, offer alternative strategies, often involving Euclidean embeddings followed by hyperbolic conversion. The hydra method directly generates hyperbolic coordinates through dimension reduction. Artificial neural networks provide another approach, learning low-dimensional representations but with increased complexity and interpretability challenges. However, almost all existing methods lack the crucial ability to handle directed networks effectively. Existing approaches for directed networks either rely on likelihood optimization with specific models or employ neural networks, limiting their generality and interpretability. This paper presents a novel framework that overcomes these limitations.

This paper proposes a model-independent framework for embedding directed networks into hyperbolic spaces. The framework comprises three main steps: (1) creating a proximity matrix based on network topology; (2) performing dimension reduction on this matrix to obtain a Euclidean embedding; and (3) converting the Euclidean coordinates to hyperbolic coordinates using a model-independent conversion (MIC). The proximity matrix can be defined in several ways. The authors propose a new measure based on exponential shortest path lengths (TREXPEN), where Pst = e^(-q * SPLst), with SPLst being the shortest path length from node s to t, and q a decay parameter. This is compared to using the Katz matrix, a weighted sum of paths. Variants of these methods (HOPE-S, HOPE-R, TREXPEN-S, TREXPEN-R) are introduced, involving shifting the mean of proximity values to zero (HOPE-S, TREXPEN-S) or removing the first dimension (HOPE-R, TREXPEN-R). The dimension reduction employs singular value decomposition (SVD). The MIC converts Euclidean coordinates to hyperbolic coordinates in the native representation of hyperbolic space, preserving the attractivity of radial positions regarding link creation. The conversion uses the relationship between Euclidean inner products and hyperbolic distances, transferring angular coordinates directly while transforming radial coordinates to maintain consistency in attractivity. The authors derive a formula for the hyperbolic radial coordinate based on the Euclidean radial coordinate and network size, ensuring the hyperbolic volume scales appropriately. Additionally, a method called TREXPIC is introduced, which embeds networks directly into hyperbolic space using dimension reduction of a Lorentz product matrix calculated from exponential shortest path lengths, eliminating the need for an intermediate Euclidean embedding. The methods were evaluated on synthetic and real networks.

The proposed methods were tested on various synthetic and real-world networks, including a Wikipedia subgraph, a yeast transcription network, a network of political blogs, and a word association network. The performance was evaluated using three key metrics: mapping accuracy, graph reconstruction, and greedy routing. Mapping accuracy, measured as Spearman's correlation between shortest path lengths and geometric measures (Euclidean distance, inner product, and hyperbolic distance), showed that TREXPEN, its variants, and TREXPIC generally outperformed HOPE and its variants, particularly when focusing on shortest paths. Graph reconstruction, evaluated using precision, AUPR, and AUROC, indicated that both Katz and exponential proximity measures performed well, with the Euclidean inner product often showing the best results, but hyperbolic embeddings demonstrating strong performance, especially when considering distances. Greedy routing, assessing network navigability, revealed that hyperbolic embeddings achieved the best scores across all networks, with distance-based routing in Euclidean space also performing reasonably well. The hyperbolic distance consistently produced high-quality scores across all three tasks. The authors emphasize the effectiveness of the exponential shortest path length-based methods (TREXPEN, TREXPIC) compared to those using the Katz matrix (HOPE). The model-independent Euclidean-to-hyperbolic conversion proved effective in producing high-quality hyperbolic embeddings from both TREXPEN and HOPE outputs. Two-dimensional hyperbolic layouts often appeared more visually appealing than their Euclidean counterparts.

The study's findings highlight the effectiveness of the proposed model-independent framework for embedding directed networks in both Euclidean and hyperbolic spaces. The use of exponential shortest path lengths in TREXPEN and TREXPIC proves advantageous over Katz proximities in several aspects, especially in greedy routing. The model-independent conversion method successfully bridges Euclidean and hyperbolic representations, offering a versatile approach. The hyperbolic distance consistently outperforms Euclidean distance and inner product as a measure for evaluating embedding quality. The results obtained across diverse real-world networks demonstrate the framework's broad applicability. The study's results support the use of hyperbolic geometry for representing complex network structures, emphasizing the importance of considering directedness in network analysis.

This paper presents a novel and effective framework for embedding directed networks into Euclidean and hyperbolic spaces. The model-independent nature of the methods, coupled with their strong performance across various evaluation metrics, positions them as a valuable contribution to the field of network analysis. Future research could explore the optimization of the proposed methods for specific types of networks or explore the relationship between network properties and the underlying geometry.

The study focuses on unweighted networks. While the exponential shortest path length measure can be extended to weighted networks (as shown in the supplementary material), further investigation of the performance of the framework on weighted networks is warranted. The parameter settings for the embedding algorithms were not exhaustively optimized. A more thorough parameter search might reveal further improvements in performance. The evaluation metrics used are not exhaustive, and additional metrics could provide a more complete picture of the embedding's quality. The visual comparison of embeddings is subjective and might not be fully generalizable across all types of networks.