Identification of essential proteins using induced stars in protein–protein interaction networks

Chrysafis Vogiatzis, Mustafa Can Camur

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)703-718
Number of pages16
JournalINFORMS Journal on Computing
Issue number4
StatePublished - Sep 2019
Externally publishedYes


  • Centrality
  • Complex network analysis
  • Protein-protein interaction networks

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Identification of essential proteins using induced stars in protein–protein interaction networks'. Together they form a unique fingerprint.

Cite this