The stochastic pseudo-star degree centrality problem

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.