UC San Diego

This dissertation provides a study of complex networks within a hyperbolic latent space model. We present, to our knowledge, the first theoretical analysis of popular link prediction indices on graphs in hyperbolic space. In network and graph analysis, nodes with different degrees are usually handled differently. For instance, when two individuals are both connected to a celebrity, it is often considered less likely that they know each other compared to a scenario in which they are both connected to an ordinary person. In this dissertation, we explore the reason behind this heuristic and analyze some popular link prediction indices through a hyperbolic graph model. Specifically, in this model, we identify the optimal weighted scheme for the common neighbor index and extend our findings to the shortest path index and some other indices, thereby introducing modifications to these methods. Empirical results demonstrate that our findings hold true not only in theory, i.e., for simulated data, but also in real-world networks. Moreover, we also explore different embedding methods to recover the underlying hyperbolic geometry from resulting graphs. By comparing different methods, we found that ordinal embedding effectively recovers the latent geometry of networks. Building on this, we proposed a modified ordinal embedding method that integrates the insights from our theoretical analysis. This enhancement further improves our ability to capture and represent the underlying hyperbolic structure of complex networks. This dissertation aims to enhance the understanding of complex networks, offering new perspectives and tools to analyze them effectively. Through a blend of theoretical rigor and practical experimentation, we provide a comprehensive study that contributes to the broader field of network science.