Resolution of ranking hierarchies in directed networks

PLoS One. 2018 Feb 2;13(2):e0191604. doi: 10.1371/journal.pone.0191604. eCollection 2018.

Abstract

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.

Publication types

  • Research Support, Non-U.S. Gov't

MeSH terms

  • Algorithms
  • Social Support*
  • Stochastic Processes

Grants and funding

EL received no specific funding for this work. PB acknowledges support from First Future and Emerging Technologies: Project DOLFINS nr. 640772 https://ec.europa.eu/programmes/horizon2020/en/news/first-future-and-emerging-technologies-fet-proactive-projects-under-horizon-2020-framework and First Future and Emerging Technologies: IP Project MULTIPLEX nr. 317532 http://cordis.europa.eu/project/rcn/106336_en.html FL acknowledges support by the European Community’s H2020 Program under the scheme INFRAIA-1- 2014-2015: Research Infrastructures, grant agreement no. 654024 SoBigData: Social Mining & Big Data Ecosystem. https://ec.europa.eu/research/participants/portal/desktop/en/opportunities/h2020/calls/h2020-infraia-2014-2015.html#c,topics=callIdentifier/t/H2020-INFRAIA-2014-2015/1/1/1/default-group&callStatus/t/Forthcoming/1/1/0/default-group&callStatus/t/Open/1/1/0/default-group&callStatus/t/Closed/1/1/0/default-group&+identifier/desc The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.