Search ETDs:
Delta-Hyperbolicity in Real-World Networks: Algorithmic Analysis and Implications
Alrasheed, Hend

2018, PHD, Kent State University, College of Arts and Sciences / Department of Computer Science.
The main interest behind a lot of research has been in understanding the structural properties in the topology
of large graphs. The goal is to exploit any hidden properties to increase the efficiency of existing algorithms,
as well as to propose new algorithms that are more natural to the structure that a graph exhibits. Structural
properties such as the small-world property and the power-law degree distribution have been studied widely
for multiple network types. Another graph structural property that has been commonly investigated is the
delta-hyperbolicity. The delta-hyperbolicity is a parameter that measures how close the metric structure of
a graph is to the metric structure of a tree. The graph delta-hyperbolicity is related to its underlying
hyperbolic geometry (negative curvature). Gromov hyperbolicity is important in divers applied fields
including discrete mathematics, biology, phylogenetics, and several aspects of computer science such as
algorithms and networking. The importance of delta-hyperbolicity in graphs emerges from the fact that in
many applications, many intractable problems become tractable when the graph has a metric structure that
is close to the tree metric. Recent empirical studies showed that many real-world graphs are tree-like from
a metric point of view.
In this dissertation, we are concerned with the theoretical and empirical implications of delta-hyperbolicity
in graphs. We propose two models to partition a graph into a core and periphery parts by exploiting a
property that is intrinsic to delta-hyperbolic graphs – the eccentricity-based bending property of shortest
paths. We theoretically analyze the essence of this bending by studying its relationship to the distances
between vertex pairs. Moreover, we empirically identify a graph's core as the part that is responsible for
maximizing its delta-hyperbolicity parameter. Identifying the area in a graph where the delta-hyperbolicity
value is maximized is crucial for reducing the cost of its computation.
In many applications, it is desirable to map a graph into another structure that is cheapest (in terms of the
amount of stored data) and that maintains some of the properties in the original graph. Trees are the cheapest
structure that a graph can be mapped to and that maintains its connectivity. An eccentricity k-approximating
tree is a tree in which the difference between the eccentricity of any vertex in the tree and its eccentricity
in the original graph is at most k. It is known that any delta-hyperbolic graph admits a distance
approximating tree with an additive error O(delta log n). In this dissertation, we investigate the eccentricity
approximating tree problem for delta-hyperbolic graphs.
Feodor Dragan (Advisor)
Javed Khan (Committee Member)
Hassan Peyravi (Committee Member)
Dmitry Ryabogin (Committee Member)
Artem Zvavitch (Committee Chair)
196 p.

Recommended Citations

Hide/Show APA Citation

Alrasheed, H. (2018). Delta-Hyperbolicity in Real-World Networks: Algorithmic Analysis and Implications. (Electronic Thesis or Dissertation). Retrieved from https://etd.ohiolink.edu/

Hide/Show MLA Citation

Alrasheed, Hend. "Delta-Hyperbolicity in Real-World Networks: Algorithmic Analysis and Implications." Electronic Thesis or Dissertation. Kent State University, 2018. OhioLINK Electronic Theses and Dissertations Center. 23 Oct 2018.

Hide/Show Chicago Citation

Alrasheed, Hend "Delta-Hyperbolicity in Real-World Networks: Algorithmic Analysis and Implications." Electronic Thesis or Dissertation. Kent State University, 2018. https://etd.ohiolink.edu/

Files

Dissertation.pdf (1.5 MB) View|Download