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 minimizes a score function, termed agony. This function penalizes the links violating the hierarchy in a way depending on the strength of the violation. To investigate the detectability of ranking hierarchies we introduce an ensemble of random graphs, the Hierarchical 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 characterize the detectability threshold and we show that an iterated version of agony can partly overcome this resolution limit. |
Year | Venue | Field |
---|---|---|
2016 | arXiv: Social and Information Networks | Random graph,Ranking,Computer science,Social network analysis,Directed graph,Stochastic block model,Artificial intelligence,Score,Hierarchy,Iterated function,Machine learning |
DocType | Volume | Citations |
Journal | abs/1608.06135 | 0 |
PageRank | References | Authors |
0.34 | 8 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Elisa Letizia | 1 | 0 | 0.34 |
Paolo Barucca | 2 | 11 | 3.76 |
Fabrizio Lillo | 3 | 41 | 10.66 |