Balanced Ranking with Relative Centrality: A multi-core periphery perspective

Ranking of vertices in a graph for different objectives is one of the most fundamental tasks in computer science. It is known that traditional ranking algorithms can generate unbalanced ranking when the graph has underlying communities, resulting in loss of information, polarised opinions, and reduced diversity (Celis, Straszak & Vishnoi [ICALP 2018]). In this paper, we focus on unsupervised ranking on graphs and observe that popular centrality-measure-based ranking algorithms such as PageRank may often generate unbalanced ranking here as well. We address this issue by coining a new approach, which we term relative centrality. Our approach is based on an iterative graphdependent local normalization of the centrality score, which promotes balancedness while maintaining the validity of the ranking. We further quantify the reasons behind this unbalancedness of centrality measures. using novel structure that we propose. We term this as the multi-core-periphery with communities (MCPC) structure. We provide theoretical and extensive simulation support for our approach towards resolving the unbalancedness in MCPC. Finally, we consider graph embeddings of 11 single-cell datasets. We observe that top-ranked as per existing centrality measures are better separable into the ground truth communities. However, due to the unbalanced ranking, the top nodes often do not contain points from some communities. Here, our relative-centrality-based approach generates a ranking that provides a similar improvement in clusterability while providing significantly higher balancedness.