Resolution of ranking hierarchies in directed networks

An iterative version of a method to identify hierarchies and rankings of nodes in directed networks can partly overcome its resolution limit.

PLOS ONE 13, 2 (2018)

E. Letizia, P. Barucca, F. Lillo

Resolution of ranking hierarchies in directed networks

Identifying hierarchies and rankings of nodes in directed graphs is fundamental in many applications such as social network analysis, biology, economics, and finance. A recently proposed method identifies the hierarchy by finding the ordered partition of nodes which minimises a score function, termed agony. This function penalises the links violating the hierarchy in a way depending on the strength of the violation. To investigate the resolution of ranking hierarchies we introduce an ensemble of random graphs, the Ranked Stochastic Block Model. We find that agony may fail to identify hierarchies when the structure is not strong enough and the size of the classes is small with respect to the whole network. We analytically characterise the resolution threshold and we show that an iterated version of agony can partly overcome this resolution limit.

More in Hidden communities

  • Proceedings of the National Academy of Sciences of the USA

    True scale-free networks

    Naturally occurring networks have an underlying scale-free structure that is often clouded by finite-size effects in the sample data.

  • Physical Review E

    Communities in networks

    A new tool derived from information theory quantitatively identifies trees, hierarchies and community structures within complex networks.

  • Journal of Statistical Mechanics

    Disentangling links in networks

    Inference from single snapshots of temporal networks can misleadingly group communities if the links between snapshots are correlated.

  • Physical Review E

    Spectral partitioning

    The spectral density of graph ensembles provides an exact solution to the graph partitioning problem and helps detect community structure.