Source-linked AI summary
Hierarchy measure for complex networks
Enys Mones, Lilla Vicsek, Tamás Vicsek
TL;DR
The paper addresses the lack of a widely accepted quantitative measure of hierarchy in complex networks. It generalizes m-reach centrality to define global reaching centrality, evaluates it on synthetic and real networks, and proposes visualization for large graphs. The measure varies with adjustable hierarchy, relates to controllability in real networks, and supports qualitative visualization of hierarchical structure.
Problem
Existing hierarchy concepts and measures lack a unique, widely accepted quantitative characterization for complex networks.
Method
The paper generalizes m-reach centrality to define global reaching centrality and extends the framework to weighted and undirected networks, alongside a large-network visualization procedure.
Results
The GRC increases monotonically with the adjustable hierarchy parameter, relates moderately to controllability in real networks, and supports qualitative comparisons of hierarchical structure.
Takeaways & Limitations
GRC provides a broadly applicable way to quantify hierarchy while accounting for loops and undirected edges and helping visualize large network structure.
Takeaways & Limitations
Sugiyama-based hierarchical visualization becomes difficult beyond 2-300 nodes and can produce misleading layouts regardless of whether hierarchy is present.
Abstract
from arXiv · showhide
Nature, technology and society are full of complexity arising from the intricate web of the interactions among the units of the related systems (e.g., proteins, computers, people). Consequently, one of the most successful recent approaches to capturing the fundamental features of the structure and dynamics of complex systems has been the investigation of the networks associated with the above units (nodes) together with their relations (edges). Most complex systems have an inherently hierarchical organization and, correspondingly, the networks behind them also exhibit hierarchical features. Indeed, several papers have been devoted to describing this essential aspect of networks, however, without resulting in a widely accepted, converging concept concerning the quantitative characterization of the level of their hierarchy. Here we develop an approach and propose a quantity (measure) which is simple enough to be widely applicable, reveals a number of universal features of the organization of real-world networks and, as we demonstrate, is capable of capturing the essential features of the structure and the degree of hierarchy in a complex network. The measure we introduce is based on a generalization of the m-reach centrality, which we first extend to directed/partially directed graphs. Then, we define the global reaching centrality (GRC), which is the difference between the maximum and the average value of the generalized reach centralities over the network. We investigate the behavior of the GRC considering both a synthetic model with an adjustable level of hierarchy and real networks. Results for real networks show that our hierarchy measure is related to the controllability of the given system. We also propose a visualization procedure for large complex networks that can be used to obtain an overall qualitative picture about the nature of their hierarchical structure.
Introduction
Hierarchy is widespread across natural, technological, and social networks, but existing concepts and measures do not provide a broadly accepted quantitative characterization. The paper therefore targets a universally applicable hierarchy measure and an unbiased visualization method for large graphs.
- Hierarchy appears in physical, chemical, biological, social, and technological systems, including animal, regulatory, and leader-follower networks.
- Hierarchy lacks a unique, widely accepted definition, motivating a quantitative measure as a starting point for refining the concept.
- The paper distinguishes order, nested, and flow hierarchies, focusing on flow hierarchy because it is tied to network interactions.
- Existing hierarchy measures rely on free parameters, penalize loops or multiple edges, or apply only to fully directed or fully undirected graphs.
- Sugiyama-based hierarchical layouts become difficult beyond 2-300 nodes, leave level meanings undefined, can mislead, and require NP-complete or NP-hard steps.
- The paper aims to provide a universally applicable hierarchy measure and an unbiased, unambiguous visualization technique for large complex networks.
Definition of the global reaching centrality
The paper defines flow hierarchy through how unevenly nodes can reach the rest of an unweighted directed graph. It then extends the framework to weighted and undirected networks using path weights and undirected reachability.
- The proposed hierarchy measure should avoid free parameters, apply to directed graphs, extend to weighted and undirected graphs, and support graph layout.
- Unweighted directed networks: Local reaching centrality CR(i) is the proportion of other nodes reachable from node i through outgoing edges.
- Unweighted directed networks: Global reaching centrality measures hierarchy as the heterogeneity between the highest and average local reaching centrality values.
- Unweighted directed networks: GRC = 1 occurs when only one node has nonzero local reaching centrality, as in a star graph.
- Weighted and undirected networks: For weighted directed graphs, local reaching centrality averages edge weights along directed paths and selects the strongest among multiple shortest paths.
- Weighted and undirected networks: For undirected unweighted graphs, the directed-distance term is removed, yielding a quantity related to generalized closeness centrality for disconnected graphs.
Methods
The methods introduce an adjustable hierarchical network with tunable edge structure, randomize real networks for comparison, and construct layered visualizations from node-level quantities.
- Synthetic model: The adjustable hierarchical network starts from a directed tree and adds random edges with a tunable proportion constrained to preserve or alter hierarchy.Nodes receive levels from the tree, with the root at the highest level and leaves at ℓ=1.
- Synthetic model: Down, horizontal, and up edges respectively conserve hierarchy, slightly influence it, or strongly change the directed tree’s structure.
- Network randomization: Real networks are randomized first with matching in- and out-degree distributions, then by repeatedly rewiring edge endpoints.The number of rewired edge pairs is ten times the number of edges.
- Hierarchical visualization: The visualization grades nodes by a local quantity and adds them to successive levels while within-level variation remains below z times the graph-wide variation.The adjustable coefficient z controls the layout’s vertical extension for large graphs.
- Hierarchical visualization: Levels are horizontally centered and vertically spaced according to logarithmic differences between their average node quantities, while preserving a fixed overall graph height.The method produces few close levels for localized distributions and many levels with greater vertical extension for non-localized distributions.
- Implementation: Graph generations, randomizations, and shortest-path calculations use implemented functions from the igraph software package.
Results
Synthetic and real-network analyses show that GRC tracks hierarchical structure, decreases with network density, and is moderately related to controllability. Visualizations and case studies provide qualitative and structural support for these patterns.
- Adjustable hierarchical network: The adjustable hierarchical model’s GRC increases monotonically with p and spans the (0,1) interval, supporting its use as a hierarchy measure.The local-reaching-centrality distribution also changes continuously from random to fully hierarchical states.
- Classical random networks: Higher average degree generally produces lower GRC, and the measure vanishes at large densities in both ER and SF networks.Figure 4 likewise reports that larger density makes the same hierarchy level less likely in the adjustable model.
- Real networks: Real networks show a broad GRC range: food webs are most hierarchical, whereas intra-organizational trust networks are least hierarchical.The paper directs edge orientation from nodes with greater effect toward nodes with lesser effect before calculating reaching centrality.
- Real networks: GRC and the relative number of driver nodes are moderately positively correlated, indicating that hierarchical networks are harder to control.For synthetic networks with ⟨k⟩≥5, the two quantities are close except for highly hierarchical graphs with p > 0.85.
- Real networks: Terrorist-network analyses identify previously reported leaders and additional important participants, supporting the effectiveness of generalized reaching centralities for undirected graphs.The Bojinka case highlights Isamudin and K. S. Mehmood, while the London Bombings analysis identifies H. R. Awsat, M. S. Khan, and I. M. Said.
- Visualization of large networks: The hierarchical layouts distinguish GrassLand as highly hierarchical and Enron as very egalitarian, consistent with their GRC values.Electrical and biological regulatory networks occupy intermediate structural patterns between these extremes.
Discussion
The paper proposes GRC as a parameter-free hierarchy measure based on heterogeneity in nodes’ reaching centrality. It also reports a positive association between hierarchy and controllability under switchboard dynamics.
- Discussion: GRC measures hierarchy through the heterogeneity of local reaching centrality across the whole graph.Local reaching centrality reflects the proportion of nodes reachable from each node.
- Discussion: Unlike earlier measures, GRC does not penalize loops or undirected edges and treats bidirectionally connected node pairs as equivalent.The method incorporates these structures into the hierarchy measure rather than excluding or penalizing them.
- Discussion: GRC requires neither free parameters nor optimization, with node ranks emerging naturally from the measure.
- Discussion: Hierarchical structures are more easily controllable because controllability and hierarchy are positively correlated under switchboard dynamics.