Centrality in directed networks

The identification of important nodes in a network is a pervasive task in a variety of disciplines from sociology and bibliometry to geography and chemistry, and an ever growing number of centrality indices is proposed for this purpose. While such indices are often ad-hoc, preservation of the vicinal preorder has been identified as the core axiom shared by centrality rankings on undirected graphs. We extend this idea to directed graphs by defining vertex preorders based on directed neighborhood-inclusion criteria. While, for the undirected case, the vicinal preorder is total on threshold graphs and preserves all standard centrality indices, we show that our generalized preorders are total on certain subclasses of threshold digraphs. We thus provide a consistent formalization of the hitherto rather conceptual notions of radial, medial, and hierarchical centralities. Through the criteria different notions of centrality are distinguishable, as we exemplify with selected standard centrality indices.