Hyperbolic Embedding to the Rescue in Communication and Social Networks

We consider the following problems where this embedding provides high performance and efficient solutions. First, we develop greedy backpressure routing algorithms for both static and dynamic wireless networks that result in much better, and even controllable, trade-off between throughput and delay. The solution involves a new combination of greedy hyperbolic routing and backpressure scheduling. Second, we develop a context-aware routing scheme for social networks that aims to increase the relevance of messages shared across a social network. It achieves this by forwarding each message to the most relevant nodes, taking into account both user preferences and the network structure. Again greedy hyperbolic embedding is utilized and a new relevance metric is constructed that incorporates a context similarity measure and network structure, the latter represented by the hyperbolic distance between nodes. Third, we consider the advertisement allocation problem for large social networks. We show how hyperbolic embedding can be utilized again to formulate the underlying optimization problem in a continuum that not only reduces dramatically the dimensionality of the advertisement allocation problem from that of the associated integer programming formulation but also provides a general framework for designing allocation strategies incorporating business rules. Fourth, we consider network tomography problems, whereby properties of internal nodes and links of the network are dynamically inferred from iterated adaptive measurements on a subset of nodes, called boundary nodes. Again using hyperbolic embedding we demonstrate that these tomography problems can be formulated as true tomography problems in hyperbolic space, involving inversion of Radon transforms on symmetric spaces; the tomographic "integrals" are now over paths of the graph