  In this work, we propose a novel centrality metric, referred to as star
centrality, which incorporates information from the closed neighborhood of a
node, rather than solely from the node itself, when calculating its topological
importance. More specifically, we focus on degree centrality and show that in
the complex protein-protein interaction networks it is a naive metric that can
lead to misclassifying protein importance. For our extension of degree
centrality when considering stars, we derive its computational complexity,
provide a mathematical formulation, and propose two approximation algorithms
that are shown to be efficient in practice. We portray the success of this new
metric in protein-protein interaction networks when predicting protein
essentiality in several organisms, including the well-studied Saccharomyces
cerevisiae, Helicobacter pylori, and Caenorhabditis elegans, where star
centrality is shown to significantly outperform other nodal centrality metrics
at detecting essential proteins. We also analyze the average and worst case
performance of the two approximation algorithms in practice, and show that they
are viable options for computing star centrality in very large-scale
protein-protein interaction networks, such as the human proteome, where exact
methodologies are bound to be time and memory intensive.
