1-3 July 2021
Europe/Warsaw timezone

Hierarchy depth in directed networks

2 Jul 2021, 17:13



Krzysztof Suchecki (Warsaw University of Technology)


The term "hierarchy" when applied to networks can mean one of the few structures: simple order hierarchy meaning ordering of elements, nested hierarchy that is multi-level community structure or flow hierarchy defined by directed links that show causal or control structure in the network.
We introduce two measures of node depth for flow hierarchy in directed networks, measuring the level of hierarchy the nodes belong to. Rooted depth is defined as distance from specific root node and relative depth relies on directed links serving as "target node has larger depth than source" relations.
We explore the behavior of these two measures, their properties and differences between them. To cope with eventual directed loops in the networks we introduce loop-collapse method, that evens out depth values for all nodes in the same directed loop.
We investigate the behavior of the introduced depth measures in random graphs of different sizes and densities as well as some real network topologies. Maximum depth depends on network density, first increasing with mean degree, up to percolation threshold and declining afterwards as the number of loops increase.

Primary author

Krzysztof Suchecki (Warsaw University of Technology)


Janusz Hołyst (Warsaw University of Technology)

Presentation Materials