Hierarchy Measures in Complex Networks

Abstract

Using each node's degree as a proxy for its importance, the topological hierarchy of a complex network is introduced and quantified. We propose a simple dynamical process used to construct networks which are either maximally or minimally hierarchical. Comparison with these extremal cases as well as with random scale-free networks allows us to better understand hierarchical versus modular features in several real-life complex networks. For random scale-free topologies the extent of topological hierarchy is shown to smoothly decline with $\gamma$ -- the exponent of a degree distribution -- reaching its highest possible value for $\gamma \le 2$ and quickly approaching zero for $\gamma >3$.

4 pages, 4 figures

References in corpus (7)

• Assortative mixing in networks
• Random graphs with arbitrary degree distributions and their applications
• Specificity and stability in topology of protein networks
• Scale-free topology of e-mail networks
• Organization of Growing Random Networks
• Pattern Detection in Complex Networks: Correlation Profile of the Internet
• The origin of degree correlations in the Internet and other networks

Cited by in corpus (53)

• Hyperbolic Geometry of Complex Networks
• Extracting the hierarchical organization of complex systems
• Maximal planar networks with large clustering coefficient and power-law degree distribution
• Hierarchy measure for complex networks
• On the Origins of Hierarchy in Complex Networks
• Self-similar disk packings as model spatial scale-free networks
• The evolutionary origins of hierarchy
• Community structure and ethnic preferences in school friendship networks
• Ordinary Percolation with Discontinuous Transitions
• Hierarchical characterization of complex networks
• Searchability of Networks
• Hide and seek on complex networks
• Structural constraints in complex networks
• Geographical Coarsegraining of Complex Networks
• Topology regulates pattern formation capacity of binary cellular automata on graphs
• The shortest path to complex networks
• Outer-totalistic cellular automata on graphs
• Networking - A Statistical Physics Perspective
• Interplay Between Hierarchy and Centrality in Complex Networks
• On the basic computational structure of gene regulatory networks
• Load distribution in weighted complex networks
• Navigating Networks with Limited Information
• The Network of Scientific Collaborations within the European Framework Programme
• Self-Assembly of Information in Networks
• Hierarchical networks of scientific journals
• Extracting tag hierarchies
• Random walk hierarchy measure: What is more hierarchical, a chain, a tree or a star?
• The effects of degree correlations on network topologies and robustness
• Multiple Scale-Free Structures in Complex Ad-Hoc Networks
• Clustering under the line graph transformation: Application to reaction network
• Scaling of Clusters near Discontinuous Percolation Transitions in Hyperbolic Networks
• Measuring the Hierarchy of Feedforward Networks
• Self-organization of structures and networks from merging and small-scale fluctuations
• Hierarchy in directed random networks
• The Regularizing Capacity of Metabolic Networks
• Time evolution of the hierarchical networks between PubMed MeSH terms
• Aggregate Dynamics in an Evolutionary Network Model
• Degree Landscapes in Scale-Free Networks
• Talent and experience shape competitive social hierarchies
• Real-Space Renormalization Group for Spectral Properties of Hierarchical Networks
• Radial Structure of the Internet
• Comparing the hierarchy of keywords in on-line news portals
• Edge Balance Ratio: Power Law from Vertices to Edges in Directed Complex Network
• Static and dynamic characteristics of protein contact networks
• Local multiresolution order in community detection
• Information slows down hierarchy growth
• Correlations in Networks associated to Preferential Growth
• Geometric detection of hierarchical backbones in real networks
• One Hub-One Process: A Tool Based View on Regulatory Network Topology
• Generating Hierarchically Modular Networks via Link Switching
• Simple estimation of hierarchical positions and uncertainty in networks of asymmetric interactions
• Graph Hierarchy: A novel approach to understanding hierarchical structures in complex networks
• Comparing the hierarchy of author given tags and repository given tags in a large document archive