Title: The Hourglass Effect in Source-Target Dependency Networks

Kaeser M. Sabrin
School of Computer Science
College of Computing
Georgia Institute of Technology

Date: Wednesday, Oct 31, 2018
Time: 02:30 pm - 04:30 pm 
Location: Klaus 1202

Committee:
Dr. Constantine Dovrolis (Advisor), School of Computer Science, Georgia Institute of Technology
Dr. Bistra Dilkina, Department of Computer Science, University of Southern California & School of Computational Science and Engineering, Georgia Institute of Technology
Dr. Ümit V. Çatalyürek, School of Computational Science and Engineering, Georgia Institute of Technology
Dr. Rahul Basole, School of Interactive Computing, Georgia Institute of Technology
Dr. Faryad Darabi Sahneh, Department of Mathematics, University of Arizona

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 hourglass 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.