On the Origins of Hierarchy in Complex Networks

Bernat Corominas-Murtra; Joaquín Goñi; Ricard V. Solé; Carlos Rodríguez-Caso

Source-linked AI summary

On the Origins of Hierarchy in Complex Networks

Bernat Corominas-Murtra, Joaquín Goñi, Ricard V. Solé, Carlos Rodríguez-Caso

arXiv:1303.2503v2Mar 11, 2013physics.soc-phcond-mat.stat-mech

TL;DR

The paper addresses the lack of a general account of hierarchy’s forms and origins in complex systems. It formalizes hierarchy through a three-coordinate network morphospace and finds four major network groups, with random-like groups contrasting with ecologically and genetically constrained networks. The analysis is limited because functionality, dynamics, and weighted structures are not included.

Problem
Existing accounts do not capture hierarchy’s complexity and origins, leaving open its forms and whether selection or structural constraints shape it.
Method
The paper combines morphospace and network theories, using condensed directed graphs and treeness, feedforwardness, and orderability to compare networks.
Results
Four major network groups occupy the hierarchy morphospace; two match random-network expectations, while ecological and gene networks form distinct groups.
Takeaways & Limitations
Random-like hierarchy can arise from spontaneous degree correlations, whereas ecological and gene-network organization is associated with functional constraints.
Takeaways & Limitations
The study excludes functionality, dynamics, and weighted structures from its static causal-network analysis.

Abstract

from arXiv · show

Hierarchy seems to pervade complexity in both living and artificial systems. Despite its relevance, no general theory that captures all features of hierarchy and its origins has been proposed yet. Here we present a formal approach resulting from the convergence of theoretical morphology and network theory that allows constructing a 3D morphospace of hierarchies and hence comparing the hierarchical organization of ecological, cellular, technological and social networks. Embedded within large voids in the morphospace of all possible hierarchies, four major groups are identified. Two of them match the expected from random networks with similar connectivity, thus suggesting that non-adaptive factors are at work. Ecological and gene networks define the other two, indicating that their topological order is the result of functional constraints. These results are consistent with an exploration of the morphospace using in silico evolved networks.

I. INTRODUCTION

The paper frames hierarchy as widespread but polysemous, leaving open how to measure its forms and determine whether it reflects selection or structural constraints. It proposes combining morphospace and network theories to formalize and compare possible hierarchies.

Hierarchy appears across natural and artificial systems, including social, ecological, cellular, technological, and developmental organizations.
Existing descriptions of hierarchy involve order, levels, inclusion, or control but do not capture its full complexity or origins.
The paper asks whether hierarchy is widespread, what forms it takes, and whether selection pressures or structural constraints shape it.
The approach combines morphospace and network theories, treating hierarchy as a directed, pyramidal pattern in which few elements control many.
The study formalizes and quantitatively characterizes a morphospace of possible hierarchies and compares real networks with model systems.

II. THE COORDINATES OF HIERARCHY

The methodology represents relations as directed graphs, condenses cyclic modules into weighted nodes, and describes hierarchy using three coordinates: treeness, feedforwardness, and orderability.

System elements and their relations are represented as a directed graph G(V, E), with nodes connected by directed arrows.
The graph is transformed into a node-weighted condensed graph by collapsing each strongly connected component into one node.
Each condensed node receives weight α_i equal to the number of original graph elements it represents.
The hierarchy morphospace Ω uses treeness T, feedforwardness F, and orderability O as its three coordinates.

A. Treeness

Treeness quantifies how closely a graph follows a pyramidal chain of command by comparing forward and backward path uncertainty across the condensed graph and its leaf-removal subgraphs.

Treeness T ranges from -1 to 1 and distinguishes hierarchical, anti-hierarchical, and non-pyramidal structures.
Forward entropy Hf measures downstream path diversity, whereas backward entropy Hb measures uncertainty when pathways are followed in reverse.
The function f(G) is the normalized difference between Hf(GC) and Hb(GC).
T(G) averages f over the condensed graph and subgraphs generated by top-down or bottom-up leaf removal.
T(G) is set to zero for a linear chain with no entropy and for a condensed graph with no links, such as a totally cyclic graph.

B. Feedfordwardness

Feedforwardness measures how cyclic, non-orderable modules disrupt hierarchical flow, weighting their size and position within paths from maximal nodes.

Strongly connected components are non-orderable modules because their internal elements cannot be intrinsically ordered.
Feedforwardness F ranges from 0 to 1 and penalizes cyclic modules more when they occur nearer the top of the network.
For each path from the top of the condensed graph, F compares the path’s node fraction with the original nodes represented by those condensed nodes.
The set Π_M contains all paths starting at maximal nodes and ending at any other condensed-graph node.
F(G) is the average of path-level feedforwardness values over Π_M.

C. Orderability

Orderability (O) measures the fraction of graph nodes outside cycles, providing an estimate of how much of the network can be ordered.

C. Orderability: Orderability ranges from 0 to 1 and is defined as the fraction of graph nodes that do not belong to any cycle.Nodes outside cycles form the portion of the network that can actually be ordered.
C. Orderability: The orderability descriptor complements treeness and feedforwardness in the three-coordinate hierarchy representation.Together, these indicators are collected to evaluate and compare networks in the morphospace Ω.

III. THE DEFINITION OF THE MORPHOSPACE Ω

The hierarchy morphospace Ω represents each directed network with treeness, feedforwardness, and orderability, distinguishing pyramidal, cyclic, and feedforward organization.

III. THE DEFINITION OF THE MORPHOSPACE Ω: Each directed network is represented in a 3D morphospace Ω by a point determined by its hierarchical properties.The space lies within [−1, 1] × [0, 1] × [0, 1].
III. THE DEFINITION OF THE MORPHOSPACE Ω: The perfect hierarchy is located at u(G) = (1, 1, 1), while a totally cyclic network is located at u(G) = (0, 0, 0).Orderability and feedforwardness also define forbidden regions of the morphospace.
III. THE DEFINITION OF THE MORPHOSPACE Ω: Feedforward networks lie on the F(G) = O(G) = 1 line, whereas F and O differ when orderability approaches zero.Feedforwardness is measured on the condensed graph, while orderability concerns nodes outside cycles in the original graph.
III. THE DEFINITION OF THE MORPHOSPACE Ω: Treeness adds information about the organization of the feedforward structure after network condensation.The plane T = 0 separates hierarchical and anti-hierarchical structures; with cycles, it yields bow-tie organization.

IV. NULL MODELS AND REAL NETWORK ANALYSIS

Random models and real networks occupy distinct but partly overlapping regions of the hierarchy morphospace, producing four major network groups and different structural scenarios.

IV. NULL MODELS AND REAL NETWORK ANALYSIS: Random networks with different degree distributions occupy basically the same region of Ω, centered between hierarchical and anti-hierarchical structures.Their co-occupation occurs within the bow-tie plane at T(G) = 0.
IV. NULL MODELS AND REAL NETWORK ANALYSIS: Metabolic, neural, linguistic, and some social networks occupy the lower bow-tie domain within the cloud of random graphs.Metabolic networks have a larger central cycle than their randomized counterparts, consistent with molecule reuse and recycling.
IV. NULL MODELS AND REAL NETWORK ANALYSIS: Gene regulatory and protein kinase networks form a group with slightly positive treeness, very high orderability, and variable feedforwardness.Their separation from the random cloud is associated with transcription factors at the network top participating in cycles.
IV. NULL MODELS AND REAL NETWORK ANALYSIS: Ecological flow graphs form an isolated cluster around u(G) = (0.35, 0.45, 0.25), combining pyramidal structure with loops.Their low orderability is consistent with recycling in trophic networks.
IV. NULL MODELS AND REAL NETWORK ANALYSIS: Most datasets lie within the envelope predicted by random graphs, suggesting that hierarchical order can arise from random fluctuations while some networks reflect functional constraints.The paper identifies four clusters and connects their locations with different scenarios for hierarchical organization.

V. MORPHOSPACE ACCESSIBILITY BY DRIVEN EVOLUTION

In silico evolution tests which regions of the hierarchy morphospace are accessible. Accessibility depends strongly on orderability, while some accessible extreme regions remain unoccupied by real networks.

V. MORPHOSPACE ACCESSIBILITY BY DRIVEN EVOLUTION: The evolutionary search starts from small random graphs and attempts to reach evenly gridded target points throughout Ω.This procedure estimates how accessible different morphospace regions are.
V. MORPHOSPACE ACCESSIBILITY BY DRIVEN EVOLUTION: The null-model cloud is easily accessible, and hierarchical and anti-hierarchical regions are approximately symmetric.Finite-size effects and high cycle counts produce deviations, especially at low orderability.
V. MORPHOSPACE ACCESSIBILITY BY DRIVEN EVOLUTION: At O = 0.15, extreme values of treeness and feedforwardness are inaccessible in the in silico evolutionary experiments.This restriction is relaxed at O = 0.5, where a large region of high reachability appears.
V. MORPHOSPACE ACCESSIBILITY BY DRIVEN EVOLUTION: At O = 0.5, some highly reachable regions are not occupied by real networks, suggesting that random fluctuations can generate order without adaptation.The paper therefore assigns a major role to non-adaptive processes in shaping hierarchies.
V. MORPHOSPACE ACCESSIBILITY BY DRIVEN EVOLUTION: As O approaches 1, the possible range of F contracts until only F = 1 configurations remain near the upper bound.These configurations correspond to feedforward networks, including electronic circuits and software networks.

VI. CONCLUDING REMARKS

The paper frames hierarchy through a formal network-based morphospace while recognizing that evolutionary and structural constraints limit the space of possible organizations. Its framework characterizes hierarchical deviations and supports comparisons between real and random networks, while leaving functionality, dynamics, and weighted relations for future work.

VI. CONCLUDING REMARKS: Evolutionary constraints and network-growth rules limit the repertoire of potential designs in biological and cultural systems.The study examines these constraints under a static view dominated by causal relations among components and modules.
VI. CONCLUDING REMARKS: Driven evolution explored 300 target points across three morphospace sections, with reachability assessed over 10^3 generations and 250 experiments.Colors indicate the generation at which grid points were acquired; blue denotes early accessibility and red denotes failure before 1,000 iterations.
VI. CONCLUDING REMARKS: The formalism defines hierarchy through deviations from a perfectly hierarchical configuration and quantifies those deviations using three coordinates.Its conceptual apparatus includes graph relations, condensation, and layered structure.
VI. CONCLUDING REMARKS: The framework operates on directed graphs and uses condensation to represent strongly connected components as nodes, producing a feedforward structure for hierarchical analysis.The resulting condensed graph can retain node weights corresponding to the number of original elements represented by each component.
VI. CONCLUDING REMARKS: A perfect hierarchy is represented by a directed tree whose leaves all occur at the same depth.The result follows from acyclicity, reversible command chains, branching, connectivity, and equal path lengths from the root to leaves.

Appendix D: Detailed derivation of the Coordinates of Hierarchy

The hierarchy descriptor represents each directed graph in a three-dimensional morphospace using treeness, feedforwardness, and orderability. These coordinates quantify pyramidal structure, cycle placement, and path reversibility, with limiting cases corresponding to hierarchical, antihierarchical, cyclical, and ordered structures.

Coordinate system: Hierarchy coordinates are defined as u(G) = (T(G), F(G), O(G)), where T, F, and O denote treeness, feedforwardness, and orderability.The coordinates map every directed graph to a point in the hierarchy morphospace.
Orderability: Orderability O(G) measures the fraction of nodes outside cycles, equaling 1 for trees or feed-forward networks and 0 for wholly cyclical networks.The condensed graph represents strongly connected components as weighted nodes, allowing cyclic and non-cyclic regions to be distinguished.
Feedforwardness: Feedforwardness F(G) measures where non-orderable regions occur along paths beginning at maximal nodes, with F(G) = 1 in directed acyclic graphs and F(G) = 0 in a single strongly connected component.Together, O(G) and F(G) describe both the location of cycles and their impact on the graph’s causal organization.
Treeness: Treeness T(G) compares top-down path-choice diversity with uncertainty when paths are reversed, thereby measuring pyramidal structure and command ambiguity.Treeness ranges from hierarchical graphs with T > 0 through non-pyramidal graphs with T = 0 to anti-hierarchical graphs with T < 0.

a. T in random directed graphs

For random directed graphs, symmetry between each graph and its edge-reversed counterpart yields an expected treeness coordinate of zero. Generating-function analysis also provides qualitative estimates for cyclic structure, while feedforwardness changes sharply with connectivity.

Expected treeness: ⟨T⟩ = 0 because randomly oriented graph ensembles are symmetric under reversing every edge direction.The derivation pairs graphs with their transposed adjacency matrices and applies the same symmetry after condensation.
Assumptions: The symmetry argument requires random edge directions with p = 1/2 and assumes ensemble averages collapse to the most probable observable value.The authors caution that a fully rigorous derivation would require deeper examination of these assumptions.
Connectivity effects: Increasing connectivity raises the variance of T because condensation leaves a very small graph, while F decreases sharply as connectivity increases.The change in F is tied to condensation and the resulting path structure, but its analytical connection to connectivity remains unresolved.
Cyclic structure: Under strong independence assumptions for in- and out-degrees, generating functions provide a rough estimate of the giant strongly connected component.The authors explicitly characterize the independence condition as strong, so the resulting prediction is qualitative.

Appendix E: Analysis of Networks

The analysis compares directed random-network models with 125 real networks spanning multiple system types. Random models occupy characteristic morphospace regions, while real networks form distinct groups whose locations can reflect cycles, feedforward organization, and functional structure.

Model networks: Directed ER, BA, and Callaway models show similar morphospace behavior across connectivity levels.Highly connected models cluster near T ∈ (−1, 1), F ≈ (0, 0.5), O ≈ 0; low-connectivity models approach T = 0, F = 1, O = 1.
Model networks: At low connectivity, models approach T = 0, F = 1, O = 1, a region occupied only by directed acyclic graphs.At high connectivity, condensation produces small condensed graphs and greater variance in T.
Real networks: The empirical collection contains 125 networks from 13 system types, including cellular, neural, linguistic, social, technological, ecological, and gene-regulatory systems.The networks include food webs, metabolic networks, electronic circuits, software, citation, ownership, blog, and gene-regulatory graphs.

b. Randomization Methods

The randomization methods generate network ensembles while preserving structural features of the original graphs. One method preserves undirected degree sequence and component structure, while the other preserves directed degree sequence and component structure.

Method A: Method A preserves the undirected degree sequence and component structure through a directed local-swap algorithm.This distinguishes it from standard configuration-model rewiring, which does not preserve component structure.
Method B: Method B preserves the directed degree sequence and component structure, making it more restrictive than Method A.Only arrow-compatible chain structures can be rewired because the directions of links matter.
Randomized ensembles: Each real network receives 100 randomized replicas after up to 4|E| link switches or 20|E| trials.The trial limit commonly applies to ensembles with few members, including overly dense, sparse, or structurally unusual networks.

c. Confronting real data with their randomized counterparts

Randomized ensembles provide a null comparison for locating real networks in the TFO morphospace. Real networks generally differ from randomized counterparts, especially when directed degree sequence is not conserved, while evolutionary experiments probe accessibility of morphospace regions.

Randomized comparison: Randomization compares each real network’s TFO coordinates with percentile distributions from ensembles generated by iterative arc rewiring.The comparison avoids assuming a particular statistical distribution for randomized graphs.
Randomized comparison: Real networks fall outside the median percentile of their randomized ensembles in morphospace.This indicates that real networks are not representative graphical configurations for their degree sequences.
Randomized comparison: The real-versus-randomized difference is stronger under method a than method b because method b imposes a stricter graphical restriction.Method a does not conserve the directed degree sequence, whereas method b does.
Patterns in TFO space: Most networks have T values near zero, but food webs and most gene regulatory networks are positively biased while electronic circuits are slightly negative.Positive T denotes hierarchical organization, whereas negative T denotes anti-hierarchical organization.
Patterns in TFO space: Real networks generally lie far from randomized whiskers in F and O, with randomizations showing more cyclic character, especially when directed degree sequence is not conserved.The pattern suggests that input-output organization contributes to TFO values beyond local connectivity correlations.