Back to search

Georgia Institute of Technology

The hourglass effect in source-target dependency networks

Abstract

dc:description.abstract

Many hierarchically modular systems are structured in a way that resembles the shape of an hourglass: the system generates many outputs from many inputs through a relatively small number of intermediate modules that are critical for the operation of the entire system,referred to as the waist of the hourglass.We first investigate the hourglass effect in hierarchical, but not necessarily layered, dependency networks. Our analysis focuses on the number of source-to-target dependency paths that traverse each vertex. We identify the core of a dependency network as the smallest set of vertices that collectively cover a given fraction of all dependency paths. We examine if a given network exhibits the hourglass property or not, comparing its core size with a “flat” (i.e., non-hierarchical) network that preserves the source dependencies of each target in the original network.As a possible explanation for the hourglass effect, we propose the “Reuse Preference”(RP) model that captures the bias of new modules to reuse intermediate modules of similar complexity instead of connecting directly to sources or low-complexity modules.We have applied this analysis in dependency networks that include technological, natural and information systems, showing that they exhibit the general hourglass property but to a varying degree and with different waist characteristics. We also compare the hour-glass analysis framework with existing network “core finding” methods and compare path centrality with other vertex centrality metrics. Finally, we extend our framework to networks that are not strictly hierarchical because they include feedback loops and lateral connections. In that context, we focus on the C. elegans brain network (connectome) and identify a core of ten neurons that almost all paths from sensory to motor neurons traverse. We explain the role of those neurons as a dimensionality reduction mechanism, compressing the information provided by the 88 sensory neurons into a smaller set of intermediate-complexity functions that are re-used by the 119 motor neurons.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Computer Science
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2018

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Sabrin, Kaeser M.
Advisor dc:contributor.advisor
  • Dovrolis, Constantine
Committee members dc:contributor.committeemember
  • Dilkina, Bistra
  • Catalyurek, Umit
  • Basole, Rahul
  • Sahneh, Faryad

Subjects

dc:subject × 2

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/60778

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Sabrin, Kaeser M.. The hourglass effect in source-target dependency networks. Doctoral thesis, Georgia Institute of Technology, 2018. http://hdl.handle.net/1853/60778