Graph Hierarchy: A novel approach to understanding hierarchical structures in complex networks
arXiv:1908.04358
Abstract
Trophic coherence, a measure of a graph's hierarchical organisation, has been shown to be linked to a graph's structural and dynamical aspects such as cyclicity, stability and normality. Trophic levels of vertices can reveal their functional properties and partition and rank the vertices accordingly. Yet trophic levels and hence trophic coherence can only be defined on graphs with basal vertices, vertices with zero in-degree. Consequently, trophic analysis of graphs had been restricted until now. In this paper we introduce a novel framework, a generalisation of trophic levels, which we call hierarchical levels, that can be defined on any simple graph. Within this general framework, we develop additional metrics named influence centrality, a measure of a vertices ability to influence dynamics, and democracy coefficient, a measure of overall feedback in the system, both of which have implications for the controllability of complex systems. We discuss how our generalisation relates to previous attempts and what new insights are illuminated on the topological and dynamical aspects of graphs. Finally, we show how the hierarchical structure of a network relates to the incidence rate in a SIS epidemic model.
arXiv comment32 pages, 26 figures
References in corpus (11)
- The structure and function of complex networks
- Hierarchical organization of modularity in metabolic networks
- Epidemic processes in complex networks
- Hierarchical Organization in Complex Networks
- Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
- Hierarchy measure for complex networks
- Trophic coherence determines food-web stability
- On the Origins of Hierarchy in Complex Networks
- Hierarchy Measures in Complex Networks
- May's Instability in Large Economies
- Looplessness in networks is linked to trophic coherence