Discovering hierarchical and asymmetric network structures, with applications in neuroscience

 

JONATHAN CROFTS

UNIVERSITY OF STRATHCLYDE, UK

 

Hierarchical organization is a common feature in many naturally occurring and man-made systems. As an example, one can consider a tree-like structure, such as the United States government, where a well-defined message-passing framework clearly exists. However, in most real-world networks, any such patterns of hierarchy are unlikely to be quite so transparent. Due to the nature with which empirical data is collated the nodes will typically be ordered so as to obscure any underlying structure, in addition to this, the presence of a small number of links violating the so-called ``chain of command'' makes the determination of such structures extremely challenging. Here we use a combination of linear algebra and graph theory in an attempt to address this issue. We argue that given the adjacency matrix for a directed network, determining the underlying hierarchical structure equates to reordering the network nodes in such a manner that the adjacency matrix is "approximately" lower triangular. We then present and compare several algorithms for solving this problem. In particular, we shall see that an optimization problem can be formulated to solve the aforementioned, a solution of which can be written down explicitly in terms of the in/out-degree of the network. These ideas are then extended using the notion of a directed walk, this leads to a class of algorithms, based on matrix functions, that can be used to uncover hierarchies. Further we show that there exists a natural link between these ideas and Google's page-rank, thus we also compare the performance of page-rank as a tool for measuring hierarchy. We finish by showing how the algorithms perform when applied to both synthetic networks and a real-world network from neuroscience where results may be validated biologically. This work is supported through the Medical Research Council (UK) project grant G0601353.