The stochastic pseudo-star degree centrality problem

Mustafa C. Camur, Thomas C. Sharkey, Chrysafis Vogiatzis

Research output: Contribution to journalArticlepeer-review


We introduce the stochastic pseudo-star degree centrality problem, which focuses on a novel probabilistic group-based centrality metric. The goal is to identify a feasible induced pseudo-star, which is defined as a collection of nodes forming a star network with a certain probability, such that it maximizes the sum of the individual probabilities of unique assignments between the star and its open neighborhood. The feasibility is measured as the product of the existence probabilities of edges between the center node and leaf nodes and the product of one minus the existence probabilities of edges among the leaf nodes. First, the problem is shown to be NP-complete. We then propose a non-linear binary optimization model subsequently linearized via McCormick inequalities. We test both classical and modern Benders Decomposition algorithms together with both two- and three-phase decomposition frameworks. Logic-based-Benders cuts are examined as alternative feasibility cuts when needed. The performance of our implementations is tested on small-world (SW) graphs and a real-world protein-protein interaction network. The SW networks resemble large-scale protein-protein interaction networks for which the deterministic star degree centrality has been shown to be an efficient centrality metric to detect essential proteins. Our computational results indicate that Benders implementations outperforms solving the model directly via a commercial solver in terms of both the solution time and the solution quality in every test instance. More importantly, we show that this new centrality metric plays an important role in the identification of essential proteins in real-world networks.

Original languageEnglish (US)
Pages (from-to)525-539
Number of pages15
JournalEuropean Journal of Operational Research
Issue number2
StatePublished - Jul 16 2023


  • Benders decomposition
  • Integer programming
  • Network analysis with biological applications
  • Probabilistic group-based centrality
  • Protein-protein interaction networks

ASJC Scopus subject areas

  • Information Systems and Management
  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research


Dive into the research topics of 'The stochastic pseudo-star degree centrality problem'. Together they form a unique fingerprint.

Cite this