Using arborescences to estimate hierarchicalness in directed complex networks

Michele Coscia

Scholarly Articles from Harvard Kennedy School of Government

Abstract: Complex networks are a useful tool for the understanding of complex systems. One of the emerging properties of such systems is their tendency to form hierarchies: networks can be organized in levels, with nodes in each level exerting control on the ones beneath them. In this paper, we focus on the problem of estimating how hierarchical a directed network is. We propose a structural argument: a network has a strong top-down organization if we need to delete only few edges to reduce it to a perfect hierarchy—an arborescence. In an arborescence, all edges point away from the root and there are no horizontal connections, both characteristics we desire in our idealization of what a perfect hierarchy requires. We test our arborescence score in synthetic and real-world directed networks against the current state of the art in hierarchy detection: agony, flow hierarchy and global reaching centrality. These tests highlight that our arborescence score is intuitive and we can visualize it; it is able to better distinguish between networks with and without a hierarchical structure; it agrees the most with the literature about the hierarchy of well-studied complex systems; and it is not just a score, but it provides an overall scheme of the underlying hierarchy of any directed complex network.

Date: 2018
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Published in PLOS ONE

Downloads: (external link)
http://dash.harvard.edu/bitstream/handle/1/3714031 ... ness-notrackchng.pdf (application/pdf)
http://dash.harvard.edu/bitstream/handle/1/3714031 ... ness-notrackchng.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hrv:hksfac:37140312

Access Statistics for this paper

More papers in Scholarly Articles from Harvard Kennedy School of Government Contact information at EDIRC.
Bibliographic data for series maintained by Office for Scholarly Communication ().