Hierarchy, Graph Conductance, and the
Essential Synchronization Backbone
C. Tyler Diggans
April 6th, 1:00 pm, CAMP 175
Hierarchy is the quintessential form of structure, identifiable in complex systems as
diverse as government, the human brain, and tree root systems. However, the emergence of
hierarchy in growing complex networks is not yet fully understood. We seek to develop a the
connection between hierarchy and the network property of graph conductance. The amount of
hierarchy displayed by a system seems to be inversely proportional to the complexity of its
function or intended purpose. For example, tree-like branching structures often occur in simple
transport networks and this extreme case has been attributed to the so-called constructal law.
On the other end of complexity, we have the human brain, which although retains some
measure of hierarchy, also contains a vast number of loops in its neuronal network. After
suggesting that graph conductance provides a mechanism for understanding the emergence of
hierarchy, we provide an exploration of the wider range of hierarchical structures through the
dynamics of synchronization for networked oscillator systems. By defining a new optimization
problem that seeks to find the minimal spanning subgraph for which a synchronizing system
can maintain the same essential form of synchronization, we identify features of functional
networks that have a purpose beyond simple transport. By comparing solutions for systems of
phase oscillators with those of positive entropy (chaotic) oscillators, we show that the levels of
hierarchy are determined by spectra of the Laplacian. We focus on the role of graph
conductance in synchronization as it is important to global synchronization on the one hand,
but also plays a central role in the prevention of synchronization on the other hand. Although
we only explore the simplistic model of networked oscillators, we hope this contributes to a
deepening of understanding in the source and function of structure of many real-world
complex systems.
PhD Examining Committee:
Dr. Erik Bollt, Advisor
Dr. Daniel ben-Avraham, Co-Advisor
Dr. Dhara Trivedi
Dr. Jan Scrimgeour
Dr. Christino Tamon