Picture of rolled up £5 note

Open Access research that shapes economic thinking...

Strathprints makes available scholarly Open Access content by the Fraser of Allander Institute (FAI), a leading independent economic research unit focused on the Scottish economy and based within the Department of Economics. The FAI focuses on research exploring economics and its role within sustainable growth policy, fiscal analysis, energy and climate change, labour market trends, inclusive growth and wellbeing.

The open content by FAI made available by Strathprints also includes an archive of over 40 years of papers and commentaries published in the Fraser of Allander Economic Commentary, formerly known as the Quarterly Economic Commentary. Founded in 1975, "the Commentary" is the leading publication on the Scottish economy and offers authoritative and independent analysis of the key issues of the day.

Explore Open Access research by FAI or the Department of Economics - or read papers from the Commentary archive [1975-2006] and [2007-2018]. Or explore all of Strathclyde's Open Access research...

Googling the brain : discovering hierarchical and asymmetric network structures, with applications in neuroscience

Crofts, J.J. and Higham, D.J. (2011) Googling the brain : discovering hierarchical and asymmetric network structures, with applications in neuroscience. Internet Mathematics, 7 (4). pp. 233-254.

[img] PDF
35hitech.pdf
Preprint

Download (553kB)

Abstract

Hierarchical organisation is a common feature of many directed networks arising in nature and technology. For example, a well-defined message-passing framework based on managerial status typically exists in a business organisation. However, in many real-world networks such patterns of hierarchy are unlikely to be quite so transparent. Due to the nature in which empirical data is collated the nodes will often be ordered so as to obscure any underlying structure. In addition, the possibility of even a small number of links violating any overall “chain of command” makes the determination of such structures extremely challenging. Here we address the issue of how to reorder a directed network in order to reveal this type of hierarchy. In doing so we also look at the task of quantifying the level of hierarchy, given a particular node ordering. We look at a variety of approaches. Using ideas from the graph Laplacian literature, we show that a relevant discrete optimization problem leads to a natural hierarchical node ranking. We also show that this ranking arises via a maximum likelihood problem assiocated with a new range-dependent hirearchical random graph model. This random graph insight allows us to compute a likelihood ratio that quantifies the overall tendency for a given network to be hierarchical. We also develop a node ordering algorithm based on the combinatorics of directed walks. In passing, we note that Google’s PageRank algorithm tackles a closely related problem, and may also be motivated from a walk-counting viewpoint. We illustrate the performance of the Hierarchical organisation is a common feature of many directed networks arising in nature and technology. For example, a well-defined message-passing framework based on managerial status typically exists in a business organisation. However, in many real-world networks such patterns of hierarchy are unlikely to be quite so transparent. Due to the nature in which empirical data is collated the nodes will often be ordered so as to obscure any underlying structure. In addition, the possibility of even a small number of links violating any overall “chain of command” makes the determination of such structures extremely challenging. Here we address the issue of how to reorder a directed network in order to reveal this type of hierarchy. In doing so we also look at the task of quantifying the level of hierarchy, given a particular node ordering. We look at a variety of approaches. Using ideas from the graph Laplacian literature, we show that a relevant discrete optimization problem leads to a natural hierarchical node ranking. We also show that this ranking arises via a maximum likelihood problem assiocated with a new range-dependent hirearchical random graph model. This random graph insight allows us to compute a likelihood ratio that quantifies the overall tendency for a given network to be hierarchical. We also develop a node ordering algorithm based on the combinatorics of directed walks. In passing, we note that Google’s PageRank algorithm tackles a closely related problem, and may also be motivated from a walk-counting viewpoint. We illustrate the performance of theHierarchical organisation is a common feature of many directed networks arising in nature and technology. For example, a well-defined message-passing framework based on managerial status typically exists in a business organisation. However, in many real-world networks such patterns of hierarchy are unlikely to be quite so transparent. Due to the nature in which empirical data is collated the nodes will often be ordered so as to obscure any underlying structure. In addition, the possibility of even a small number of links violating any overall “chain of command” makes the determination of such structures extremely challenging. Here we address the issue of how to reorder a directed network in order to reveal this type of hierarchy. In doing so we also look at the task of quantifying the level of hierarchy, given a particular node ordering. We look at a variety of approaches. Using ideas from the graph Laplacian literature, we show that a relevant discrete optimization problem leads to a natural hierarchical node ranking. We also show that this ranking arises via a maximum likelihood problem assiocated with a new range-dependent hirearchical random graph model. This random graph insight allows us to compute a likelihood ratio that quantifies the overall tendency for a given network to be hierarchical. We also develop a node ordering algorithm based on the combinatorics of directed walks. In passing, we note that Google’s PageRank algorithm tackles a closely related problem, and may also be motivated from a walk-counting viewpoint. We illustrate the performance of the resulting algorithms on synthetic network data, and on a real-world network from neuroscience where results may be validated biologically.