Measuring the Hierarchy of Feedforward Networks

Abstract

In this paper we explore the concept of hierarchy as a quantifiable descriptor of ordered structures, departing from the definition of three conditions to be satisfied for a hierarchical structure: {\em order}, {\em predictability} and {\em pyramidal structure}. According to these principles we define a hierarchical index taking concepts from graph and information theory. This estimator allows to quantify the hierarchical character of any system susceptible to be abstracted in a feedforward causal graph, i.e., a directed acyclic graph defined in a single connected structure. Our hierarchical index is a balance between this predictability and pyramidal condition by the definition of two entropies: one attending the onward flow and other for the backward reversion. We show how this index allows to identify hierarchical, anti-hierarchical and non hierarchical structures. Our formalism reveals that departing from the defined conditions for a hierarchical structure, feedforward trees and the inverted tree graphs emerge as the only causal structures of maximal hierarchical and anti-hierarchical systems, respectively. Conversely, null values of the hierarchical index are attributed to a number of different configuration networks; from linear chains, due to their lack of pyramid structure, to full-connected feedforward graphs where the diversity of onward pathways is canceled by the uncertainty (lack of predictability) when going backwards. Some illustrative examples are provided for the distinction among these three types of hierarchical causal graphs.

12 pages, 6 figures. Accepted for publication in Chaos Journal special issue "Mesoscales in Complex Networks". Previous inconsistencies in the definition of the hierarchy index have been fixed

References in corpus (9)

• Hierarchical organization of modularity in metabolic networks
• Hierarchical structure and the prediction of missing links in networks
• Large-scale topological and dynamical properties of Internet
• Hierarchical modularity in human brain functional networks
• Extracting the hierarchical organization of complex systems
• Hierarchy Measures in Complex Networks
• Hierarchy and Feedback in the Evolution of the E. coli Transcription Network
• On the basic computational structure of gene regulatory networks
• Exploring the randomness of Directed Acyclic Networks

Cited by in corpus (10)

• Predictability and hierarchy in Drosophila behavior
• On the Origins of Hierarchy in Complex Networks
• The evolutionary origins of hierarchy
• Hierarchical networks of scientific journals
• Random walk hierarchy measure: What is more hierarchical, a chain, a tree or a star?
• Extracting tag hierarchies
• Time evolution of the hierarchical networks between PubMed MeSH terms
• Comparing the hierarchy of keywords in on-line news portals
• Information slows down hierarchy growth
• Comparing the hierarchy of author given tags and repository given tags in a large document archive