Graph hierarchy: a novel framework to analyse hierarchical structures in complex networks

Giannis Moutsinas, Choudhry Shuaib, Weisi Guo, Stephen Jarvis

    Research output: Contribution to journalArticlepeer-review

    6 Citations (Scopus)
    63 Downloads (Pure)

    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, partition and rank the vertices accordingly. Trophic levels and hence trophic coherence can only be defined on graphs with basal vertices, i.e. vertices with zero in-degree. Consequently, trophic analysis of graphs had been restricted until now. In this paper we introduce a hierarchical framework which can be defined on any simple graph. Within this general framework, we develop several metrics: hierarchical levels, a generalisation of the notion of trophic levels, influence centrality, a measure of a vertex’s ability to influence dynamics, and democracy coefficient, a measure of overall feedback in the system. 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 and the economic insights we can gain through it.

    Original languageEnglish
    Article number13943
    JournalScientific Reports
    Volume11
    Issue number1
    DOIs
    Publication statusPublished - 6 Jul 2021

    Bibliographical note

    Funding Information:
    The authors would like to express their gratitude to Robert MacKay for his invaluable advice and showing their approach to the subject. CS also gratefully acknowledges funding from the UK Engineering and Physical Sciences Research Council under the EPSRC Centre for Doctoral Training in Urban Science (EPSRC grant no. EP/ L016400/1).

    Publisher Copyright:
    © 2021, The Author(s).

    Funder

    UK Engineering and Physical Sciences Research Council under the EPSRC Centre for Doctoral Training in Urban Science (EPSRC grant no. EP/ L016400/1).

    ASJC Scopus subject areas

    • General

    Fingerprint

    Dive into the research topics of 'Graph hierarchy: a novel framework to analyse hierarchical structures in complex networks'. Together they form a unique fingerprint.

    Cite this