Abstract
delta-Hyperbolicity is a graph parameter that shows how close to a tree a graph is metrically. In this work, we propose a method that reduces the size of the graph to only a subset that is responsible for maximizing its delta-hyperbolicity using the local dominance relationship between vertices. Furthermore, we empirically show that the hyperbolicity of a graph can be found in a set of vertices that are in close proximity and that concentrate in the core of the graph. We adopt two core definitions each of which represents a different notion of vertex coreness. The minimum-cover-set core, which is a transport-based core, and the k-core, which is a density-based core. Our observations have crucial implications on computing the delta-hyperbolicity of large graphs. (Parts of this work were published in Alrasheed (On the delta-hyperbolicity of complex networks. In: Proceedings of the IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM), 2016).)