Emergent Hierarchy Through Conductance-based Degree Constraints

Abstract

The presence of hierarchy in many real-world networks is not yet fully understood. We observe that complex interaction networks are often coarse-grain models of vast modular networks, where tightly connected subgraphs are agglomerated into nodes for simplicity of representation and computational feasibility. The emergence of hierarchy in such growing complex networks may stem from one particular property of these ignored subgraphs: their graph conductance. Being a quantification of the main bottleneck of flow through the coarse-grain node, this scalar quantity implies a structural limitation and supports the consideration of heterogeneous degree constraints. The internal conductance values of the subgraphs are mapped onto integer degree restrictions, which we call internal bottlenecks, by using inverse cumulative density functions. This leads to a hidden variable model based on the rich-get-richer scheme. It is shown that imposing such restrictions generally leads to an increased measure of hierarchy and alters the tail of the degree distribution in a predictable way. Thus, a mechanism is provided whereby inherent limitations on network flow leads to hierarchical self-organization.

Keywords

• hierarchy
• conductance
• randomly growing network