The Skeleton of Hyperbolic Graphs for Greedy Navigation

Heszberger, Zalán and Bíró, József and Gulyás, András (2020) The Skeleton of Hyperbolic Graphs for Greedy Navigation. In: 6th Annual Conference on Computational Science and Computational Intelligence, 2019. dec. 5-8., Las Vegas, Nevada, USA.

Preview

Text CSCI_2019_Las_Vegas.pdf Download (444kB) | Preview

Abstract

Random geometric (hyperbolic) graphs are impor-tant modeling tools in analyzing real-world complex networks.Greedy navigation (routing) is one of the most promising infor-mation forwarding mechanisms in complex networks. This paperis dealing with greedy navigability of complex graphs generatedby using a metric (hyperbolic) space. Greedy navigability meansthat every source-destination pairs in the graph can communicatein such a way that every node passes the information towards thatneighboring node which is ”closest” to the destination in terms ofnode coordinates in the metric space. A set of compulsory linksin greedy navigable graphs called Greedy Skeleton is identified.Because the two-dimensional hyperbolic plane (H2, also knownas the two dimensional Bolyai-Lobachevsky Space [2]) turnedout to be extremely useful in modelling and generating real-like networks, we deal with the statistical properties of theGreedy Skeleton when the metric space isH2. Some examples ofnumerical studies and simulation results supporting the analyticalformulae are also performed. The significance of the results liesin that every (either artificial or natural) network formationprocess aiming at greedy navigability must contain this GreedySkeleton. Furthermore, this could be an important step towardsthe formal argumentation of the very high greedy navigabilityof some models observed only experimentally for the time being,and also to analyze equilibrium of greedy network navigationgames onH2.

Actions (login required)

Edit Item